Мне нужно формально (с помощью функции перехода) описать машину Тьюринга, чтобы каждое слово w в {a,b}* заменяло каждое a на b и каждое b на a.
Я попробовал, и это мое решение:
(s,a) -> (s,b,R)
(s,b) -> (s,a,R)
(s, пусто) -> (n, пусто)
где n — состояние остановки, а s — начальное состояние.
Это работает? Спасибо!
Обычный подход к вопросам такого рода — либо «проверка», либо «доказательство». Здесь я покажу, как вы можете легко проверить, успешен ли ваш подход:
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>
At least in my eyes, this haskell code looks similar enough to your transition specification. The [] case in the third line of the definition of the cnv function stands for "empty list", i.e. it is your halting state. And for the recursion of this function it is the base case where recursion stops.
Что касается того, как формально доказать, что ваши автоматы закончились, я недостаточно специалист по информатике, чтобы помочь вам с этим. Кто-то другой может.
Ваша ТМ работает правильно. Если вы знакомы с обозначениями TM, почти очевидно, что ваше работает, поэтому формальное доказательство кажется излишним, но если вы действительно настаиваете на доказательстве с помощью математической индукции по длине ввода, это просто.
Утверждение: данный ТМ выполняет описанную функцию.
Доказательство: доказательство основано на сильной математической индукции по длине m исходной строки, изначально записанной на ленту ТМ.
Базовый случай: если входная лента содержит пустую строку, то НП выполняет переход (s,blank) -> (n,blank) и, следовательно, останавливается без изменения каких-либо символов ленты. Поскольку результирующая строка остается на ленте неизменной, это пустая строка. Бессмысленно верно, что пустая строка эквивалентна пустой строке после замены всех a на b и наоборот; в строке нет символов, противоречащих этому.
Гипотеза индукции: предположим, что ТМ правильно обрабатывает все входные строки длины до k включительно.
Шаг индукции: мы должны показать, что ТМ корректно обрабатывает все входные строки длины, равной k + 1. Заметим, что любая входная строка длины k + 1 в алфавите {a, b} равна некоторой входной строке длины k, с добавленным к нему символом a или символом b. Мы уже обнаружили, что ТМ корректно обрабатывает строки длины k; то есть он переставил все a на b и наоборот. Кроме того, поскольку TM должен был остановиться, последним выполненным переходом был (s,blank) -> (n,blank). Если бы в этот момент на ленте не было пустого места, а вместо этого было бы видно a или b, мы были бы в настоящем случае: то есть TM добрался бы до той же позиции, обработав префикс длины k из наша строка длины k + 1. Вместо выполнения перехода (s,blank) -> (n,blank) будет принудительно выполнен один из переходов (s,a) -> (s,b,R) или (s,b) -> (s,a,R), в зависимости от того, является ли (k + 1)-й символ a или b. Эти переходы правильно перевернут символ в позиции k + 1, оставив строку из k + 1, в которой все символы были правильно заменены. Следующий переход будет пустым и переход в состояние остановки. На этом доказательство заканчивается.
