Машина Пост-Тьюринга [1] представляет собой «программную формулировку» типа машины Тьюринга , включающую вариант модели вычислений Эмиля Поста , эквивалентной Тьюрингу . Модель Поста и модель Тьюринга, хотя и очень похожи друг на друга, были разработаны независимо. Статья Тьюринга была получена для публикации в мае 1936 года, а в октябре последовала статья Поста. Машина Пост-Тьюринга использует двоичный алфавит , бесконечную последовательность двоичных ячеек памяти и примитивный язык программирования с инструкциями для двунаправленного перемещения между ячейками хранения и изменения их содержимого по одному. Названия «Программа Пост-Тьюринга» и «Машина Пост-Тьюринга» использовались Мартином Дэвисом в 1973–1974 годах (Davis 1973, стр. 69 и далее). Позже, в 1980 году, Дэвис использовал название «программа Тьюринга-Поста» (Дэвис, в Стин, стр. 241).
В своей статье 1936 года «Конечные комбинаторные процессы — формулировка 1» Эмиль Пост описал модель, которая, по его предположению, « логически эквивалентна рекурсивности ».
Модель вычислений Поста отличается от модели машины Тьюринга дальнейшей «атомизацией» действий, которые человеческий «компьютер» будет выполнять во время вычислений. [2]
Модель Поста использует « пространство символов », состоящее из «двусторонней бесконечной последовательности пробелов или блоков», причем каждый блок может находиться в любом из двух возможных состояний, а именно «отмечено» (например, одним вертикальным штрихом) и «неотмечено». " (пустой). Первоначально конечное число ячеек отмечено, остальные не отмечены. Затем «работник» должен перемещаться между ящиками, находясь и действуя только в одном ящике одновременно, в соответствии с фиксированным конечным «набором направлений» ( инструкциями ), которые пронумерованы по порядку (1,2,3, ..., н ). Начиная с коробки, «выделенной в качестве отправной точки», рабочий должен следовать набору инструкций по одной, начиная с инструкции 1.
Существует пять различных примитивных операций, которые может выполнять рабочий:
Тогда i- е «направление» (инструкция), данное работнику, должно иметь одну из следующих форм:
(Текст с отступом выше и курсив такие же, как в оригинале.) Пост отмечает, что эта формулировка находится «на начальных стадиях» разработки, и упоминает несколько возможностей для «большей гибкости» в ее окончательной «окончательной форме», включая
Как кратко упоминается в статье «Машина Тьюринга », Пост в своей статье 1947 года (« Рекурсивная неразрешимость проблемы Туэ ») раздробил 5-кортежи Тьюринга на 4-кортежи:
Как и Тьюринг, он определил стирание как печать символа «S0». Поэтому его модель допускала четверки только трех типов (ср. «Неразрешимые» , стр. 294):
В то время он все еще придерживался соглашения Тьюринга о конечном автомате - он не формализовал понятие предполагаемого последовательного выполнения шагов до тех пор, пока конкретная проверка символа не «разветвила» выполнение в другом месте.
Для еще большего сокращения – всего лишь до четырех инструкций – представленной здесь модели Ванга см. Wang B-machine .
Ван (1957, но представлен ACM в 1954 году) часто цитируется (ср. Мински (1967), стр. 200) как источник «формулировки программ» машин Тьюринга с двоичной лентой с использованием пронумерованных инструкций из набора
Любую машину Тьюринга с двоичной лентой можно легко преобразовать в эквивалентную «программу Ванга» с помощью приведенных выше инструкций.
Мартин Дэвис был студентом Эмиля Поста. Вместе со Стивеном Клин он защитил докторскую диссертацию. под церковью Алонсо (Дэвис (2000), 1-я и 2-я сноски, стр. 188).
Следующую модель он представил в серии лекций в Курантовском институте Нью-Йоркского университета в 1973–1974 годах. Это модель, к которой Дэвис формально применил название «машина Пост-Тьюринга» с ее «языком Пост-Тьюринга». [2] Предполагается, что инструкции выполняются последовательно (Дэвис 1974, стр. 71):
Следующая модель представлена в виде эссе Что такое вычисление? в Стине, страницы 241–267. По какой-то причине Дэвис переименовал свою модель в «машину Тьюринга-Поста» (с одним обратным скольжением на странице 256).
В следующей модели Дэвис присваивает цифры «1» «знаку/косой черте» Поста и «0» пустому квадрату. Цитируя Дэвиса: «Теперь мы готовы представить язык программирования Тьюринга-Поста. В этом языке существует семь видов инструкций:
«Программа Тьюринга-Поста представляет собой список инструкций, каждая из которых относится к одному из этих семи видов. Конечно, в реальной программе буква i на этапе пятого или шестого рода должна быть заменена на определенное (целое положительное) число». (Дэвис в Стин, стр. 247).
«Хотя представленная нами формулировка Тьюринга ближе по духу к той, которую первоначально дал Эмиль Пост, именно анализ Тьюринга вычислений сделал эту формулировку настолько подходящей. Этот язык сыграл фундаментальную роль в теоретической информатике». (Дэвис и др. (1994), стр. 129)
Эта модель позволяет печатать несколько символов. Модель допускает B (пусто) вместо S 0 . Лента бесконечна в обоих направлениях. Либо голова, либо лента движется, но их определения ПРАВО и ЛЕВО всегда определяют один и тот же результат в любом случае (Тьюринг использовал одно и то же соглашение).
Эта модель сводится к двоичным версиям { 0, 1 }, представленным выше, как показано здесь:
Следующий метод «редукции» (декомпозиции, атомизации) - от 2-символьных 5-кортежей Тьюринга к последовательности 2-символьных инструкций Пост-Тьюринга - можно найти у Мински (1961). Он утверждает, что это сведение к « программе ... последовательности инструкций » находится в духе Б-машины Хао Ванга (курсив в оригинале, ср. Мински (1961), стр. 439).
(Сведение Мински к тому, что он называет «подпрограммой», приводит к 5, а не к 7 инструкциям Пост-Тьюринга. Он не атомизировал Wi0: «Записать символ Si0; перейти в новое состояние Mi0» и Wi1: «Записать символ Si1; перейти в новое состояние Mi1». Следующий метод дополнительно атомизирует Wi0 и Wi1; во всем остальном методы идентичны.)
Это сокращение 5-кортежей Тьюринга до инструкций Пост-Тьюринга может не привести к созданию «эффективной» программы Пост-Тьюринга, но оно будет верным исходной программе Тьюринга.
В следующем примере каждая пятерка Тьюринга занятого бобра с двумя состояниями преобразуется в
всего 1 + 2 + 1 + 2 + 1 = 7 инструкций на одно состояние Тьюринга.
Например, состояние Тьюринга «А» занятого бобра с 2 состояниями, записанное в виде двух строк по 5 кортежей, выглядит так:
Таблица представляет собой всего лишь одну «инструкцию» Тьюринга, но мы видим, что она состоит из двух строк по 5 кортежей: одна для случая «символ ленты под заголовком = 1», другая для случая «символ ленты под заголовком = 0». ". Тьюринг заметил (« Undecidable» , стр. 119), что два левых столбца – «m-конфигурация» и «символ» – представляют текущую «конфигурацию» машины – ее состояние, включая Ленту и Таблицу в данный момент – а последние три столбца являются его последующее «поведение». Поскольку машина не может находиться в двух «состояниях» одновременно, она должна «разветвиться» либо в одну, либо в другую конфигурацию:
После «ветви конфигурации» (J1 xxx) или (J0 xxx) машина следует одному из двух последующих «поведений». Мы перечисляем эти два поведения в одной строке и нумеруем (или маркируем) их последовательно (уникально). Под каждым переходом (ветвью, переходом) мы помещаем его «номер» перехода (адрес, местоположение):
Согласно соглашениям машины Пост-Тьюринга каждая из инструкций «Печать», «Стереть», «Влево» и «Вправо» состоит из двух действий:
А согласно соглашениям машины Пост-Тьюринга условные «переходы» J0xxx, J1xxx состоят из двух действий:
И согласно соглашениям машины Пост-Тьюринга безусловный «прыжок» Jxxx состоит из одного действия, или, если мы хотим упорядочить последовательность из двух действий:
Какие и сколько прыжков необходимы? Безусловный переход J xxx — это просто J0 , за которым сразу следует J1 (или наоборот). Ван (1957) также показывает, что требуется только один условный переход, т.е. либо J0 xxx, либо J1 xxx. Однако из-за этого ограничения становится сложно писать инструкции для машины. Часто используются только два, т.е.
но использование всех трех { J0 xxx, J1 xxx, J xxx} исключает дополнительные инструкции. В примере Busy Beaver с 2 состояниями мы используем только { J1 xxx, J xxx }.
Миссия занятого бобра — напечатать как можно больше изображений, прежде чем остановиться. Инструкция «Печать» записывает 1, инструкция «Стереть» (не используется в этом примере) записывает 0 (т.е. это то же самое, что P0). Лента движется «влево» или «вправо» (т.е. «голова» неподвижна).
Таблица состояний для занятого бобра с двумя состояниями машины Тьюринга :
Инструкции для версии Пост-Тьюринга занятого бобра с двумя состояниями: обратите внимание, что все инструкции находятся в одной строке и в последовательности. Это существенное отличие от версии «Тьюринга» и имеет тот же формат, что и так называемая «компьютерная программа»:
Альтернативно мы могли бы записать таблицу в виде строки. Использование «разделителей параметров» «:» и разделителей инструкций «,» полностью является нашим выбором и не присутствует в модели. Здесь нет никаких соглашений (но см. Booth (1967), стр. 374 и Boolos and Jeffrey (1974, 1999), стр. 23), где описаны некоторые полезные идеи о том, как сочетать соглашения о диаграммах состояний с инструкциями – т.е. использовать стрелки для обозначения пункт назначения прыжков). В примере ниже инструкции идут последовательно , начиная с «1», а параметры/«операнды» считаются частью их инструкций/«кодов операций»: