Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Построить машину Тьюринга, применимую ко всем словам X1X2...Xn в алфавите {а, b} и переводящую их в слово α

d Ученик (82), открыт 3 недели назад

α: XnXn-1..X1
2 ответа
Василий Пктров Искусственный Интеллект (117196) 3 недели назад
Просто строй длинную ленту , что бы больше мест для пропусков имела
Александрович Ученик (171) 3 недели назад
Для построения машины Тьюринга, преобразующей слова в алфавите {а, b} в слово α, можно использовать следующий алгоритм:

1. Поставить начальную точку чтения на самый правый символ слова.
2. Считать символ.
3. Записать его в ячейку памяти под текущим символом.
4. Сдвинуть позицию чтения на одну ячейку влево.
5. Повторить шаги 2-4 до тех пор, пока не будет достигнут начало слова.
6. Прочитать символ в начальной позиции.
7. Записать его в выходное слово α.
8. Сдвинуть позицию на одну ячейку вправо.
9. Повторить шаги 6-8 до тех пор, пока не будет достигнут конец слова.
10. Остановиться.

Таким образом, данная машина Тьюринга будет преобразовывать слова X1X2...Xn в алфавите {а, b} в слово α: XnXn-1..X1.
Похожие вопросы