Эквиваленты машины Тьюринга

Машина Тьюринга — это гипотетическое вычислительное устройство, впервые изобретенное Аланом Тьюрингом в 1936 году. Машины Тьюринга манипулируют символами на потенциально бесконечной полосе ленты в соответствии с конечной таблицей правил и обеспечивают теоретическую основу понятия компьютерного алгоритма.

Хотя ни одна из следующих моделей не показала большей эффективности, чем одноленточная, односторонняя, бесконечная, многосимвольная модель машины Тьюринга, их авторы определили и использовали их для исследования вопросов и решения проблем с большей легкостью, чем они могли бы. если бы они остались с моделью машины Тьюринга.

Машины, эквивалентные модели машины Тьюринга

Тьюринговая эквивалентность

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

Модели последовательных машин

Все перечисленные ниже модели называются «последовательными машинными моделями», чтобы отличить их от «параллельных машинных моделей». ^[2]

Ленточные машины Тьюринга

Тьюринг - модель машины

Машина Тьюринга (как он ее называл) была левосторонней и бесконечной справа. Он предоставил символы əə для обозначения левого конца. Разрешалось ограниченное количество символов ленты. Инструкции (если машина универсальная), а «вход» и «выход» писались только на «F-квадратах», а на «Е-квадратах» должны были появляться маркеры. По сути, он разделил свою машину на две ленты, которые всегда двигались вместе. Инструкции представлялись в табличной форме, называемой «5-кортежами», и не выполнялись последовательно.

Одноленточные машины с ограниченными символами и/или ограниченными инструкциями

Следующие модели представляют собой машины Тьюринга с одной лентой, но ограничены (i) ограниченными символами ленты { отметка, пробел } и/или (ii) последовательными компьютерными инструкциями и/или (iii) полностью атомизированными машинными действиями.

Модель вычислений Поста «Формула 1»

Эмиль Пост в независимом описании вычислительного процесса свел разрешенные символы к эквивалентному двоичному набору меток на ленте { "mark", "blank" = not_mark }. Он изменил понятие «ленты» с односторонней бесконечности вправо на бесконечное множество комнат, в каждой из которых есть лист бумаги в обоих направлениях. Он разделил 5-кортежи Тьюринга на 4-кортежи — инструкции движения отделены от инструкций печати/стирания. Хотя его модель 1936 года неоднозначна в этом отношении, модель Поста 1947 года не требовала последовательного выполнения инструкций.

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

Ван машины

В своей влиятельной статье Хао Ван » Поста свел « формулировку 1 к машинам, которые по-прежнему используют двустороннюю бесконечную двоичную ленту, но чьи инструкции проще – будучи «атомарными» компонентами инструкций Поста – и по умолчанию выполняются последовательно (например, «компьютерная программа»). Его заявленная основная цель заключалась в том, чтобы предложить в качестве альтернативы теории Тьюринга теорию, которая «более экономична в основных операциях». Его результатами стали «программные формулировки» множества таких машин, в том числе W-машины Ванга с 5 командами и набором команд.

{ SHIFT-ВЛЕВО, SHIFT-ВПРАВО, ОТМЕТКА-КВАДРАТ, СТЕРЕТЬ-КВАДРАТ, ПРЫГАТЬ-ЕСЛИ-КВАДРАТ-ОТМЕТКА-в xxx }

и его наиболее сильно урезанная B-машина Вана с четырьмя инструкциями («B» означает «базовый») с набором команд

{ SHIFT-LEFT, SHIFT-RIGHT, MARK-SQUARE, JUMP-IF-SQUARE-MARKED-to xxx }

в котором нет даже инструкции ERASE-SQUARE.

Многие авторы позже представили варианты машин, обсуждаемых Вангом:

Мински развил идею Вана, создав свою версию (многоленточной) модели «счетчика», которая позволяла перемещать отдельные головки с помощью SHIFT-LEFT и SHIFT-RIGHT, но вообще не печатать. ^[3] В этом случае ленты будут иметь левый конец, каждый конец будет отмечен одной «меткой», обозначающей конец. Ему удалось сократить это до одной ленты, но за счет введения движения с несколькими лентами в квадрате, эквивалентного умножению и делению, а не гораздо более простому { SHIFT-LEFT = DECREMENT, SHIFT-RIGHT = INCREMENT }.

