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

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

Структура и описание машины Тьюринга
Машина Тьюринга состоит из:
бесконечной ленты, разделенной на ячейки;
каретки (читающей и записывающей головки);
программируемого автомата (программа в виде таблицы).
Автомат каждый раз “видит” только одну ячейку. В зависимости от того, какую букву он видит, а также в зависимости от своего состояния q автомат может выполнять следующие действия:
записать новую букву в обозреваемую ячейку;
выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным;
перейти в новое состояние.

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

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

Виды команд машины Тьюринга
Написать новую букву в обозреваемую ячейку
Выполнить сдвиг по ленте на одну ячейку
вправо/влево или остаться на месте (П, Л, Н)
Перейти в новое состояние.
Указание о смене символа
Указание о сдвиге каретки
Указание о смене внутреннего состояния

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

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

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

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

К началу работы машины на ленту подается исходный набор данных в виде слова α
Описание работы машины Тьюринга
Будем говорить, что непустое слово α в алфавите А\{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

Ситуации неприменимости машины Тьюринга
Считается, что машина Тьюринга неприменима к данному входному слову, если в программе нет клеток останова или машина в процессе работы на них не попадает.
Например:
Машина Тьюринга применима к данному входному слову, если, начав работу над этим входным словом, она рано или поздно дойдёт до одной из клеток останова. Как изменилась программа в примере?

Пример машин Тьюринга
Требуется построить машину Тьюринга для решения следующей задачи: во входном слове все буквы «а» заменить на буквы «б» и наоборот.
у
→
у
б
→
а
а
→
б
р
→
р
у
б
а
р
а
б
а
→
б
б
→
а
а
б
б
а

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

Реализуйте предложенный алгоритм
На ленте машины Тьюринга содержится последовательность символов «+». Машина Тьюринга каждый второй символ «+» заменяет на «–». Замена начинается с правого конца последовательности. Автомат в состоянии q1 обозревает один из символов указанной последовательности.
q1 – машина ищет правый конец числа;
q2 – пропускает знак «+», при достижении конца последовательности – останов;
q3 – знак «+» заменяет на «–».

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

Решение

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

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

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

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

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

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

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