Войти
A Машина Пост-Тьюринга - это "программная формулировка" типа машины Тьюринга, включающая вариант Эмиля Поста Эквивалент Тьюринга модель вычисления . Модель Поста и модель Тьюринга, хотя и очень похожи друг на друга, были разработаны независимо. Статья Тьюринга была получена для публикации в мае 1936 года, а в октябре - статья Поста.) Машина Пост-Тьюринга использует двоичный алфавит, бесконечную последовательность двоичных символов. хранилище местоположения и примитивный язык программирования с инструкциями для двунаправленного перемещения между ячейками хранилища и изменения их содержимого по одной за раз. Названия «программа Пост-Тьюринга» и «машина Пост-Тьюринга» использовались Мартином Дэвисом в 1973–1974 гг. (Davis 1973, p. 69ff). Позже, в 1980 году, Дэвис использовал название «программа Тьюринга – Поста» (Дэвис, в Steen, стр. 241).
В своей статье 1936 года «Конечные комбинаторные процессы - формулировка 1», Эмиль Пост описал модель, которая, по его предположениям, «логически эквивалентна рекурсивности ».
Модель вычислений Поста отличается от модели машины Тьюринга дальнейшей "атомизацией" действий, которые человеческий "компьютер" будет выполнять во время вычислений.
Модель Поста использует "символ пробел », состоящий из« двусторонней бесконечной последовательности пробелов или квадратов », каждый прямоугольник может находиться в одном из двух возможных состояний, а именно« отмечен »(как одиночный вертикальный штрих) и« немаркирован » "(пусто). Изначально конечно - многие поля отмечены, остальные не отмечены. Затем «рабочий» должен перемещаться между ящиками, находясь внутри и работая только в одном ящике за раз, в соответствии с фиксированным конечным «набором направлений» (инструкции ), которые нумеруются в порядке ( 1,2,3,..., п). Начиная с поля, «выделенного в качестве отправной точки», работник должен следовать набору инструкций по одной, начиная с инструкции 1.
В частности, «направление» (инструкция) i, данное для рабочий должен быть одной из следующих форм:
(Вышеупомянутый текст с отступом и курсивом такие же, как в оригинале.) Пост отмечает, что эта формулировка находится «на начальных стадиях» разработки, и упоминает несколько возможностей «большей гибкости» в ее окончательной «окончательной форме», включая
Как кратко упоминалось в статье Машина Тьюринга, Пост, в его статье 1947 года (Рекурсивная неразрешимость проблемы of Thue) раздробил 5-кортежи Тьюринга на 4-кортежи:
Как и Тьюринг, он определил стирание как печать символа« S0 ». Таким образом, его модель допускала четверные только трех типов (см.« Неразрешимый », стр. 294):
В это время он все еще придерживался соглашения о машине состояний Тьюринга - он не формализовал понятие предполагаемого последовательного выполнения шагов до тех пор, пока конкретный тест символа не «разветвил» выполнение в другом месте..
Для еще большего сокращения - всего до четырех инструкций - модели Ванга, представленной здесь, см. Ван Б-машина.
Ван (1957, но представленный ACM в 1954 г.) часто упоминается (см. Minsky (1967), стр. 200) как источник «программной формулировки» бинарных ленточных машин Тьюринга с использованием пронумерованных инструкций из набора
Любая машина Тьюринга с двоичной лентой легко конвертируется в эквивалентную «программу Ванга» с помощью приведенных выше инструкций.
Мартин Дэвис был студентом у Эмиля Поста. Вместе с Стивеном Клини он защитил докторскую диссертацию по программе Алонзо Черч (Дэвис (2000), 1-я и 2-я сноски, стр. 188).
Следующую модель он представил в серии лекций в Институте Куранта в Нью-Йоркском университете в 1973–1974 годах. Это модель, к которой Дэвис формально применил название «машина Пост-Тьюринга» с ее «языком Пост-Тьюринга». Предполагается, что инструкции выполняются последовательно (Davis 1974, стр. 71):
Следующая модель выглядит как эссе Что такое вычисление? в Стин, страницы 241–267. По какой-то причине Дэвис переименовал свою модель в «машину Тьюринга – Поста» (с одним сдвигом назад на странице 256.)
В следующей модели Дэвис присваивает цифры «1» «знаку / косой черте» Поста. и «0» на пустой квадрат. Процитируем Дэвиса: «Теперь мы готовы представить язык программирования Тьюринга – Поста. В этом языке есть семь видов инструкций:
" Тогда программа Тьюринга-Поста представляет собой список инструкций, каждая из которых относится к одному из этих семи типов. Конечно, в реальной программе буква i в шаге пятого или шестого рода должны быть заменены определенным (положительным целым) числом ». (Дэвис в Steen, стр. 247).
«Хотя формулировка Тьюринга, которую мы представили, ближе по духу к той, что была первоначально дана Эмилем Постом, она был проведенный Тьюрингом анализ вычислений, который сделал эту формулировку такой подходящей. Этот язык сыграл фундаментальную роль в теоретической информатике ». (Дэвис и др. (1994) стр. 129)
Эта модель позволяет печатать несколько символов. Модель позволяет использовать B (пусто) вместо S 0. Лента бесконечна в обоих направлениях. Либо голова, либо лента движется, но их определения ВПРАВО и ВЛЕВО всегда указывают один и тот же результат в любом случае (Тьюринг использовал одно и то же соглашение).
Эта модель сокращается до двоичных версий {0, 1}, представленных выше, как показано здесь:
Следующая «редукция» (разложение, атомизация) метод - от m 2-символьных 5-кортежей Тьюринга для последовательности 2-символьных инструкций Пост-Тьюринга - можно найти у Мински (1961). Он заявляет, что это сокращение до «программы... последовательности инструкций» находится в духе Хао Ванга B-машины (курсив в оригинале, ср. Minsky (1961)) с. 439).
(Сведение Мински к тому, что он называет «подпрограммой», приводит к 5, а не 7 инструкциям Пост-Тьюринга. Он не атомизировал Wi0: «Записать символ Si0; перейти в новое состояние Mi0», и Wi1 : «Записать символ Si1; перейти в новое состояние Mi1». Следующий метод дополнительно атомизирует Wi0 и Wi1; во всех остальных отношениях методы идентичны.)
Это сокращение 5-кортежей Тьюринга до инструкций Пост-Тьюринга может не привести к "эффективной" программе Пост-Тьюринга, но она будет верна исходной программе Тьюринга.
В следующем примере каждый 5-кортеж Тьюринга из 2-state busy beaver преобразуется в
, всего 1 + 2 + 1 + 2 + 1 = 7 инструкций на состояние Тьюринга.
Например, тьюринговое состояние «А» занятого бобра с двумя состояниями, записанное в виде двух строк по 5 кортежей, это:
| Начальная m-конфигурация (состояние Тьюринга) | Символ ленты | Операция печати | Движение ленты | Окончательная m-конфигурация (состояние Тьюринга) |
|---|---|---|---|---|
| A | 0 | P | R | B |
| A | 1 | P | L | B |
Таблица представляет только одну «инструкцию» Тьюринга, но мы видим, что он состоит из двух строк по 5 кортежей, одна для случая «символ ленты под заголовком = 1», другая для случая «символ ленты под заголовком = 0». Тьюринг заметил (Undecidable, p. 119), что два левых столбца - «m-конфигурация» и «символ» - представляют текущую «конфигурацию» машины - ее состояние, включая ленту и таблицу в этот момент, - и последние три столбца. являются его последующим «поведением». Поскольку машина не может находиться в двух «состояниях» одновременно, машина должна «перейти» либо к одной конфигурации, либо к другой:
| Исходная m-конфигурация и символ S | Операция печати | Движение ленты | Окончательная m-конфигурация |
|---|---|---|---|
| S = 0 -> | P -> | R -> | B |
| ->A< | |||
| S = 1 -> | P -> | L -> | B |
После «ветви конфигурации» (J1 xxx) или (J0 xxx) машина следует за одним из два последующих «поведения». Мы перечисляем эти два поведения в одной строке и пронумеровываем (или маркируем) их последовательно (однозначно). Под каждым переходом (переходом, переходом) мы помещаем его «номер» перехода (адрес, местоположение):
| Начальная m-конфигурация и символ S | Операция печати | Движение ленты | Окончательный случай m-конфигурации S = 0 | Операция печати | Движение ленты | Окончательный случай m-конфигурации S = 1 | |
|---|---|---|---|---|---|---|---|
| Если S = 0, то: | P | R | B | ||||
| --->A< | |||||||
| Если S = 1, то: | P | L | B | ||||
| инструкция № | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Инструкция Пост-Тьюринга | J1 | P | R | J | P | L | J |
| инструкция перехода № | 5 | B | B |
Пер. Согласно соглашениям машины Пост-Тьюринга каждая из инструкций «Печать», «Стирание», «Влево» и «Вправо» состоит из двух действий:
И согласно соглашениям машины Пост-Тьюринга условные "переходы" J0xxx, J1xxx состоят из двух действий:
И согласно соглашениям машины Пост-Тьюринга безусловный "джум p "Jxxx состоит из одного действия, или, если мы хотим упорядочить последовательность из двух действий:
Какие и сколько прыжков необходимы? Безусловный переход J xxx - это просто J0, за которым сразу следует J1 (или наоборот). Ван (1957) также показывает, что требуется только один условный переход, то есть либо J0 xxx, либо J1 xxx. Однако из-за этого ограничения на машине становится сложно писать инструкции. Часто используются только два, т.е.
но использование всех трех {J0 xxx, J1 xxx, J xxx} исключает лишние инструкции. В примере с 2 состояниями Busy Beaver мы используем только {J1 xxx, J xxx}.
Задача занятого бобра - напечатать как можно больше бобров перед остановкой. Команда «Печать» записывает 1, команда «Стереть» (не используется в этом примере) записывает 0 (т. Е. То же самое, что и P0). Лента движется «влево» или «вправо» (т.е. «голова» неподвижна).
Таблица состояний для машины Тьюринга с 2 состояниями занятый бобер :
| Символ ленты | Текущее состояние A | Текущее состояние B | ||||
|---|---|---|---|---|---|---|
| Символ записи | Переместить ленту | Следующее состояние | Записать символ | Переместить ленту | Следующее состояние | |
| 0 | 1 | R | B | 1 | L | A |
| 1 | 1 | L | B | 1 | N | H |
Инструкции для версии пост-Тьюринга для двухуровневой занятости бобер: обратите внимание, что все инструкции в одной строке и в последовательности. Это существенное отличие от версии «Тьюринга» и имеет тот же формат, что и так называемая «компьютерная программа»:
| Инструкция № | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Инструкция | J1 | P | R | J | P | L | J | J1 | P | L | J | P | N | J | H |
| Перейти к # | 5 | 8 | 8 | 12 | 1 | 15 | |||||||||
| Метка состояния Тьюринга | A | B | H |
В качестве альтернативы мы могли бы записать таблицу в виде строки. Использование «разделителей параметров» «:» и разделителей инструкций «,» является полностью нашим выбором и не используется в модели. Условий нет (но см. Бут (1967), стр. 374, и Булос и Джеффри (1974, 1999), стр. 23), где можно найти некоторые полезные идеи о том, как комбинировать условные обозначения диаграммы состояний с инструкциями, т. Е. Использовать стрелки для обозначения место назначения прыжков). В приведенном ниже примере инструкции идут последовательно, начиная с "1", а параметры / "операнды" считаются частью их инструкций / "кодов операций":
Диаграмма состояний занятого бобра с двумя состояниями (маленький рисунок, правый угол) преобразуется в эквивалентную машину Пост-Тьюринга с заменой 7 инструкций Пост-Тьюринга на каждое состояние «Тьюринга». Инструкция HALT добавляет 15-е состояние:
Показан "запуск" занятого бобра с двумя состояниями со всеми промежуточными этапами машины Пост-Тьюринга:
