Машина Тьюринга
жүктеу/скачать 17.58 Kb.
|
- Бұл бет үшін навигация:
- 5.1. Машина Тьюринга, работающая на полубесконечной ленте
- 5.2. Двумерные машины Тьюринга
5. Варианты машины ТьюрингаМодель машины Тьюринга допускает расширения. Можно рассматривать машины Тьюринга с произвольным числом лент и многомерными лентами с различными ограничениями. Однако все эти машины являются полными по Тьюрингу и моделируются обычной машиной Тьюринга. 5.1. Машина Тьюринга, работающая на полубесконечной лентеВ качестве примера такого сведения рассмотрим следующую теорему: Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте. Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте: Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ: Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны: Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. Очевидно, что слева от ограничивающих маркеров «*» лента в эквивалентной машине Тьюринга не используется. 5.2. Двумерные машины ТьюрингаМуравей Лэнгтона Другие абстрактные исполнители и формальные системы вычисленийНормальный алгоритм Маркова (продукционное программирование) Машина Поста (автоматное программирование) Рекурсивная функция (теория вычислимости) Лямбда-исчисление (функциональное программирование) Brainfuck (императивное программирование) жүктеу/скачать 17.58 Kb. Достарыңызбен бөлісу:
|