Дэвис, добавляя явную инструкцию HALT к одной из машин, обсуждавшихся Вангом, использовал модель с набором команд

{ SHIFT-LEFT, SHIFT-RIGHT, ERASE, MARK, JUMP-IF-SQUARE-MARKED-to xxx, JUMP-to xxx, HALT }

а также рассматривались версии с лентой-алфавитами размером больше 2.

Теоретический машинный язык Бема P"

В соответствии с проектом Ванга по поиску теории, эквивалентной Тьюрингу, «экономичной в основных операциях» и стремящейся избежать безусловных переходов, известным теоретическим языком является язык с 4 инструкциями P», представленный Коррадо Бёмом в 1964 году - первый «GOTO». -менее «императивный» язык структурированного программирования должен быть доказан Тьюринг-полным .

Многоленточные машины Тьюринга

В практическом анализе часто используются различные типы многоленточных машин Тьюринга. Многоленточные машины аналогичны одноленточным машинам, но имеется некоторое постоянное число k независимых лент.

Детерминированные и недетерминированные машины Тьюринга

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

Забывчивые машины Тьюринга

Забывчивая машина Тьюринга — это машина Тьюринга, в которой для каждой входной длины движение различных головок является фиксированной функцией времени, независимой от входных данных. Другими словами, существует заранее определенная последовательность, в которой различные ленты сканируются, продвигаются вперед и записываются. Фактические значения, записываемые на ленту на любом этапе, могут быть разными для каждого входа такой длины. Пиппенджер и Фишер показали, что любое вычисление, которое может быть выполнено многоленточной машиной Тьюринга за n шагов, может быть выполнено не обращающей внимания двухленточной машиной Тьюринга за ⁠ $O(n\log n)$ ⁠ шаги. ^[4]

Забывчивые машины ступенчато-линейно соответствуют схемам комбинационной логики, когда сложность таблицы переходов принимается постоянной. Таким образом, можно реализовать вычисления как схемные задачи размером ⁠ $O(n\log n)$ ⁠ и глубина ⁠ $O(n)$ ⁠ (см. Сложность схемы ). Это улучшение оригинала ⁠ $O(n^{3})$ ⁠ результат Кука и Левина .

Регистрация моделей машин

Петер ван Эмде Боас относит все машины этого типа к одному классу — «регистрационные машины». ^[2] Однако исторически в литературе самого примитивного представителя этой группы, т.е. «счетную машину», называли также «регистровой машиной». А самый примитивный вариант «счетной машины» иногда называют «машиной Минского».

«Счетная машина», также называемая моделью «регистрационной машины».

Регистровая машина примитивной модели, по сути, представляет собой многоленточную двухсимвольную машину Пост-Тьюринга, поведение которой ограничено, поэтому ее ленты действуют как простые «счетчики».

Ко времени Мельзака, Ламбека и Мински понятие «компьютерной программы» породило другой тип простой машины со множеством лент с левым концом, вырезанных из ленты Пост-Тьюринга. Во всех случаях модели допускают только два символа ленты { отметка, пробел }. ^[3]

Некоторые версии представляют положительные целые числа как только строки/стопку меток, разрешенных в «регистре» (т.е. ленту с левым концом), и пустую ленту, представленную счетчиком «0». Мински устранил инструкцию ПЕЧАТЬ, снабдив свою модель обязательной одинарной отметкой на левом конце каждой ленты. ^[3]

В этой модели односторонние ленты-регистры рассматриваются как «счетчики», их инструкции ограничены только двумя (или тремя, если инструкция TEST/DECREMENT атомизирована). Два общих набора команд:

(1): { INC ( r ), DEC ( r ), JZ ( r,z ) }, т.е.

{ INCrement содержимое регистра #r; УМЕНЬШИТЬ содержимое регистра #r; IF содержимое #r=Zero THEN Инструкция перехода #z}

(2): {CLR (р); ВКЛ (р); JE ( r _i , r _j , z ) }, т.е.

{ CLeaR содержимое регистра r; INCrement содержимого r; сравнить содержимое r _i с r _j и, если равно, перейти к инструкции z}

Хотя его модель более сложна, чем это простое описание, модель «камешка» Мельзака расширила понятие «счетчика», чтобы разрешить мульти-камешек складывает и вычитает.

Модель машины с произвольным доступом (RAM)

Мельзак обнаружил пару серьезных дефектов в своей модели регистровой/счетной машины: ^[5] (i) Без формы косвенной адресации он не смог бы «легко» показать, что модель эквивалентна Тьюрингу , (ii) Программа и регистры находились в разных «пространствах», поэтому самомодифицирующиеся программы были бы непростыми. Когда Мельзак добавил в свою модель косвенную адресацию, он создал модель машины с произвольным доступом.

(Однако с помощью гёделевой нумерации инструкций Минский предложил доказательство того, что при такой нумерации общерекурсивные функции действительно возможны; он предлагает доказательство того, что µ-рекурсия действительно возможна. ^[3]).

В отличие от модели RASP, модель RAM не позволяет действиям машины изменять ее инструкции. Иногда модель работает только по регистру без аккумулятора, но большинство моделей, похоже, включают аккумулятор.

Ван Эмде Боас делит различные модели оперативной памяти на несколько подтипов: ^[2]

SRAM, «ОЗУ-преемник» только с одной арифметической инструкцией, преемником (ИНКРЕМЕНТ h). Остальные включают «CLEAR h» и переход IF равенства между регистрами THEN к xxx.
Оперативная память: стандартная модель со сложением и вычитанием
MRAM: оперативная память, дополненная функциями умножения и деления.
BRAM, MBRAM: побитовые логические версии RAM и MRAM.
N****: недетерминированные версии любого из вышеперечисленных с буквой N перед именем.

Модель машины с хранимой программой произвольного доступа (RASP)

RASP представляет собой ОЗУ, в котором инструкции хранятся вместе с их данными в одном и том же «пространстве», то есть последовательности регистров. Понятие RASP было описано, по крайней мере, еще в Кифенгсте. В его модели была «мельница» — аккумулятор, но теперь инструкции находились в регистрах вместе с данными — так называемая архитектура фон Неймана . Когда RASP имеет чередующиеся четные и нечетные регистры — четный содержит «код операции» (инструкцию), а нечетный — ее «операнд» (параметр), тогда косвенная адресация достигается путем простого изменения операнда инструкции. ^[6]

Первоначальная модель RASP Элгота и Робинсона содержала только три инструкции, аналогичные модели регистровой машины: ^[7] но они поместили их в регистровое пространство вместе со своими данными. (Здесь COPY заменяет CLEAR, когда один регистр, например, «z» или «0», начинается с 0 и всегда содержит 0. В этом трюке нет ничего необычного. Единица 1 в регистре «unit» или «1» также полезна.)

{ INC ( r ), COPY ( r _i, r _j ), JE ( r _i, r _i, z ) }

Модели RASP допускают как косвенную, так и прямую адресацию; некоторые допускают и «немедленные» инструкции, например «Загрузить аккумулятор с константой 3». Инструкции могут иметь весьма ограниченный набор, например следующие 16 инструкций Хартманиса. ^[8] В этой модели используется аккумулятор A. Мнемоника та же, что использовали авторы (их CLA — «нагрузочный аккумулятор» с константой или из регистра; STO — «сохраняющий аккумулятор»). Их синтаксис следующий, за исключением переходов: «n, <n>, <<n>>» для «немедленного», «прямого» и «косвенного»). Переходы осуществляются через две «инструкции передачи» TRA — безусловный переход путем прямого «n» или косвенного «<n>» забивания содержимого регистра n в счетчик команд TRZ (условный переход, если аккумулятор равен нулю, аналогично TRA):

