Машины Тьюринга

 

Машина Тьюринга – это система, работающая в дискретные моменты времени и состоящая из следующих частей:

конечная лента, разбитая на конечное число ячеек. В каждый момент времени в ячейках записаны буквы из некоторого алфавита (где , ), называемого внешним алфавитом машины. Ячейка, в которой записан символ , называется пустой. Если в какой–то момент времени лента имеет ячеек, то состояние ленты полностью описывается словом , где ­– состояние первой (слева) ячейки, – состояние второй ячейки и т.д.

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

Программа Π, т.е. совокупность выражений (где ), называемых командами, каждое из которых имеет один из следующих видов:

сдвиг головки, находящейся в состоянии напротив ячейки с буквой , на одну ячейку влево с заменой состояния на ;

сдвиг головки, находящейся в состоянии напротив ячейки с буквой , на одну ячейку вправо с заменой состояния на ;

замена буквы в текущей ячейке на букву , а также замена состояния головки на состояние

Замечание 1. 1) Команды не могут начинаться со слов .

2) .

Таким образом, машина Тьюринга – это пятерка .

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

Пустое слово обозначим через .

Опишем преобразование машинного слова в машинное слово за один шаг работы машины :

если , то при и при ;

если , то при и при ;

если , то .

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

Пусть – множество натуральных чисел с нулем, .

Отображение , где , называется n–местной частичной функцией. Если , то частичная функция называется всюду определенной. Если , то частичная функция называется нигде не определенной.

Для любого числа через обозначим слово, состоящее из числа единиц: . Для любой –ки слово называется записью этой –ки.

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

1) ;

2) машина применима к запис n и n- ки ;

3) для и .

Пример 1. Построим машину Тьюринга , вычисляющую функцию . Пусть , где , , программа Π состоит из команд: