Условие задачи
Постройте машину Тьюринга, применимую ко всем словам x1x2…xn в алфавите {a, b} и переводящую их в слово α.
Ответ
Введем в алфавит дополнительный символ , ограничивающий входное слово с обеих сторон. Начальная конфигурация МТ обозревает ячейку с крайним левым символом слова.
Примем, что слово не может быть пустым.
Если слово начинается с символа а, то МТ из состояния q1 переходит в состояние q2 и сдвигается вправо, оставляя все символы слова без изменений, до символа , который она стирает, заменяя на символ а, и останавливается.
Если первый символ слова символ b, то МТ из состояния q1 переходит в состояние q3 и сдвигается вправо на одну ячейку. Если второй сим...
Потяни
