Машина Тьюринга: такая, что для каждого слова w в {a, b} * оно изменит каждое a на b, а b на a, а затем остановится

Question

Мне нужно формально (с помощью функции перехода) описать машину Тьюринга так, чтобы каждое слово w в {a, b} * заменяло каждое a на b, а каждое b на a.

Я попробовал, и вот мое решение:

(s, a) -> (s, b, R)

(s, b) -> (s, a, R)

(с, пусто) -> (n, пусто)

где n - состояние остановки, а s - начальное состояние

Это работает? Спасибо!

Answer 1

Ваша ТМ работает правильно. Если вы знакомы с обозначениями ТМ, почти очевидно, что ваша работа работает, поэтому формальное доказательство кажется излишним, но если вы действительно настаиваете на доказательстве математической индукции на длине ввода, это просто.

Заявка: данный ТМ выполняет описанную функцию.

Доказательство: доказательство заключается в сильной математической индукции по длине m входной строки, изначально записанной на ленте ТМ.

Базовый случай: если входная лента содержит пустую строку, то ТМ выполняет переход (s, пусто) -> (n, пусто) и поэтому останавливается без изменения каких-либо символов ленты. Поскольку результирующая строка, оставленная на ленте, не изменилась, это пустая строка. Вакуумно верно, что пустая строка эквивалентна пустой строке после замены всех a на b и наоборот; в строке нет символов, противоречащих этому.

Гипотеза об индукции: предположим, что TM правильно обрабатывает все входные строки длиной до k включительно.

Шаг индукции: мы должны показать, что TM правильно обрабатывает все входные строки длины, равной k + 1. Обратите внимание, что любая входная строка длины k + 1 в алфавите {a, b} равна некоторой входной строке длина k, к которой добавляется либо символ a, либо символ b. Мы уже обнаружили, что TM правильно обрабатывает строки длины k; то есть он перевернул все a на b и наоборот. Кроме того, поскольку TM должен был остановиться, последний выполненный переход был (s, пусто) -> (n, пусто). Если бы вместо того, чтобы видеть пустым на ленте в этой точке, он вместо этого видел a или b, мы были бы в данном случае: то есть, ТМ добрался бы до той же позиции, обработав префикс длины k наша строка длиной k + 1. Вместо выполнения перехода (s, пробел) -> (n, пробел) он будет вынужден выполнить один из переходов (s, a) -> (s, b, R) или (s, b) -> (s, a, R), в зависимости от того, является ли (k + 1) -й символ a или b. Эти переходы правильно перевернут символ в позиции k + 1, оставляя строку k + 1, где все символы были правильно заменены. Следующий переход будет пустым и перейдет в состояние остановки. Это завершает доказательство.

Answer 2

Обычный подход к таким вопросам - «тест» или «доказательство». Здесь я покажу, как вы можете легко проверить, насколько успешен ваш подход:

GHCi, version 8.2.2: http://www.haskell.org/ghc/  
:? for help
Prelude> :{
Prelude| cnv ('a':xs) = 'b':cnv xs
Prelude| cnv ('b':xs) = 'a':cnv xs
Prelude| cnv [] = []
Prelude| :}
Prelude> cnv "abaaab"
"babbba"
Prelude>

По крайней мере, на мой взгляд, этот код на haskell достаточно похож на вашу спецификацию перехода. Регистр [] в третьей строке определения функции cnv означает «пустой список», т. Е. Это ваше состояние остановки. И для рекурсии этой функции это базовый случай, когда рекурсия останавливается.

Что касается того, как формально доказать, что ваши автоматы заканчиваются, мне не хватает специалиста по информатике, чтобы помочь вам в этом. Кто-то другой мог бы.