Машина Тьюринга – это система, работающая в дискретные моменты времени и состоящая из следующих частей:
конечная лента, разбитая на конечное число ячеек. В каждый момент времени в ячейках записаны буквы из некоторого алфавита (где , ), называемого внешним алфавитом машины. Ячейка, в которой записан символ , называется пустой. Если в какой–то момент времени лента имеет ячеек, то состояние ленты полностью описывается словом , где – состояние первой (слева) ячейки, – состояние второй ячейки и т.д.
Управляющая головка, представляющая собой устройство, которое может перемещаться вдоль ленты так, что в каждый рассматриваемый момент времени оно находится напротив определенной ячейки и имеет некоторое состояние из конечного множества внутренних состояний , . Состояние называется заключительным и означает завершение работы машины. Состояние называется начальным и означает начало работы машины.
Программа Π, т.е. совокупность выражений (где ), называемых командами, каждое из которых имеет один из следующих видов:
сдвиг головки, находящейся в состоянии напротив ячейки с буквой , на одну ячейку влево с заменой состояния на ;
сдвиг головки, находящейся в состоянии напротив ячейки с буквой , на одну ячейку вправо с заменой состояния на ;
замена буквы в текущей ячейке на букву , а также замена состояния головки на состояние
Замечание 1.1) Команды не могут начинаться со слов .
2) .
Таким образом, машина Тьюринга – это пятерка .
Машинным словом называется слово , где – состояние ленты, – состояние головки, находящейся напротив ячейки с состоянием , занимающей то же положение среди других ячеек, что и буква в слове .
Пустое слово обозначим через .
Опишем преобразование машинного слова в машинное слово за один шаг работы машины :
если , то при и при ;
если , то при и при ;
если , то .
Машинное словополучается из машинного словас помощью машины Тьринга , если существует последовательность преобразований , , для которой , .
Пусть – множество натуральных чисел с нулем, .
Отображение , где , называется n–местной частичной функцией. Если , то частичная функция называется всюду определенной. Если , то частичная функция называется нигде не определенной.
Для любого числа через обозначим слово, состоящее из числа единиц: . Для любой –ки слово называется записью этой –ки.
Частичная функция , где , называется вычислимой по Тьюрингу, если существует машина Тьюринга такая, что
1) ;
2) машина применима к записnи n-ки ;
3) для и .
Пример 1.Построим машину Тьюринга , вычисляющую функцию . Пусть , где , , программа Π состоит из команд: