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

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

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

ПРИМЕР

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

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

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

1.

2.

3.

4.

5.

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