Машина Тьюринга-Поста

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

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

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

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

3. Таблица переходов: описание поведения автомата в зависимости от состояния и считанного символа.

Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:

1. Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).

2. Перемещаться влево и вправо по ленте.

3. Менять свое внутреннее состояние.

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