Пост–машина Тьюринга

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article contains instructions, advice, or how-to content. Please help rewrite the content so that it is more encyclopedic or move it to Wikiversity, Wikibooks, or Wikivoyage. (August 2020) This article is written like a research paper or scientific journal. Please help improve the article by rewriting it in encyclopedic style and simplify overly technical phrases. (August 2020) (Learn how and when to remove this message) This article may need to be rewritten to comply with Wikipedia's quality standards. You can help. The talk page may contain suggestions. (August 2020) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Post–Turing machine" – news · newspapers · books · scholar · JSTOR (August 2020) (Learn how and when to remove this message) (Learn how and when to remove this message)

Пост -Тьюринговая машина ^[1] — это «программная формулировка» типа машины Тьюринга , включающая вариант эквивалентной Тьюрингу модели вычислений Эмиля Поста . Модель Поста и модель Тьюринга, хотя и очень похожи друг на друга, были разработаны независимо. Статья Тьюринга была получена для публикации в мае 1936 года, а затем в октябре последовала работа Поста. Пост-Тьюринговая машина использует двоичный алфавит , бесконечную последовательность двоичных ячеек хранения и примитивный язык программирования с инструкциями для двунаправленного перемещения между ячейками хранения и изменения их содержимого по одной за раз. Названия «Пост-Тьюринговая программа» и «Пост-Тьюринговая машина» использовались Мартином Дэвисом в 1973–1974 годах (Дэвис 1973, стр. 69 и далее). Позже, в 1980 году, Дэвис использовал название «Программа Тьюринга–Поста» (Дэвис, в Steen, стр. 241).

В своей статье 1936 года «Конечные комбинаторные процессы — Формулировка 1» Эмиль Пост описал модель, которая, по его предположению, « логически эквивалентна рекурсивности ».

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

Модель Поста использует « символическое пространство», состоящее из «двусторонней бесконечной последовательности пространств или ящиков», каждый из которых может находиться в одном из двух возможных состояний, а именно «отмечен» (например, одним вертикальным штрихом) и «неотмечен» (пустой). Первоначально конечное число ящиков отмечено, остальные неотмечены. Затем «работник» должен перемещаться между ящиками, находясь и работая только в одном ящике за раз, в соответствии с фиксированным конечным «набором указаний» ( инструкций ), которые пронумерованы в порядке (1,2,3,..., n ). Начиная с ящика, «выделенного в качестве отправной точки», рабочий должен следовать набору инструкций по одной за раз, начиная с инструкции 1.

Рабочий может выполнять пять различных примитивных операций:

(a) Отметить поле, в котором он находится, если оно пустое

(б) Стирание отметки в поле, в котором она находится, если она отмечена

(c) Переходим к полю справа

(d) Переходим к полю слева

(e) Определение того, маркирована ли коробка, в которой она находится, или нет.

Тогда i ^-е «указание» (инструкция), даваемое работнику, должно иметь одну из следующих форм:

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

1. замена бесконечности ящиков конечным расширяемым символьным пространством, «расширяя примитивные операции, чтобы обеспечить необходимое расширение заданного конечного символьного пространства по мере выполнения процесса»,
2. использование алфавита, состоящего более чем из двух символов, «имеющего более одного способа обозначить поле»,
3. введение конечного числа «физических объектов, служащих указателями, которые работник может идентифицировать и перемещать из коробки в коробку».

Как кратко упоминается в статье « Машина Тьюринга» , Пост в своей работе 1947 года ( «Рекурсивная неразрешимость проблемы Туэ ») разбил тьюринговские 5-кортежи на 4-кортежи:

«Наши четверки являются пятерками в развитии Тьюринга. То есть, там, где наша стандартная инструкция заказывает либо печать (надпечатку) , либо движение, влево или вправо, стандартная инструкция Тьюринга всегда заказывает печать и движение, вправо, влево или ничего» (сноска 12, Undecidable , стр. 300)

Как и Тьюринг, он определил стирание как печать символа «S0». И поэтому его модель допускала квадруплеты только трех типов (ср. Undecidable , стр. 294):

q _i S _j L q _l ,

q _i S _j R q _l ,

q _i S _j S _k q _l

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

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

написать 0

написать 1

двигаться влево

двигаться вправо

если сканирование 0, то переходим к инструкции i

если сканирование 1, то переходим к инструкции j

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

Мартин Дэвис был студентом бакалавриата Эмиля Поста. Вместе со Стивеном Клини он защитил докторскую диссертацию под руководством Алонзо Чёрча (Davis (2000) 1-я и 2-я сноски, стр. 188).

