Машина Тьюринга. Тезис Тьюринга.

Устройство машины Тьюринга включает в себя:

1. Внешний алфавит, то есть конечное множество символов . В этом алфавите в виде слова кодируется та информация, которая подаётся в машину. Машина перерабатывает информацию, поданную в виде слова, в новое слово.

2. Внутренний алфавит машины, состоящий из символов q₀, q₁, q₂, …, П, Л, Н. Символы q₀, q₁, q₂, …, q_m выражают конечное число состояний машины. Для каждой машины число состояний фиксировано. Два состояния имеют особое назначение: q₁ – начальное состояние машины, q₀ – заключительное состояние (стоп-состояние). Символы П, Л, Н – символы сдвига (вправо, влево, на месте).

3. Бесконечная в обе стороны лента (внешняя память машины). Она разбита на клетки. В каждую клетку может быть записана только одна буква. Пустая клетка обозначается символом a₀.

4. Управляющая головка. Она передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, то есть воспринимать символ. В одном такте работы машины управляющая головка может сдвигаться только на одну клетку (вправо, влево) или оставаться на месте.

Каждое сведение, хранящееся на ленте, изображается конечным набором символов (букв) внешнего алфавита, отличного от a₀. К началу работы машины на ленту подаётся начальное сведение (начальная информация). В этом случае управляющая головка может обозревать любую букву, записанную на ленте, например, крайнюю левую букву (q₁ – начальная конфигурация):

Говорят, что непустое слово α в алфавите A\{a₀}={a₁, a₂, …, a_n} воспринимается машиной в стандартном положении, если оно записано в последовательных клетках ленты, все другие клетки пусты, и машина обозревает крайнюю справа клетку из тех, в которых записано слово α.

Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q₁ (в состоянии q₀).

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

В каждом такте работы машины она действует по функциональной схеме, которая имеет вид:

.

Здесь a_i, a_ν – буквы внешнего алфавита; q_j, q_s – состояния машины; {П, Л, Н} – символы сдвига.

В зависимости от того, какая буква на ленте обозревается управляющей головкой (в нашей записи a_i) и в каком состоянии (в нашей записи q_j) находится машина, в данном такте вырабатывается команда, состоящая из трёх элементов:

1) буквы внешнего алфавита, на которую заменяется обозреваемая буква (a_ν);

2) адреса внешней памяти для следующего такта {П, Л, Н};

3) следующего состояния машины (q_s).

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

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

Рассмотрим теорему