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

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

Устройство машины Тьюринга

В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство (также называется головкой записи-чтения (ГЗЧ)), способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.

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

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

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

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

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q_ia_j→q_i1a_j1d_k (если головка находится в состоянии q_i, а в обозреваемой ячейке записана буква a_j, то головка переходит в состояние q_i1, в ячейку вместо a_j записывается a_j1, головка делает движение d_k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <q_i, a_j> имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Пример машины Тьюринга

Приведём пример МТ для умножения чисел в унарной системе счисления. Запись правила «q_ia_j→q_i1a_j1R/L/N» следует понимать так: q_i — состояние при котором выполняется это правило, a_j — данные в ячейке, в которой находится головка, q_i1 — состояние в которое нужно перейти, a_j1 — что нужно записать в ячейку, R/L/N — команда на перемещение.

Машина работает по следующему набору правил:

Описание состояний:

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

Начало. Находимся в состоянии q₀, ввели в машину данные: *111x11=*, головка машины располагается на первом символе *.

1-й шаг. Смотрим по таблице правил что будет делать машина, находясь в состоянии q₀ и над символом "*". Это правило из 1-го столбца 5-й строки - q₀*→q₀*R. Это значит, что мы переходим в состояние q₀ (т.е. не меняем его), символ станет "*" (т.е. не изменится) и смещаемся по введённому нами тексту "*111x11=*" вправо на одну позицию (R), т.е. на 1-й символ 1. В свою очередь, состояние q₀1 (1-й столбец 1-я строка) обрабатывается правилом q₀1→q₀1R. Т.е. снова происходит просто переход вправо на 1 позицию. Так происходит, пока мы не станем на символ "х". И так далее: берём состояние (индекс при q), берём символ, на котором стоим (подчёркнутый символ), соединяем их и смотрим обработку полученной комбинации по таблице правил.

Простыми словами, алгоритм умножения следующий: помечаем 1-ю единицу 2-го множителя, заменяя её на букву "а", и переносим весь 1-й множитель за знак равенства. Перенос производится путём поочерёдной замены единиц 1-го множителя на "а" и дописывания такого же количества единиц в конце строки (слева от крайнего правого "*"). Затем меняем все "а" до знака умножения "х" обратно на единицы. И цикл повторяется. Действительно, ведь A умножить на В можно представить как А+А+А В раз. Помечаем теперь 2-ю единицу 2-го множителя буквой "а" и снова переносим единицы. Когда до знака "=" не окажется единиц - значит умножение завершено.