{ ADD n , ADD < n >, ADD << n >>, SUB n, SUB < n >, SUB << n >>, CLA n, CLA < n >, CLA << n >>, STO < n > , СТО << n >>, TRA n, TRA < n >, ТРЗ n, TRA < n >, HALT }

Модель машины Pointer

Относительным опозданием стала машина модификации памяти Шёнхаге, или указательная машина . Другая версия - машина Колмогорова-Успенского и предложение Кнута о «связывающем автомате». (Для справки см. указательную машину ). Подобно диаграмме конечного автомата, узел испускает как минимум два помеченных «ребра» (стрелки), которые указывают на другой узел или узлы, которые, в свою очередь, указывают на другие узлы и т. д. Внешний мир указывает на центральный узел.

Машины с вводом и выводом

Любая из вышеперечисленных ленточных машин может быть оснащена входными и выходными лентами; Любая из вышеперечисленных машин на основе регистров может быть оснащена выделенными входными и выходными регистрами. Например, модель указательной машины Шёнхаге имеет две инструкции, называемые « вход λ ₀ , λ ₁ » и « выход β ».

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

Мы решаем эту проблему, введя k -струнную машину Тьюринга с вводом и выводом. Это то же самое, что и обычная машина Тьюринга с k -струной, за исключением того, что функция перехода $δ$ ограничена так, что входную ленту невозможно изменить, а выходная головка никогда не может двигаться влево. Эта модель позволяет нам определять детерминированные пространственные классы, меньшие, чем линейные. Машины Тьюринга с вводом и выводом имеют такую же временную сложность, как и другие машины Тьюринга; По словам Пападимитриу 1994 г., Предложение 2.2:

Для любой k -струнной машины Тьюринга M, работающей за ограниченное время ⁠

f(n)

⁠ есть ⁠

(k+2)

⁠ -струнная машина Тьюринга M' со входом и выходом, работающая в пределах времени ⁠

O(f(n))

⁠ .

k -строковые машины Тьюринга с вводом и выводом могут использоваться в формальном определении ресурса сложности DSPACE . ^[9]

Другие эквивалентные машины и методы

Многомерная машина Тьюринга. Например, модель Шёнхаге использует четыре команды движения головы { Север , Юг , Восток , Запад }. ^[10]
Машина Тьюринга с одной лентой и несколькими головками: в доказательстве неразрешимости «проблемы тегов» Мински, Шепердсон и Стерджис описали машины с одной лентой, которые могли читать по ленте одной головкой и писать дальше по ленте другой. . ^[11]^[12]

Алгоритм Маркова — еще одна удивительно простая вычислительная модель, основанная на переписывании строк, эквивалентная машинам Тьюринга.
Лямбда-исчисление
Автомат очереди

Ссылки

