Модель машины Тьюринга

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

Модель машины Тьюринга

Детерминированная машина Тьюринга имеет функцию перехода, которая по комбинации текущего состояния и символа на ленте определяет три вещи:

• символ, который будет записан на ленте;
• направление смещения головки по ленте;
• новое состояние конечного автомата.

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

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

1. Можно считать, что НМТ – «чрезвычайно удачлива»; то есть всегда выбирает переход, который в конечном счете приводит к допускающему состоянию, если такой переход вообще есть.

2. Можно представить, что в случае неоднозначности перехода (текущая комбинация состояния и символа на ленте допускает несколько переходов) НМТ делится на копии, каждая из которых следует за одним из возможных переходов.

В отличие от ДМТ, которая имеет единственный «путь вычислений», НМТ имеет «дерево вычислений» (в общем случае — экспоненциальное число путей). Говорят, что НМТ допускает входные данные, если какая-нибудь ветвь этого дерева останавливается в допускающем состоянии, иначе НМТ входные данные не допускает. 

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

Элементы модели и их характеристики

В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки[2][3], и управляющее устройство (также называется головкой записи-чтения (ГЗЧ)), способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано. Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные. Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма. Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

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

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

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

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

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

Основные отличия машины Тьюринга от человека-вычислителя и компьютера

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

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

2. Машина Тьюринга снабжена потенциально бесконечной памятью. Что значит «потенциально бесконечная память»? Это значит, что хотя в каждый момент ее память хранит лишь конечное количество информации, однако для этого количества информации нет никакой верхней границы. Вообразим такую память машины Тьюринга в виде ленты, разделенной на клеточки -- ячейки памяти, -- которая может быть продолжена вправо сколько угодно.

• Пратт Т., Зелковиц М. Языки программирования: разработка и реализация / Под общей ред. А. Матросова. — СПб.: Питер, 2002. — 688 с.
• Карпов Ю. Г. Теория и технология программирования. Основы построения трансляторов. — СПб.: БХВ-Петербург, 2005. — 272 с.
• Овсянников А. В. Алгоритмы и структуры данных : учебно-методический комплекс для специальности 1-31 03 07 «Прикладная информатика (по направлениям)». Ч. 1 / А. В. Овсянников, Ю. А. Пикман ; БГУ, Фак. социокультурных коммуникаций, Каф. информационных технологий. – Минск : БГУ, 2015. – 124 с.