Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Программа машины Тьюринга (Р) - совокупность всех команд, Программа представляется в виде таблицы и называется Тьюринговой функциональной схемой



  a0 a1 a2
q1 а0Пq1 a1Пq1 a2Лq2
q2 а1Пq2 a2Нq0 a0Нq0

Таким образом, машина Тьюринга может быть представлена в виде четверки:

(4.9)

Работа машины Тьюринга:

Информация, хранящаяся на ленте, является набором символов из внешнего алфавита. Начальное состояние управляющей головки характеризуется символом внутреннего алфавита . Работа машины складывается из тактов. В течение любого такта машина Тьюринга осуществляет следующие действия: машина Тьюринга находится во внутреннем состоянии , считывает входной символ и по таблице работы совершает операцию сдвига , переходя в состояние , при этом входное слово заменяется на :

Если в результате операции машина перейдет в состояние , то работа машины останавливается. Если состояние недостижимо, то значит по данному входному слову машина Тьюринга не достигает конечного состояния и алгоритма для данного входного слова не существует.

ПРИМЕР

Построить машину Тьюринга, которая будет стирать последнюю единицу в последовательности единиц.

Внешний алфавит - . Внутренний алфавит - , при этом состояние .сохраняется до тех пор, пока не будет найден конец последовательности единиц, состояние - стирание последней единицы. При этом следует заметить, что ситуация в работе машины Тьюринга невозможна, поэтому соответствующая клеточка доопределена произвольно, например . Начальное состояние на начале последовательности единиц. Рабочая программа машины Тьюринга имеет вид:

 

Проверим работоспособность машины Тьюринга:

1.

2.

3.

4.

5.

Тезис А. Черча. Если функция выполнима, то она всегда может быть представлена в виде машины Тьюринга.





Дата публикования: 2014-11-03; Прочитано: 315 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.008 с)...