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

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

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

Первые работы по уточнению понятия алгоритм появились в 1936 – 1937 годах. Это были работы Тьюринга, Поста, Маркова, Чёрча. Было предложено несколько определений понятия алгоритм. Впоследствии было показано, что все они равносильны.

Одной из первых и весьма удачных попыток дать точный математический эквивалент интуитивного представления об алгоритме было введение понятия машины Тьюринга в 1937 году, за 9 лет до появления первой ЭВМ.

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

Машина Тьюринга состоит из ленты и управляющего устройства со считывающей и записывающей головки (каретки) (рис. 5.1).

Рис. 5.1

Лента жестко закреплена слева и бесконечна справа. Иногда считают, что лента не ограничена справа и слева. Лента разделена на ячейки, которые нумеруются натуральными числами 1, 2, ….

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

A = { a ₀, a ₁,... a_n }. (5.1)

Один из символов (пробел) соответствует незаполненной, пустой ячейке.

Головка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, то стоит против некоторой ячейки ленты; говорят, что головка обозревает эту ячейку.

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

Управляющее устройство может находиться в одном из множества дискретных состояний:

Q = { q ₀, q ₁,... q_m }. (5.2)

Множество Q называется внутренним алфавитом машины Тьюринга или алфавитом внутренних состояний.

Словом называется последовательность W = a_{i 1}, a_{i 2}, …, a_is символов, записанных в ячейках ленты, где a_{i 1} – символ, находящийся в самой левой непустой ячейке, а a_is – символ, находящийся в самой правой непустой ячейке. Количество символов s в слове называется длиной слова.

Пусть в некоторый момент времени t на ленте записано слово W, управляющее устройство находится в состоянии q_i, а каретка – напротив символа a_im слова W. Конфигурацией машины в момент времени t называется последовательность K = a_{i 1}, …, a_{i ( m – 1)}, q_i, a_im …, a_is. Конфигурации в начале и в конце работы называют соответственно начальной и заключительной.

Пример 5.4.

Пусть на ленте записано слово abcde, управляющее устройство находится в состоянии q_i и каретка стоит против символа d. Конфигурация в этом случае запишется так:

abcq_ide.

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

Если управляющее устройство в некоторый момент времени находится в состоянии q_i, обозревается символ a_j, в следующий момент времени записывается символ a_r, управляющее устройство переходит в состояние q_k, и каретка сдвигается, то говорят, что машина выполняет команду

a_jq_i ® a_rSq_k, (5.3)

где S – сдвиг, S = L, если сдвиг влево, S = R, если сдвиг вправо, S = C, если каретка остается на месте.

Совокупность всех команд, которые может выполнить машина, называется ее программой. Условие однозначности требует, чтобы для любого j и любого i имеется только одна команда вида (5.3). Каждая машина Тьюринга полностью определяется своим алфавитом, внутренними состояниями и программой.

Итак, машина Тьюринга есть совокупность

M = < A, Q, P >, (5.4)

где A – внешний алфавит (5.1), Q – алфавит внутренних состояний (5.2), P – программа (5.3).

Пример 5.5.

Машина с внешним алфавитом A = {1, a }, алфавитом внутренних состояний Q = { q ₁, q ₂} и программой

1 q ₁®1 Rq ₁,

aq ₁®1 R q ₁,

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

Порядок работы машины Тьюринга часто задается в виде таблицы.

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

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

Формат команды: aKq, где:

a – новое содержание текущей ячейки (новый символ внешнего алфавита, который заносится в текущую ячейку);

K – команда лентопротяжного механизма машины Тьюринга (влево, вправо, стоп);

q – новое внутренне состояние машины Тьюринга.

Работа машины на основании заданной программы происходит следующим образом.

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

Тогда машина переходит к выполнению команды a_jKq_i в ячейке, на пересечении столбца q_i и строки a_j:

1) в текущую ячейку ленты заносится новый символ a_j (возможно, тот же самый).

2) происходит сдвиг головки влево (K = влево), или сдвиг головки вправо (K = вправо), или головка остается на месте, т. е. происходит остановка машины (K = стоп).

3) машины переходит в новое внутреннее состояние q_i.

Возможные случаи останова машины Тьюринга:

1) в ходе выполнения программы машина дойдет до выполнения команды остановки; программа в этом случае считается выполненной, машина останавливается – происходит результативная остановка.

2) машина никогда не останавливается, происходит зацикливание.

Пример 5.6.

Пусть внешний алфавит A = {0, 1, 2}, а множество внутренних состояний состоит лишь из одного состояния Q = { q ₀}. Необходимо построить машину Тьюринга, которая в произвольной записи, начиная из любой ячейки, двигаясь вправо, находит первый нуль и останавливается. Такая машина может быть задана таблицей 5.1.

Табл. 5.1

Действительно, пусть, например, вначале машина находится в состоянии

Рис. 5.2

Головка обозревает символ 1. В соответствии с табл. 5.2 выполняется команда 1 Rq ₀, т. е. в обозреваемую ячейку записывается тот же самый символ 1 и головка смещается вправо (рис 5.3).

Рис. 5.3

Теперь головка снова обозревает символ 1 и в соответствии с табл. 5.2 выполняется команда 1 Rq ₀, т. е. т. е. в обозреваемую ячейку записывается тот же самый символ 1 и головка смещается вправо (рис 5.4).

Рис. 5.4

Теперь головка обозревает символ 2 и в соответствии с табл. 5.2 выполняется команда 2 Rq ₀, т. е. т. е. в обозреваемую ячейку записывается тот же самый символ 2 и головка смещается вправо (рис 5.5).

Рис. 5.5

Теперь головка обозревает символ 0 и в соответствии с табл. 5.2 выполняется команда 0 Cq ₀ т. е. в обозреваемую ячейку записывается тот же самый символ 0 и машина останавливается.

Пример 5.7.

Построим машину Тьюринга, которая слово Ø(АÚ B) преобразует в слово ØА&Ø B, а слово Ø(А& B) преобразует в слово ØА ÚØ B, что соответствует законам де Моргана. Такая машина может быть задана таблицей 5.2.

Внешний алфавит A = {Ø, А, B, Ú, &, (,), _} (символ _ соответствует пустой ячейке), а множество внутренних состояний состоит лишь из одного состояния Q = { q ₀}.

Табл. 5.2

Данные машины Тьюринга – это слова во внешнем алфавите ленты. На ленте записывается и исходные данные и конечный результат. На ленте могут быть записаны слова, а также последовательности слов. В последнем случае между словами ставится специальный символ-разделитель, им может быть пробел или символ *. Натуральное число a представляется словом 1…1= 1 ^a, состоящим из a единиц. Например, числу 3 соответствует слово 111.

Пример 5.8.

Построим машину Тьюринга, которая производит сложение двух натуральных чисел a и b. Сложить два числа a и b – это значит слово 1 ^a * 1 ^b преобразовать в слово 1 ^{a + b}. Это можно сделать, удалив в записи a * b символ разделителя * и сдвинув первое слагаемое ко второму. Такая машина может быть задана таблицей 5.3. Внешний алфавит A = {1, *, _}, где * – символ разделителя, а _ – символ пустой ячейки (пробел). Множество внутренних состояний состоит из трех состояний Q = { q ₀, q ₁, q ₂}.

Табл. 5.3

Начальное и конечное состояния ленты для случая a = 2, b = 3 представлено на рис. 5.6 a) и b)

a)

b)

Рис. 5.6