^ Джон Хопкрофт и Джеффри Уллман (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Аддисон-Уэсли, Reading Mass. ISBN 0-201-02988-Х .
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Питер ван Эмде Боас , «Модели машин и моделирование» ; Ян ван Леувен , изд. Справочник по теоретической информатике. Том А: Алгоритмы и сложность , с. 3-66, MIT Press/Elsevier, 1990. ISBN 0-262-72014-0 (том А). QA76.H279 1990 г.
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д Марвин Мински , Вычисления: конечные и бесконечные машины , Prentice-Hall, Inc., Нью-Джерси, 1967. См. главу 8, раздел 8.2 «Неразрешимость проблемы остановки».
^ Пиппенджер, Николас ; Фишер, Майкл Дж. (1979), «Отношения между мерами сложности» , Журнал ACM , 26 (3): 361–381, doi : 10.1145/322123.322138 , S2CID 2432526
^ Мельзак, З.А. (сентябрь 1961 г.). «Неформальный арифметический подход к вычислимости и вычислениям» . Канадский математический бюллетень . 4 (3): 279–293. дои : 10.4153/CMB-1961-031-9 .
^ Стивен А. Кук и Роберт А. Рекхоу (1972), Машины произвольного доступа с ограниченным временем , Journal of Computer Systems Science 7 (1973), 354–375.
^ Кэлвин Элгот и Авраам Робинсон (1964), Машины с произвольным доступом к хранимым программам, подход к языкам программирования , Журнал Ассоциации вычислительной техники, Vol. 11, № 4 (октябрь 1964 г.), стр. 365–399.
^ Дж. Хартманис (1971), «Вычислительная сложность машин с хранимыми программами произвольного доступа», Теория математических систем 5, 3 (1971), стр. 232–245.
^ Христос Пападимитриу (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. ISBN 0-201-53082-1 . Глава 2: Машины Тьюринга, стр. 19–56.
^ А. Шонхаге (1980), Машины для модификации памяти , Общество промышленной и прикладной математики, SIAM J. Comput. Том. 9, № 3, август 1980 г.
^ Марвин Мински (15 августа 1960 г.). «Рекурсивная неразрешимость проблемы Поста о «теге» и других тем теории машин Тьюринга». Анналы математики . 74 (3): 437–455. дои : 10.2307/1970290 . JSTOR 1970290 .
^ Джон К. Шепердсон и Х. Э. Стерджис получили в декабре 1961 г. вычислимость рекурсивных функций , Журнал ACM 10: 217-255, 1963.

[1] Джон Хопкрофт и Джеффри Уллман (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Аддисон-Уэсли, Reading Mass. ISBN 0-201-02988-Х .

[Boas-2] Перейти обратно: Перейти обратно: ^а ^б ^с Питер ван Эмде Боас , «Модели машин и моделирование» ; Ян ван Леувен , изд. Справочник по теоретической информатике. Том А: Алгоритмы и сложность , с. 3-66, MIT Press/Elsevier, 1990. ISBN 0-262-72014-0 (том А). QA76.H279 1990 г.

[Marvin-3] Перейти обратно: Перейти обратно: ^а ^б ^с ^д Марвин Мински , Вычисления: конечные и бесконечные машины , Prentice-Hall, Inc., Нью-Джерси, 1967. См. главу 8, раздел 8.2 «Неразрешимость проблемы остановки».

[4] Пиппенджер, Николас ; Фишер, Майкл Дж. (1979), «Отношения между мерами сложности» , Журнал ACM , 26 (3): 361–381, doi : 10.1145/322123.322138 , S2CID 2432526

[5] Мельзак, З.А. (сентябрь 1961 г.). «Неформальный арифметический подход к вычислимости и вычислениям» . Канадский математический бюллетень . 4 (3): 279–293. дои : 10.4153/CMB-1961-031-9 .

[6] Стивен А. Кук и Роберт А. Рекхоу (1972), Машины произвольного доступа с ограниченным временем , Journal of Computer Systems Science 7 (1973), 354–375.

[7] Кэлвин Элгот и Авраам Робинсон (1964), Машины с произвольным доступом к хранимым программам, подход к языкам программирования , Журнал Ассоциации вычислительной техники, Vol. 11, № 4 (октябрь 1964 г.), стр. 365–399.

[8] Дж. Хартманис (1971), «Вычислительная сложность машин с хранимыми программами произвольного доступа», Теория математических систем 5, 3 (1971), стр. 232–245.

[9] Христос Пападимитриу (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. ISBN 0-201-53082-1 . Глава 2: Машины Тьюринга, стр. 19–56.

[Schonage80-10] А. Шонхаге (1980), Машины для модификации памяти , Общество промышленной и прикладной математики, SIAM J. Comput. Том. 9, № 3, август 1980 г.

[11] Марвин Мински (15 августа 1960 г.). «Рекурсивная неразрешимость проблемы Поста о «теге» и других тем теории машин Тьюринга». Анналы математики . 74 (3): 437–455. дои : 10.2307/1970290 . JSTOR 1970290 .

[12] Джон К. Шепердсон и Х. Э. Стерджис получили в декабре 1961 г. вычислимость рекурсивных функций , Журнал ACM 10: 217-255, 1963.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]