Следующая модель была представлена ​​им в серии лекций в Институте Куранта в Нью-Йоркском университете в 1973–1974 годах. Это модель, к которой Дэвис формально применил название «Пост-Тьюринговая машина» с ее «Пост-Тьюринговым языком». ^[2] Предполагается, что инструкции выполняются последовательно (Дэвис 1974, стр. 71):

Следующая модель появляется как эссе Что такое вычисление? в Стин страницы 241–267. По какой-то причине Дэвис переименовал свою модель в «машину Тьюринга–Пост» (с одним обратным скольжением на странице 256.)

В следующей модели Дэвис присваивает номер "1" "метке/косой черте" Поста и "0" пустому квадрату. Цитируя Дэвиса: "Теперь мы готовы представить язык программирования Тьюринга–Поста. В этом языке есть семь видов инструкций:

"ПЕЧАТЬ 1

"ПЕЧАТЬ 0

"ИДИТЕ НАПРАВО

"ИДИТЕ НАЛЕВО

«ПЕРЕЙТИ К ШАГУ i, ЕСЛИ 1 СКАНИРОВАН

«ПЕРЕЙТИ К ШАГУ i, ЕСЛИ СКАНИРОВАНО 0

"ОСТАНАВЛИВАТЬСЯ

«Программа Тьюринга–Поста представляет собой список инструкций, каждая из которых относится к одному из этих семи видов. Конечно, в реальной программе буква i на шаге пятого или шестого вида должна быть заменена определенным (целым положительным) числом» (Дэвис в книге Стина, стр. 247).

«Хотя представленная нами формулировка Тьюринга по духу ближе к первоначальной формулировке Эмиля Поста, именно анализ вычислений Тьюрингом сделал эту формулировку столь уместной. Этот язык сыграл фундаментальную роль в теоретической информатике». (Дэвис и др. (1994) стр. 129)

Эта модель допускает печать нескольких символов. Модель допускает B (пусто) вместо S ₀ . Лента бесконечна в обоих направлениях. Движется либо головка, либо лента, но их определения RIGHT и LEFT всегда указывают на один и тот же результат в любом случае (Тьюринг использовал то же соглашение).

PRINT σ ;Заменить отсканированный символ на σ

ЕСЛИ σ GOTO L ;ЕСЛИ сканируемый символ - σ ТО перейти к "первой" инструкции, помеченной L

ПРАВО ;Сканировать квадрат сразу справа от текущего сканируемого квадрата

LEFT ;Сканировать квадрат, расположенный непосредственно слева от текущего сканируемого квадрата.

Эта модель сводится к двоичным версиям {0, 1}, представленным выше, как показано здесь:

ПЕЧАТЬ 0 = СТЕРЕТЬ ;Заменить отсканированный символ на 0 = B = ПУСТО

ПЕЧАТЬ 1 ;Заменить отсканированный символ на 1

ЕСЛИ 0 GOTO L ;ЕСЛИ сканируемый символ равен 0 ТО перейти к «первой» инструкции, помеченной L

ЕСЛИ 1 GOTO L ;ЕСЛИ отсканированный символ равен 1 ТО перейти к «первой» инструкции, помеченной L

ПРАВО ;Сканировать квадрат сразу справа от текущего сканируемого квадрата

LEFT ;Сканировать квадрат, расположенный непосредственно слева от текущего сканируемого квадрата.

Следующий метод «редукции» (декомпозиции, атомизации) — от 2-символьных тьюринговых 5-кортежей к последовательности 2-символьных посттьюринговых инструкций — можно найти у Мински (1961). Он утверждает, что эта редукция к «программе ... последовательности инструкций » соответствует духу B-машины Хао Вана (курсив в оригинале, ср. Мински (1961) стр. 439).

(Сведение Мински к тому, что он называет «подпрограммой», приводит к 5, а не к 7 посттьюринговым инструкциям. Он не атомизировал Wi0: «Записать символ Si0; перейти в новое состояние Mi0» и Wi1: «Записать символ Si1; перейти в новое состояние Mi1». Следующий метод еще больше атомизирует Wi0 и Wi1; во всех остальных отношениях методы идентичны.)

Такое сведение тьюринговских 5-кортежей к посттьюринговским инструкциям может и не привести к «эффективной» посттьюринговской программе, но она будет верна исходной тьюринговской программе.

В следующем примере каждый кортеж Тьюринга из 5-ти элементов занятого бобра с 2 состояниями преобразуется в

всего 1 + 2 + 1 + 2 + 1 = 7 инструкций на одно состояние Тьюринга.

Например, состояние Тьюринга «A» занятого бобра с 2 состояниями, записанное в виде двух строк по 5 кортежей, выглядит следующим образом:

