Построить машину Тьюринга, чтобы решить ww ^ Rw

Question

w ^ R является обратным к w, а w равно {0, 1} *.Поэтому ТМ должен выбрать слово, за которым следует обратное слово, за которым следует слово.Я не хочу ответа, я просто хочу, чтобы лидерство началось и встало на правильный путь.

Answer 1

Поскольку прошло некоторое время и ответ, вероятно, больше не нужен, я думаю, я предложу решение для будущих студентов, которые ищут пример того, как один язык может быть распознан машиной Тьюринга.

Вот идея. Мы возьмем в качестве ленточного алфавита {0, 1, a, b, c, d} и создадим одноленточную однолинейную машину Тьюринга, которая распознает w w ^ R w. Машина будет работать в пять этапов:

1. Заменить 0 и 1 в префиксе w w ^ R на a и b.
2. Посмотрите, является ли w w ^ R палиндромом.
3. Восстановите ленту в ее первоначальное состояние.
4. Заменить 0 и 1 в суффиксе w ^ R w на c и d.
5. Посмотрите, является ли w ^ R палиндромом.

Обратите внимание, что это просто один простой (для меня, чтобы понять, то есть) способ показать, что существует машина Тьюринга для распознавания этого языка. Естественно, показ того, что существует алгоритм для решения этой проблемы в любой эквивалентной по Тьюрингу системе вычислений, так же хорош (это доказывает, что существует ТМ) ... все же, это обрисовывает в общих чертах конструкцию одной такой ТМ. Также обратите внимание, что может быть более простой, эффективный или более интуитивно понятный TM для решения этой проблемы ... опять же, это только один подход.

Шаг 1 будет работать следующим образом:

• Условие: лента начинается с пробела, содержит любую строку в (0 + 1) * и сопровождается бесконечной строкой пустых квадратов.

• Постусловие: останавливается, если лента пуста или длина не кратна 3; иначе лента начинается с пробела, затем следует (a + b) ^ 2n (c + d) ^ n, за которым следует бесконечная строка пробелов.

  1. Переместить вправо.
  2. Если пусто, прекратите прием. В противном случае сканируйте вправо, пока не найдете пустой квадрат с лентой, затем двигайтесь влево.
  3. Измените ленту на c, если 0 или d, если 1.
  4. Сканируйте влево, пока не найдете пустой квадрат с лентой. Двигайся вправо.
  5. Если лента 0 или 1, измените на a или b и двигайтесь вправо. Если лента c или d, отменить отклонение.
  6. Если лента 0 или 1, измените на a или b и двигайтесь вправо. Если лента c или d, отменить отклонение.
  7. Если лента c или d, отсканируйте ее в начало и перейдите к шагу 2. В противном случае отсканируйте вправо до c или d, а затем сдвиньте влево.
  8. Измените ленту на c, если 0 или d, если 1.
  9. Сканируйте влево, пока не найдете a или b. Двигайся вправо.
  10. Повтор, начиная с 4.

Шаг 2 будет работать следующим образом:

• Условие: лента начинается с пробела, затем следует (a + b) ^ 2n (c + d) ^ n, за которым следует бесконечная строка пробелов.

• Постусловие: останавливается, если префикс (a + b) ^ 2n не является палиндромом; в противном случае оставляет ленту в таком состоянии, как D (c + d) ^ 3n D *

  1. Двигайтесь вправо.
  2. Если лента a (или b), двигайтесь вправо. Если лента c или d, перейдите к началу ленты, затем перейдите к шагу 3.
  3. Если лента c, d или пуста, отменить отклонение. В противном случае сканируйте вправо, пока не найдете символ c, d или пробел. Двигайся влево.
  4. Если лента представляет собой b (или a), отменить отклонение. В противном случае измените это на c (или d) и отсканируйте влево, пока не увидите пробел, c или d. Двигаться вправо. Измените a (или b) на c (или d). Двигайся вправо.
  5. Повторите, начиная с шага 2.

Шаг 3 будет работать следующим образом

• Условие: лента D (c + d) ^ 3n D *

• Постусловие: Лента D (0 + 1) ^ 3n D *

  1. Двигаться вправо.
  2. Если лента c, напишите 0 и двигайтесь вправо. Если лента d, напишите 1 и двигайтесь вправо. Если лента пуста, перейдите к первому пустому месту в конце ленты и перейдите к шагу 4.
  3. Повторите шаг 2.

Шаг 4 и 5 работают так же, как шаги 1 и 2, за исключением того, что вы работаете в обратном направлении (лента теперь выглядит как D (c + d) ^ n (a + b) ^ 2n D *, и вы должны проверить, часть (a + b) ^ 2n является палиндромом.

Любая строка, проходящая оба эти теста, должна иметь форму w w ^ R w, где w находится в (0 + 1) *.

Answer 2

В качестве подсказки обратите внимание, что ww ^R w должно иметь длину 3n для некоторого n (поскольку каждый символ появляется ровно три раза).Таким образом, вы можете построить машину Тьюринга, которая будет работать, подсчитав длину строки, используя ее для определения границ трех строк, а затем проверив, что все три части имеют соответствующую композицию.Если вы не можете сосчитать кратное 3 символам, вы можете сразу же отклонить.

В зависимости от того, какой тип TM разрешен, это может быть проще всего с машиной Turing с мультитреком или мультитейпом, чтобы вы могли разметитьписьма с дополнительной информацией.

Надеюсь, это поможет!