Пост-Тьюринговая машина
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
Машина Пост -Тьюринга [1] представляет собой «программную формулировку» типа машины Тьюринга , включающую вариант Эмиля Поста эквивалентной Тьюрингу, модели вычислений , . Модель Поста и модель Тьюринга, хотя и очень похожи друг на друга, были разработаны независимо. Статья Тьюринга была получена для публикации в мае 1936 года, а в октябре последовала статья Поста. Машина Пост-Тьюринга использует двоичный алфавит , бесконечную последовательность двоичных ячеек памяти и примитивный язык программирования с инструкциями для двунаправленного перемещения между ячейками хранения и изменения их содержимого по одному. Названия «Программа Пост-Тьюринга» и «Машина Пост-Тьюринга» использовались Мартином Дэвисом в 1973–1974 годах (Davis 1973, стр. 69 и далее). Позже, в 1980 году, Дэвис использовал название «программа Тьюринга – Поста» (Дэвис, в Стин, стр. 241).
1936: Почтовая модель
[ редактировать ]В своей статье 1936 года «Конечные комбинаторные процессы — формулировка 1» Эмиль Пост описал модель, которая, по его предположению, « эквивалентна рекурсивности логически ».
Модель вычислений Поста отличается от модели машины Тьюринга дальнейшей «атомизацией» действий, которые человеческий «компьютер» будет выполнять во время вычислений. [2]
Модель Поста использует « пространство символов », состоящее из «двусторонней бесконечной последовательности пробелов или блоков», причем каждый блок может находиться в одном из двух возможных состояний, а именно «отмечено» (например, одним вертикальным штрихом) и «неотмечено». " (пустой). Первоначально конечное число ячеек отмечено, остальные не отмечены. Затем «работник» должен перемещаться между ящиками, находясь и действуя только в одном ящике одновременно, в соответствии с фиксированным конечным «набором направлений» ( инструкциями ), которые пронумерованы по порядку (1,2,3, ..., н ). Начиная с коробки, «выделенной в качестве отправной точки», рабочий должен следовать набору инструкций по одной, начиная с инструкции 1.
Существует пять различных примитивных операций, которые может выполнять рабочий:
- (а) Отметьте ящик, в котором он находится, если он пуст.
- (b) Стирание отметки в ячейке, в которой она находится, если она помечена.
- (c) Переходим к ящику справа.
- (d) Переход к ящику слева от него.
- (e) Определение того, находится ли ящик, в котором он находится, отмечен или нет.
Тогда я й «Указание» (инструкция), данное работнику, должно иметь одну из следующих форм:
- Выполните операцию O i [ O i = (a), (b), (c) или (d)] , а затем следуйте направлению j i
- Выполните операцию (e) и в зависимости от ответа «да» или «нет» соответственно следуйте направлению j i ′ или j i ″.
- Останавливаться .
(Текст с отступом и курсивом выше такие же, как в оригинале.) Пост отмечает, что эта формулировка находится «на начальных стадиях» разработки, и упоминает несколько возможностей для «большей гибкости» в ее окончательной «окончательной форме», включая
- замена бесконечности ящиков конечным расширяемым пространством символов, «расширение примитивных операций, позволяющее обеспечить необходимое расширение данного конечного пространства символов по мере продолжения процесса»,
- использование алфавита, состоящего более чем из двух символов, «имея более одного способа отметить коробку»,
- введение конечного числа «физических объектов, которые будут служить указателями, которые работник может идентифицировать и перемещать из коробки в коробку».
1947: Формальное сокращение Постом кортежей Тьюринга из 5 кортежей до 4 кортежей.
[ редактировать ]Как кратко упоминается в статье « Машина Тьюринга» , Пост в своей статье 1947 года ( «Рекурсивная неразрешимость проблемы Туэ ») раздробил 5-кортежи Тьюринга на 4-кортежи:
- «Наши четверки являются пятёрками в развитии Тьюринга. То есть там, где наша стандартная инструкция заказывает либо печать (наложение), либо движение, влево или вправо, стандартная инструкция Тьюринга всегда заказывает печать и движение, вправо, влево или нет» ( сноска 12, Неразрешимо , стр. 300).
Как и Тьюринг, он определил стирание как печать символа «S0». И поэтому его модель допускала четверки только трех типов (ср. «Неразрешимые» , стр. 294):
- q я S j L q l ,
- q я S j R q л ,
- q я S j S k q l
В то время он все еще придерживался соглашения Тьюринга о конечном автомате - он не формализовал понятие предполагаемого последовательного выполнения шагов до тех пор, пока конкретная проверка символа не «разветвила» выполнение в другом месте.
1954, 1957: Модельные деньги
[ редактировать ]Для еще большего сокращения – всего лишь до четырех инструкций – представленной здесь модели Ванга см. Wang B-machine .
Ван (1957, но представлен ACM в 1954 году) часто цитируется (ср. Мински (1967), стр. 200) как источник «формулировки программ» машин Тьюринга с двоичной лентой с использованием пронумерованных инструкций из набора
- напиши 0
- напиши 1
- двигаться влево
- двигаться вправо
- если сканируется 0, перейдите к инструкции i
- если сканируете 1, перейдите к инструкции j
Любую машину Тьюринга с двоичной лентой можно легко преобразовать в эквивалентную «программу Ванга» с помощью приведенных выше инструкций.
1974: первая модель Дэвиса
[ редактировать ]Мартин Дэвис был студентом Эмиля Поста. Вместе со Стивеном Клин он защитил докторскую диссертацию. под церковью Алонсо (Дэвис (2000), 1-я и 2-я сноски, стр. 188).
Следующую модель он представил в серии лекций в Курантовском институте Нью-Йоркского университета в 1973–1974 годах. Это модель, к которой Дэвис формально применил название «машина Пост-Тьюринга» с ее «языком Пост-Тьюринга». [2] Предполагается, что инструкции выполняются последовательно (Дэвис 1974, стр. 71):
1978: вторая модель Дэвиса
[ редактировать ]Следующая модель представлена в виде эссе Что такое вычисление? в Стине, страницы 241–267. По какой-то причине Дэвис переименовал свою модель в «машину Тьюринга-Поста» (с одним обратным скольжением на странице 256).
В следующей модели Дэвис присваивает цифры «1» «знаку/косой черте» Поста и «0» пустому квадрату. Цитируя Дэвиса: «Теперь мы готовы представить язык программирования Тьюринга-Поста. В этом языке существует семь видов инструкций:
- «ПРИНТ 1
- «ПЕЧАТЬ 0
- «ИДИТЕ НАПРАВО
- «ИДИТЕ НАЛЕВО
- «ПЕРЕЙДИТЕ К ШАГУ i, ЕСЛИ 1 СКАНИРОВАНО
- «ПЕРЕЙДИТЕ К ШАГУ i, ЕСЛИ 0» СКАНИРОВАНО
- "ОСТАНАВЛИВАТЬСЯ
«Программа Тьюринга-Поста представляет собой список инструкций, каждая из которых относится к одному из этих семи видов. Конечно, в реальной программе буква i на шаге пятого или шестого рода должна быть заменена на определенное (целое положительное) число». (Дэвис в Стин, стр. 247).
1994 (2-е издание): Программная модель Дэвиса-Сигала-Вейкера Пост-Тьюринга.
[ редактировать ]«Хотя представленная нами формулировка Тьюринга ближе по духу к той, которую первоначально дал Эмиль Пост, именно анализ Тьюринга вычислений сделал эту формулировку настолько подходящей. Этот язык сыграл фундаментальную роль в теоретической информатике». (Дэвис и др. (1994), стр. 129)
Эта модель позволяет печатать несколько символов. Модель допускает B (пусто) вместо S 0 . Лента бесконечна в обоих направлениях. Либо голова, либо лента движется, но их определения ПРАВО и ЛЕВО всегда определяют один и тот же результат в любом случае (Тьюринг использовал одно и то же соглашение).
- PRINT σ ;Заменить отсканированный символ на σ
- IF σ GOTO L ; ЕСЛИ сканируемый символ равен σ THEN переход к «первой» инструкции с меткой L
- RIGHT ;Сканировать квадрат сразу справа от сканируемого в данный момент квадрата.
- LEFT ;Сканировать квадрат слева от сканируемого в данный момент квадрата
Эта модель сводится к двоичным версиям { 0, 1 }, представленным выше, как показано здесь:
- ПЕЧАТЬ 0 = СТЕРЕТЬ ; Заменить отсканированный символ на 0 = B = ПУСТОЙ
- ПЕЧАТЬ 1 ;Заменить отсканированный символ на 1
- IF 0 GOTO L ;ЕСЛИ сканируемый символ равен 0, ТОГДА переходим к «первой» инструкции с меткой L.
- IF 1 GOTO L ;ЕСЛИ отсканированный символ равен 1, ТОГДА переходим к «первой» инструкции, обозначенной L.
- RIGHT ;Сканировать квадрат сразу справа от сканируемого в данный момент квадрата.
- LEFT ;Сканировать квадрат слева от сканируемого в данный момент квадрата
Примеры машины Пост-Тьюринга
[ редактировать ]Атомизация пятерок Тьюринга в последовательность инструкций Пост-Тьюринга
[ редактировать ]Следующий метод «редукции» (декомпозиции, атомизации) - от 2-символьных 5-кортежей Тьюринга к последовательности 2-символьных инструкций Пост-Тьюринга - можно найти у Мински (1961). Он утверждает, что это сведение к « программе ... последовательности инструкций » находится в духе Хао Ванга Б-машины (курсив в оригинале, ср. Мински (1961), стр. 439).
(Сведение Мински к тому, что он называет «подпрограммой», приводит к 5, а не к 7 инструкциям Пост-Тьюринга. Он не атомизировал Wi0: «Записать символ Si0; перейти в новое состояние Mi0» и Wi1: «Записать символ Si1; перейти в новое состояние Mi1». Следующий метод дополнительно атомизирует Wi0 и Wi1; во всем остальном методы идентичны.)
Это сокращение 5-кортежей Тьюринга до инструкций Пост-Тьюринга может не привести к созданию «эффективной» программы Пост-Тьюринга, но оно будет верным исходной программе Тьюринга.
В следующем примере каждая пятерка Тьюринга занятого бобра с двумя состояниями преобразуется в
- начальный условный «переход» (goto, ветка), за которым следует
- 2 инструкции по ленточному действию для случая «0» — «Печать» или «Стереть» или «Нет», за которыми следует «Влево», «Вправо» или «Нет», а затем
- безусловный «переход» для случая «0» к следующей инструкции
- 2 инструкции по ленточному действию для случая «1» — «Печать» или «Стереть» или «Нет», затем «Влево», «Вправо» или «Нет», а затем
- безусловный «переход» для случая «1» к следующей инструкции
всего 1 + 2 + 1 + 2 + 1 = 7 инструкций на одно состояние Тьюринга.
Например, состояние Тьюринга «А» занятого бобра с двумя состояниями, записанное в виде двух строк по 5 кортежей, выглядит так:
| Начальная m-конфигурация (состояние Тьюринга) | Символ ленты | Операция печати | Движение ленты | Окончательная m-конфигурация (состояние Тьюринга) |
|---|---|---|---|---|
| А | 0 | П | Р | Б |
| А | 1 | П | л | Б |
Таблица представляет собой всего лишь одну «инструкцию» Тьюринга, но мы видим, что она состоит из двух строк по 5 кортежей: одна для случая «символ ленты под заголовком = 1», другая для случая «символ ленты под заголовком = 0». ". Тьюринг заметил ( «Undecidable» , стр. 119), что два левых столбца – «m-конфигурация» и «символ» – представляют текущую «конфигурацию» машины – ее состояние, включая Ленту и Таблицу в данный момент – и последние три столбца являются его последующее «поведение». Поскольку машина не может находиться в двух «состояниях» одновременно, она должна «разветвиться» либо в одну, либо в другую конфигурацию:
| Начальная m-конфигурация и символ S | Операция печати | Движение ленты | Окончательная m-конфигурация |
|---|---|---|---|
| С=0 → | П → | Р → | Б |
| → А < | |||
| С=1 → | П → | Л → | Б |
После «ветви конфигурации» (J1 xxx) или (J0 xxx) машина следует одному из двух последующих «поведений». Мы перечисляем эти два поведения в одной строке и нумеруем (или маркируем) их последовательно (уникально). Под каждым переходом (ветвью, переходом) мы помещаем его «номер» перехода (адрес, местоположение):
| Начальная m-конфигурация и символ S | Операция печати | Движение ленты | Окончательный случай m-конфигурации S=0 | Операция печати | Движение ленты | Окончательный случай m-конфигурации S=1 | |
|---|---|---|---|---|---|---|---|
| Если S=0, то: | П | Р | Б | ||||
| → А < | |||||||
| Если S=1, то: | П | л | Б | ||||
| инструкция № | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Пост-Тьюринговая инструкция | J1 | П | Р | Дж | П | л | Дж |
| переход к инструкции # | 5 | Б | Б |
Согласно соглашениям машины Пост-Тьюринга каждая из инструкций «Печать», «Стереть», «Влево» и «Вправо» состоит из двух действий:
- Действие ленты: {P, E, L, R}, затем
- Действие таблицы: перейти к следующей инструкции по порядку.
А согласно соглашениям машины Пост-Тьюринга условные «переходы» J0xxx, J1xxx состоят из двух действий:
- Действие ленты: посмотрите на символ на ленте под головой.
- Действие таблицы: если символ равен 0 (1) и J0 (J1), перейдите к xxx, иначе перейдите к следующей инструкции по порядку.
И согласно соглашениям машины Пост-Тьюринга безусловный «прыжок» Jxxx состоит из одного действия, или, если мы хотим упорядочить последовательность из двух действий:
- Действие ленты: посмотрите на символ на ленте под головой.
- Действие таблицы: если символ равен 0, перейдите к xxx, если символ равен 1, перейдите к xxx.
Какие и сколько прыжков необходимы? Безусловный переход J xxx — это просто J0 , за которым сразу следует J1 (или наоборот). Ван (1957) также показывает, что требуется только один условный переход, т.е. либо J0 xxx, либо J1 xxx. Однако из-за этого ограничения становится сложно писать инструкции для машины. Часто используются только два, т.е.
- { J0 ххх, J1 ххх }
- { J1 ххх, J ххх }
- { J0 xxx, J xxx },
но использование всех трех { J0 xxx, J1 xxx, J xxx} исключает дополнительные инструкции. В примере Busy Beaver с 2 состояниями мы используем только { J1 xxx, J xxx }.
Занятой бобр с 2 штатами
[ редактировать ]Миссия занятого бобра — напечатать как можно больше изображений, прежде чем остановиться. Инструкция «Печать» записывает 1, инструкция «Стереть» (не используется в этом примере) записывает 0 (т.е. это то же самое, что P0). Лента движется «влево» или «вправо» (т.е. «голова» неподвижна).
с двумя состояниями машины Тьюринга Таблица состояний для занятого бобра :
| Символ ленты | Текущее состояние А | Текущее состояние Б | ||||
|---|---|---|---|---|---|---|
| Написать символ | Переместить ленту | Следующее состояние | Написать символ | Переместить ленту | Следующее состояние | |
| 0 | 1 | Р | Б | 1 | л | А |
| 1 | 1 | л | Б | 1 | Н | ЧАС |
Инструкции для версии Пост-Тьюринга занятого бобра с двумя состояниями: обратите внимание, что все инструкции находятся в одной строке и в последовательности. Это существенное отличие от версии «Тьюринга» и имеет тот же формат, что и так называемая «компьютерная программа»:
| Инструкция № | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Инструкция | J1 | П | Р | Дж | П | л | Дж | J1 | П | л | Дж | П | Н | Дж | ЧАС |
| Перейти к # | 5 | 8 | 8 | 12 | 1 | 15 | |||||||||
| Метка состояния Тьюринга | А | Б | ЧАС |
Альтернативно мы могли бы записать таблицу в виде строки. Использование «разделителей параметров» «:» и разделителей инструкций «,» полностью является нашим выбором и не присутствует в модели. Не существует каких-либо соглашений (но см. Booth (1967), стр. 374 и Boolos and Jeffrey (1974, 1999), стр. 23), где описаны некоторые полезные идеи о том, как сочетать соглашения о диаграммах состояний с инструкциями – т.е. использовать стрелки для обозначения пункт назначения прыжков). В примере ниже инструкции идут последовательно, начиная с «1», а параметры/«операнды» считаются частью их инструкций/«кодов операций»:
- J1:5, P, R, J:8, P, L, J:8, J1:12, P, L, J1:1, P, N, J:15, H
Примечания
[ редактировать ]- ^ Раджендра Кумар, Теория автоматов , Tata McGraw-Hill Education, 2010, с. 343.
- ↑ Перейти обратно: Перейти обратно: а б В своей главе XIII «Вычислимые функции » Клини принимает модель Поста; В модели Клини используется пробел и один символ «отметка ¤» (Клин, стр. 358), «трактовка, в некоторых отношениях более близкая к Посту 1936 года. Пост 1936 года рассматривал вычисления с помощью двусторонней бесконечной ленты и только одного символа» (Клин, стр. 358). . 361). Клини отмечает, что трактовка Поста обеспечила дальнейшее сведение к «атомарным действиям» (Клин, стр. 357) «акта Тьюринга» (Клин, стр. 379). По описанию Клини, «Акт Тьюринга» представляет собой объединение трех (последовательных во времени) действий, указанных в строке таблицы Тьюринга: (i) печать-символ/стирание/ничего не делать, за которыми следует (ii) перемещение ленты влево /move-tape-right/do-nothing, за которым следует (iii) команда test-tape-go-to-next-instruction: например, «s1Rq1» означает «Напечатайте символ «¤», затем переместите ленту вправо, тогда, если символ ленты равен « ¤" затем перейдите в состояние q1". (См. пример Клини, стр. 358.)Клини отмечает, что Пост раздробил эти 3-действия на два типа 2-действий. Первый тип — это действие «печать/стирание», второй — «действие перемещения ленты влево/вправо»: (1.i) печать-символ/стирание/ничего не делать, за которым следует (1.ii) тестовая лента- перейти к следующей инструкции, ИЛИ (2.ii) переместить ленту влево/переместить ленту вправо/ничего не делать с последующим (2.ii) тестовой лентой-перейти к следующей инструкции. Но Клини отмечает, что, хотя
- «Действительно, можно утверждать, что акт машины Тьюринга уже является составным и психологически состоит в печати и изменении состояния ума, за которыми следуют движение и другое состояние ума [, и] Пост 1947 года, таким образом, разделяет акт Тьюринга на два мы здесь не делаем, прежде всего потому, что это экономит место в станочных столах» (Клин, стр. 379);
Ссылки
[ редактировать ]- Стивен К. Клини , «Введение в метаматематику», издательство North-Holland Publishing Company , Нью-Йорк, 10-е издание 1991 г., впервые опубликовано в 1952 г. Глава XIII представляет собой превосходное описание машин Тьюринга; Клини использует в своем описании модель типа Поста и признает, что модель Тьюринга можно еще более атомизировать, см. сноску 1.
- Мартин Дэвис , редактор: «Неразрешимое», «Основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях» , Raven Press, Нью-Йорк, 1965. В число статей входят статьи Гёделя , Чёрча , Россера , Клини и Поста.
- Мартин Дэвис , «Что такое вычисление», в «Математике сегодня », Линн Артур Стин, 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, Vol. 74, № 3, ноябрь 1961 г.
- Роджер Пенроуз , Новый разум императора: о компьютерах, разуме и законах физики , Oxford University Press, Оксфорд, Англия, 1990 (с исправлениями). См. Глава 2 «Алгоритмы и машины Тьюринга». Чрезмерно сложное изложение (более лучшую модель см. в статье Дэвиса), но подробное изложение машин Тьюринга, проблемы остановки и лямбда-исчисления Чёрча .
- Хао Ван (1957): «Вариант теории вычислительных машин Тьюринга», Журнал Ассоциации вычислительной техники (JACM) 4, 63–92.