Таблица представляет собой всего одну «инструкцию» Тьюринга, но мы видим, что она состоит из двух строк по 5 кортежей, одна для случая «символ ленты под заголовком = 1», другая для случая «символ ленты под заголовком = 0». Тьюринг заметил ( Undecidable , стр. 119), что два левых столбца – «m-конфигурация» и «символ» – представляют текущую «конфигурацию» машины – ее состояние, включающее как Ленту, так и Таблицу в этот момент – а последние три столбца – ее последующее «поведение». Поскольку машина не может находиться в двух «состояниях» одновременно, она должна «перейти» либо к одной, либо к другой конфигурации:

После "ветви конфигурации" (J1 xxx) или (J0 xxx) машина следует одному из двух последующих "поведений". Мы перечисляем эти два поведения в одной строке и нумеруем (или маркируем) их последовательно (уникально). Под каждым переходом (ветвью, переходом) мы размещаем его "номер" перехода (адрес, местоположение):

Согласно соглашениям, принятым в эпоху пост-Тьюринга, каждая из инструкций «Печать», «Стирание», «Влево» и «Вправо» состоит из двух действий:

И в соответствии с соглашениями о машинах Пост-Тьюринга условные «прыжки» J0xxx, J1xxx состоят из двух действий:

И в соответствии с соглашениями о пост-Тьюринговых машинах безусловный «прыжок» Jxxx состоит из одного действия, или, если мы хотим упорядочить последовательность из 2 действий:

Какие и сколько переходов необходимо? Безусловный переход 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). Лента движется «влево» или «вправо» (т. е. «головка» неподвижна).

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

Инструкции для пост-тьюринговской версии 2-state busy beaver: обратите внимание, что все инструкции находятся на одной строке и в последовательности. Это существенное отклонение от "тьюринговской" версии и находится в том же формате, что и то, что называется "компьютерной программой":

В качестве альтернативы мы можем записать таблицу в виде строки. Использование «разделителей параметров» «:» и разделителей инструкций «,» является нашим выбором и не отображается в модели. Нет никаких соглашений (но см. Booth (1967) стр. 374, и Boolos and Jeffrey (1974, 1999) стр. 23), для некоторых полезных идей о том, как объединить соглашения диаграммы состояний с инструкциями – т. е. использовать стрелки для указания назначения переходов). В примере ниже инструкции последовательны , начиная с «1», а параметры/«операнды» считаются частью их инструкций/«кодов операций»:

J1:5, П, Р, J:8, П, Л, J:8, J1:12, П, Л, J1:1, П, Н, J:15, Н

• Стивен К. Клини , Введение в метаматематику, North-Holland Publishing Company , Нью-Йорк, 10-е издание 1991 г., впервые опубликовано в 1952 г. Глава XIII представляет собой превосходное описание машин Тьюринга; Клини использует в своем описании модель, подобную модели Поста, и признает, что модель Тьюринга может быть еще более атомизирована, см. сноску 1.
• Мартин Дэвис , редактор: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , Raven Press, Нью-Йорк, 1965. Среди статей — статьи Гёделя , Чёрча , Россера , Клини и Поста.
• Мартин Дэвис , «Что такое вычисление», в Mathematics Today , Линн Артур Стин, Vintage Books (Random House), 1980. Замечательная небольшая статья, возможно, лучшая из когда-либо написанных о машинах Тьюринга. Дэвис сводит машину Тьюринга к гораздо более простой модели, основанной на модели вычисления Поста. Включает краткую биографию Эмиля Поста.
• Мартин Дэвис , Вычислимость: с примечаниями Барри Джейкобса , Институт математических наук Куранта, Нью-Йоркский университет, 1974.
• Мартин Дэвис , Рон Сигал, Элейн Дж. Вейукер , (1994) Вычислимость, сложность и языки: основы теоретической информатики – 2-е издание , Academic Press: Harcourt, Brace & Company, Сан-Диего, 1994 ISBN  0-12-206382-1 (первое издание, 1983).
• Фред Хенни, Введение в вычислимость , Эддисон–Уэсли, 1977.
• Марвин Мински , (1961), Рекурсивная неразрешимость проблемы Поста «Тэг» и другие темы теории машин Тьюринга , Annals of Mathematics, т. 74, № 3, ноябрь 1961 г.
• Роджер Пенроуз , Новый разум императора: о компьютерах, разуме и законах физики , Oxford University Press, Оксфорд, Англия, 1990 (с исправлениями). См. главу 2, «Алгоритмы и машины Тьюринга». Излишне сложное изложение (см. статью Дэвиса для лучшей модели), но полное изложение машин Тьюринга и проблемы остановки , а также лямбда-исчисления Чёрча .
• Хао Ван (1957): «Вариант теории вычислительных машин Тьюринга», Журнал Ассоциации вычислительной техники (JACM) 4, 63–92.