Определение машины Тьюринга

Машина Тьюринга – абстрактный исполнитель, осуществляющий алгоритмический процесс
Это математический объект, а не физическая машина
Предложена Аланом Тьюрингом в 1936 году

1) Внешний алфавит
А = {a0, a1, …, an}
Элемент a0 называется пустой символ
В этом алфавите в виде слова кодируется исходный набор данных и результат работы алгоритма
Устройство машины Тьюринга

2) Внутренний алфавит
Q = {q0, q1, …, qm}, {П, Л, С}
В любой момент времени машина М находится в одном из состояний q0, q1, …, qm
При этом: q1 - начальное состояние
q0 - заключительное состояние
Символы {П, Л, С} – символы сдвига (вправо, влево, на месте)
Устройство машины Тьюринга

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

3) Внешняя память (лента)
Устройство машины Тьюринга
Пустая клетка содержит a0.
В каждый момент времени на ленте записано конечное число непустых букв
Лента является конечной, но дополняется в любой момент ячейками слева и справа для записи новых непустых символов.
Это соответствует принципу абстракции потенциальной осуществимости

4) Каретка (управляющая головка)
Каретка машины располагается над некоторой ячейкой ленты – воспринимает символ, записанный в ячейке
В одном такте работы каретка сдвигается на одну ячейку (вправо, влево) или остается на месте
Устройство машины Тьюринга

5) Функциональная схема (программа)
Программа машины состоит из команд:
Устройство машины Тьюринга
Для каждой пары (qi, aj) программа машины должна содержать одну команду (детерминированная машина Тьюринга)

Замечание
1) В недетерминированной машине может появиться несколько параллельных вычислительных процессов
2) Разные машины Тьюринга отличаются своими программами
Для каждого алгоритма создается своя машина Тьюринга, точнее ее программа

К началу работы машины на ленту подается исходный набор данных в виде слова α
Описание работы машины Тьюринга
Будем говорить, что непустое слово α в алфавите А\{a0} воспринимается машиной в стандартном положении, если:
- оно задано в последовательных ячейках ленты,
- все другие ячейки пусты,
- машина обозревает крайнюю правую ячейку из тех, в которых записано слово α

Описание работы машины Тьюринга
Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q1 (стоп-состоянии q0)

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

Описание работы машины Тьюринга
В соответствии с командой qiaj → qkal Х выполняются следующие действия:
1) Содержимое обозреваемой ячейки aj стирается и в нее записывается символ al (который может совпадать с aj)
2) Машина переходит в новое состояние qk (оно может совпадать с состоянием qi)
3) Каретка перемещается в соответствии с управляемым символом Х ∈ {П, Л, С}

При переходе машины в заключительное состояние q0 ее работа прекращается
На ленте записан результат работы алгоритма – слово β в алфавите А\{a0}
Описание работы машины Тьюринга

Машинным словом (конфигурацией) машины Тьюринга называется слово вида α1qkal α2, где α1 и α2 - слова в алфавите А.

Конфигурация α1qkal α2 интерпретируется следующим образом:
- машина находится в состоянии qk
- каретка обозревает на ленте символ al
- α1 и α2 – это содержимое ленты до и после символа al

Пример
Дана машина Тьюринга с внешним алфавитом А = {a0, 1, * }, алфавитом внутренних состояний Q = {q0, q1, q2, q3}, и следующей функциональной схемой:
Применить машину Тьюринга к слову α=11*1, начиная со стандартного начального положения

Решение

Решение
1) Заменяем содержимое обозреваемой ячейки 1 на а0

Решение
2) Машина переходит в новое состояние q2

Решение
3) Каретка перемещается влево

Решение
Полное подробное решение

Решение
Полное подробное решение

Решение
Полное подробное решение

Решение
Решение, записанное с помощью конфигураций (в строчку)

α = 1*11
Ответ: β = 111

Литература
Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, 2008. - 448 с.
Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. – СПб.: Лань, 1999. - 288 с.
Ильиных А.П. Теория алгоритмов. Учебное пособие. – Екатеринбург, 2006. - 149 с.