a0 | a1 | a2 | |
q1 | а0Пq1 | a1Пq1 | a2Лq2 |
q2 | а1Пq2 | a2Нq0 | a0Нq0 |
Таким образом, машина Тьюринга может быть представлена в виде четверки:
(4.9)
Работа машины Тьюринга:
Информация, хранящаяся на ленте, является набором символов из внешнего алфавита. Начальное состояние управляющей головки характеризуется символом внутреннего алфавита . Работа машины складывается из тактов. В течение любого такта машина Тьюринга осуществляет следующие действия: машина Тьюринга находится во внутреннем состоянии , считывает входной символ и по таблице работы совершает операцию сдвига , переходя в состояние , при этом входное слово заменяется на :
Если в результате операции машина перейдет в состояние , то работа машины останавливается. Если состояние недостижимо, то значит по данному входному слову машина Тьюринга не достигает конечного состояния и алгоритма для данного входного слова не существует.
ПРИМЕР
Построить машину Тьюринга, которая будет стирать последнюю единицу в последовательности единиц.
Внешний алфавит - . Внутренний алфавит -, при этом состояние .сохраняется до тех пор, пока не будет найден конец последовательности единиц, состояние - стирание последней единицы. При этом следует заметить, что ситуация в работе машины Тьюринга невозможна, поэтому соответствующая клеточка доопределена произвольно, например . Начальное состояние на начале последовательности единиц. Рабочая программа машины Тьюринга имеет вид:
Проверим работоспособность машины Тьюринга:
1.
2.
3.
4.
5.
Тезис А. Черча. Если функция выполнима, то она всегда может быть представлена в виде машины Тьюринга.