МАШИНА ТЬЮРИНГА

Автоматизм, необходимый при реализации алгоритма, естественно привел к мысли о передаче функции человека, реализующего алгоритм, машине. Эту идею предложили в 30-е годы прошлого века почти одновременно американский математик Э. Пост и английский математик А. Тьюринг. Рассмотрим один из вариантов, который носит название машина Тьюринга (МТ).

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

1) внешний алфавит, т. е. конечное множество символов A = {a0, a1, … an}. В этом алфавите в виде слова кодируется та информация, которая подается в машину. Машина перерабатывает эту информацию в новое слово; 2) внутренний алфавит машины состоит из символов: { q0, q1 … qm, R, L, C }. Символы q0, q1, … qm – конечное число состояний машины, т. е.

возможных реакций машины (МТ) на любой символ внешнего алфавита. Два состояния имеют особое назначение: q1 – начальное состояние машины, и q0 – заключительное состояние (стоп-состояние), т. е. реакция машины q0 – это остановка. Символы R, L, C – это символы сдвига на 1 ячейку соответственно вправо, влево, на месте;

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

a0 (часто просто 0);

4) управляющая (считывающая) головка. Она передвигается вдоль ленты и может останавливаться против какой-то клетки, т. е. «считывает» символ в этой клетке. За один шаг головка может сдвинуться лишь на одну ячейку вправо или влево или остаться на месте, что обозначается символами R, L, C соответственно.

К началу работы машины на ленту подается начальная информация и управляющая головка, как правило, находится у крайнего правого (или левого) символа всех непустых клеток с указанием начального состояния q1. Это будет так называемая начальная конфигурация.

Работа МТ складывается из тактов (шагов). За один шаг машина может в данной ячейке:

–написать один символ или оставить прежний;

–перейти в новое состояние или остаться в прежнем;

–сдвинуться по ленте на одну клетку вправо или влево или остаться на месте.

10

В зависимости от того, какая была подана начальная информация A, т. е. какая была начальная конфигурация, возможны 2 случая.

1. МТ начинает работу (не начать не может, так как при правильном задании должна быть реакция МТ на любой символ) и после конечного числа шагов останавливается в некоторой конфигурации, т. е. переходит в стоп-

состояние q0. При этом на ленте оказывается изображенной некоторая информация B. В этом случае говорят, что МТ применима к информации A и перерабатывает ее в B, т. е. существует и работает алгоритм перевода A в B.

2. МТ не останавливается, т. е. не переходит в состояние q0, как говорят, «зацикливается». В таком случае говорят, что данная МТ не применима к информации A.

В каждый момент работы МТ конфигурация записывается следующим образом:

{a1, a2, …a … an}

q

Это означает, что до a1 и после an ячейки пустые, т. е. в них стоят a0, а в ячейках a1, . . ., an могут быть как нулевые, так и ненулевые символы внешнего алфавита.

При этом машина находится в состоянии qj.

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

aiqj -> ak(R, L, C )qs

Здесь 5 символов, 2 – из внешнего, 3 – из внутреннего алфавитов. Такой шаг означает, что символ ai в ячейке, возле которой стоит управляющая головка, заменяется на символ ak, МТ из состояния qj переходит в состояние qs и при этом головка или сдвигается на 1 клетку вправо (R) или влево (L) или остается на месте (C).

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

Рассмотрим в качестве примера тьюрингову схему.

11

Посмотрим, как по такой программе работает МТ. Пусть начальная конфигурация:

МТ останавливается, она переработала слово a2 a2 в слово a2 a2 a2. Пусть теперь начальная конфигурация:

Как видим, процесс, т. е. конфигурации, начали повторяться, т. е. МТ «зациклилась», следовательно, данная МТ не применима к начальной ин-

формации {a0 a1 a1 a2 a2 a0 }.

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

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

12

Понятия рекурсивного алгоритма (алгоритм – это процесс вычисления частично-рекурсивной функции) и машины Тьюринга (алгоритм – то, что может быть задано посредством МТ), а также другие известные пока определения алгоритма, такие как машина Поста, нормальные алгоритмы Маркова, нервные сети Неймана, равносильны.

Определение. Функция y = f(x1, x2, . . . xn) называется вычислимой по Тьюрингу, если существует МТ с алфавитом {0, 1}такая, что при начальной конфигурации, задающей в алфавите МТ значения x1, x2 . . . xn

({0 1 1 1 0 1 110 111 1 0}), МТ начинает работу и, если при таких значе-

ниях функция y определена, то МТ заканчивает работу в конфигурации, определяющей значение y:

({0 0 1 1111 0 0}).

Теорема. Функции, вычислимые по Тьюрингу, есть частично-рекур- сивные функции, и наоборот.

Докажем, что простейшие ПРФ O(x) = 0; S(x) = x + 1; Im (x1 ... xn) = xm есть функции, вычислимые по Тьюрингу.

1. O(x) ≡ 0 МТ{0, 1} для вычисления этой функции задается тьюринговой схемой с двумя состояниями {q0, q1}:

q1 0Cq0 0Lq1

2. S(x) = x + 1 МТ {0, 1} c состояниями {q0, q1} для этой функции задается Тьюринговой схемой:

q1 1Cq0 1Lq1

Посмотрим, как работает эта МТ: {0 0 1 1 0 0}

{0 0 1 1 0 0}

{0 0 1 1 0 0}

{0 0 1 1 0 0} stop

13

3. I1(x1 . . . xn) = x1; x1 ≠ 0

МТ {0, 1} с состояниями {q0, q1, q2, q3, q4, q5} задается тьюринговой схемой:

МТ остановилась в конфигурации, дающей значение x1.

14