Машина Тьюринга является гипотетическим вычислительное устройство, первый зачат Алан Тьюринг в 1936 году машины Тьюринга манипулировать символами на потенциально бесконечной полосы ленты в соответствии с конечной таблицей правил, и они обеспечивают теоретические основы для понятия алгоритма компьютера.
Хотя ни одна из следующих моделей не продемонстрировала большей мощности, чем однопленочная, односторонняя бесконечная, многосимвольная модель машины Тьюринга, их авторы определили и использовали их для исследования вопросов и решения проблем более легко, чем они могли бы. если бы они остались с Тьюринга -machine модель.
Машины, эквивалентные модели машины Тьюринга [ править ]
Эквивалентность Тьюринга
Можно показать, что многие машины, которые, как можно было бы подумать, обладают большими вычислительными возможностями, чем простая универсальная машина Тьюринга, не обладают большей мощностью. [1] Они могут вычислять быстрее, возможно, использовать меньше памяти, или их набор инструкций может быть меньше, но они не могут выполнять вычисления более мощно (то есть больше математических функций). ( Тезис Черча-Тьюринга предполагает, что это правда: все, что можно «вычислить», можно вычислить с помощью некоторой машины Тьюринга.)
Последовательные машинные модели
Все нижеперечисленное называется «последовательными моделями машин», чтобы отличать их от «параллельных машинных моделей». [2]
Ленточные машины Тьюринга [ править ]
Тьюринг -machine модели
А-машина Тьюринга (как он ее называл) была левосторонней, правосторонней - бесконечной. Он предоставил символы əə, чтобы отметить левый конец. Допускалось ограниченное количество символов ленты. Инструкции (если это универсальная машина), а также «вход» и «выход» были написаны только на «F-квадратах», а маркеры должны были появиться на «E-квадратах». По сути, он разделил свою машину на две ленты, которые всегда двигались вместе. Инструкции представлены в табличной форме, называемой «кортежами из 5 элементов», и не выполняются последовательно.
Однопленочные машины с ограниченными символами и / или ограниченными инструкциями [ править ]
Следующие модели представляют собой однопленочные машины Тьюринга, но ограничены (i) ограниченными ленточными символами {mark, blank} и / или (ii) последовательными компьютерными инструкциями и / или (iii) полностью атомизированными машинными действиями.
Модель вычислений "Формулировка 1" публикации [ править ]
Эмиль Пост в независимом описании вычислительного процесса сократил разрешенные символы до эквивалентного двоичного набора меток на ленте {"mark", "blank" = not_mark}. Он изменил понятие «ленты» с односторонней бесконечности вправо на бесконечный набор комнат, каждая с листом бумаги в обоих направлениях. Он разделил 5-кортежи Тьюринга на 4-кортежи - инструкции движения отдельно от инструкций печати / стирания. Хотя его модель 1936 года неоднозначна по этому поводу, модель Поста 1947 года не требовала последовательного выполнения инструкций.
Его чрезвычайно простая модель может имитировать любую машину Тьюринга, и хотя в его Формулировке 1 1936 года не используются слова «программа» или «машина», это фактически формулировка очень примитивного программируемого компьютера и связанного с ним языка программирования , с прямоугольниками, действующими как неограниченная память битовых строк и набор инструкций, составляющих программу.
Машины Ван [ править ]
В влиятельной статье Хао Ван свел « формулировку 1 » Поста к машинам, которые все еще используют двустороннюю бесконечную двоичную ленту, но чьи инструкции проще - являются «атомарными» компонентами инструкций Поста - и по умолчанию выполняются последовательно (например, "компьютерная программа"). Его заявленная основная цель состояла в том, чтобы предложить в качестве альтернативы теории Тьюринга теорию, которая «более экономична в основных операциях». Его результатами были «программные формулировки» множества таких машин, включая 5-командную машину Ванга W с набором команд.
- {SHIFT-LEFT, SHIFT-RIGHT, MARK-SQUARE, ERASE-SQUARE, JUMP-IF-SQUARE-MARKED-to xxx}
и его наиболее сильно сокращенная 4- командная B-машина Ванга («B» для «базового») с набором команд
- {SHIFT-LEFT, SHIFT-RIGHT, MARK-SQUARE, JUMP-IF-SQUARE-MARKED-to xxx}
в котором нет даже инструкции ERASE-SQUARE.
Позже многие авторы представили варианты машин, о которых говорил Ван:
Мински развил идею Ванга с его версией (многолентой) модели «встречной машины», которая позволяла сдвигать-ВЛЕВО и СДВИГ-ВПРАВО для отдельных головок, но не печатала вообще. [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 » [ править ]
В соответствии с проектом Ванга по поиску теории, эквивалентной Тьюрингу, «экономичной в основных операциях» и стремящейся избежать безусловных скачков, заметным теоретическим языком является язык P с 4 инструкциями, представленный Коррадо Бемом в 1964 году - первый «GOTO -без «императивного» языка структурированного программирования быть доказанным по Тьюрингу .
Многоленточные машины Тьюринга [ править ]
В практическом анализе часто используются различные типы многоленточных машин Тьюринга. Многоленточные машины похожи на однопленочные, но существует некоторое постоянное k независимых лент.
Детерминированные и недетерминированные машины Тьюринга [ править ]
Если в таблице действий есть не более одной записи для каждой комбинации символа и состояния, тогда машина является «детерминированной машиной Тьюринга» (DTM). Если таблица действий содержит несколько записей для комбинации символа и состояния, тогда машина является «недетерминированной машиной Тьюринга» (NDTM). Оба они вычислительно эквивалентны, то есть любой NDTM можно превратить в DTM (и наоборот ) , хотя обычно они имеют разное время выполнения. Это можно доказать с помощью построения.
Забывчивые машины Тьюринга [ править ]
Невидимая машина Тьюринга - это машина Тьюринга, в которой для каждой длины ввода движение различных головок является фиксированной функцией времени, независимо от ввода. Другими словами, существует заранее определенная последовательность, в которой различные ленты сканируются, продвигаются и записываются. Фактические значения, записываемые на ленту на любом этапе, могут по-прежнему отличаться для каждого ввода такой длины. Пиппенгер и Фишер показали, что любое вычисление, которое может быть выполнено многоленточной машиной Тьюринга за n шагов, может быть выполнено зашаговой двухленточной машиной Тьюринга . [4]
Зарегистрировать модели машин [ править ]
Питер ван Эмде Боас объединяет все машины этого типа в один класс - «регистровые машины». [2] Однако исторически в литературе также называли наиболее примитивного представителя этой группы, то есть «счетную машину» - «регистровую машину». А самый примитивный вариант «счетной машины» иногда называют «машиной Минского».
«Машина счетчика», также называемая моделью «регистрационной машины» [ править ]
Регистровая машина примитивной модели, по сути, представляет собой двухленточную двухсимвольную машину Пост-Тьюринга с ограниченным поведением, поэтому ее ленты действуют как простые «счетчики».
Ко времени Мелзака, Ламбека и Мински понятие «компьютерная программа» произвело другой тип простой машины с множеством левых лент, вырезанных из ленты Пост-Тьюринга. Во всех случаях модели допускают использование только двух символов ленты {метка, пробел}. [3]
Некоторые версии представляют положительные целые числа только в виде строк / стопки меток, разрешенных в «регистре» (т. Е. С левой стороны ленты), и пустой ленты, представленной счетчиком «0». Минский исключил инструкцию ПЕЧАТЬ за счет того, что снабдил свою модель обязательной одиночной отметкой в левом конце каждой ленты. [3]
В этой модели несимметричные ленты-регистры рассматриваются как «счетчики», их инструкции ограничиваются только двумя (или тремя, если команда TEST / DECREMENT атомизируется). Вот два общих набора инструкций:
- (1): {INC (r), DEC (r), JZ (r, z)}, т.е.
- {INCrement содержимое регистра №r; Укажите содержимое регистра №r; ЕСЛИ содержимое # r = Zero THEN Перейти к инструкции #z}
- (2): {CLR (r); INC (r); JE (r i , r j , z)}, т.е.
- {CLeaR содержимое регистра r; Увеличить содержание r; сравнить содержимое r i с r j, и если равно, то перейти к инструкции z}
Хотя его модель сложнее, чем это простое описание, модель «гальки» Мелзака расширила это понятие «счетчик», чтобы разрешить сложение и вычитание нескольких гальк.
Модель машины с произвольным доступом (RAM) [ править ]
Мелзак обнаружил пару серьезных недостатков в своей модели регистра / контрмашины: [5] (i) без формы косвенной адресации он не смог бы «легко» показать, что модель эквивалентна Тьюрингу , (ii) программа и регистры находились в разных «пространствах», поэтому самомодификация программ была бы непростой задачей. Когда Мелзак добавил в свою модель косвенную адресацию, он создал модель машины с произвольным доступом.
(Однако с помощью гёделевской нумерации инструкций Мински предложил доказательство того, что с такой нумерацией общерекурсивные функции действительно возможны; он предлагает доказательство того, что μ-рекурсия действительно возможна [3] ).
В отличие от модели RASP, модель RAM не позволяет действиям машины изменять ее инструкции. Иногда модель работает только регистр-регистр без аккумулятора, но в большинстве моделей, похоже, есть аккумулятор.
Ван Эмде Боас делит различные модели RAM на несколько подтипов: [2]
- SRAM, «преемник RAM» только с одной арифметической инструкцией, преемник (INCREMENT h). Остальные включают «CLEAR h» и ЕСЛИ равенство между регистрами THEN переход к xxx.
- RAM: стандартная модель с добавлением и вычитанием
- MRAM: оперативная память, дополненная умножением и делением
- BRAM, MBRAM: побитовые логические версии RAM и MRAM.
- N ****: недетерминированные версии любого из вышеперечисленных с буквой N перед именем.
Модель машины с хранимой программой с произвольным доступом (RASP) [ править ]
RASP - это ОЗУ, в котором инструкции хранятся вместе с данными в одном и том же «пространстве», то есть в последовательности регистров. Понятие RASP было описано, по крайней мере, еще в Kiphengst. В его модели была «мельница» - аккумулятор, но теперь инструкции были в регистрах с данными - так называемая архитектура фон Неймана . Когда RASP имеет чередующиеся четные и нечетные регистры - четный хранит «код операции» (инструкция), а нечетный - его «операнд» (параметр), тогда косвенная адресация достигается простым изменением операнда инструкции. [6]
Исходная модель RASP Элгота и Робинсона имела только три инструкции в стиле модели регистровой машины [7], но они поместили их в регистровое пространство вместе со своими данными. (Здесь COPY заменяет CLEAR, когда один регистр, например, «z» или «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 (условный переход, если Accumulator равен нулю, так же, как TRA):
- {ДОБАВИТЬ n, ДОБАВИТЬ <n>, ДОБАВИТЬ << n >>, SUB n, SUB <n>, SUB << n >>, CLA n, CLA <n>, CLA << n >>, STO <n> , STO << n >>, TRA n, TRA <n>, TRZ n, TRA <n>, HALT}
Модель машины указателя [ править ]
Относительно поздно пришла машина для модификации хранилища или указательная машина Шёнхаге . Другая версия - это машина Колмогорова-Успенского и предложение Кнута о «связывающем автомате». (Для справки см. Указатель машины ). Подобно диаграмме конечного автомата, узел излучает по крайней мере два помеченных «ребра» (стрелки), которые указывают на другой узел или узлы, которые, в свою очередь, указывают на другие узлы и т. Д. Внешний мир указывает на центральный узел.
Машины с вводом и выводом [ править ]
Любая из вышеперечисленных ленточных машин может быть оборудована входными и выходными лентами; любая из вышеперечисленных машин на основе регистров может быть оснащена специальными регистрами ввода и вывода. Например, модель указательной машины Шёнхаге имеет две инструкции, называемые « вход λ 0 , λ 1 » и « выход β ».
Сложно исследовать сублинейную пространственную сложность на многоленточных машинах с традиционной моделью, потому что вход размера n уже занимает пространство n . Таким образом, чтобы изучить небольшие классы DSPACE , мы должны использовать другую модель. В некотором смысле, если мы никогда не «записываем» на входную ленту, мы не хотим заряжать себя за это пространство. И если мы никогда не «читаем» с нашей выходной ленты, мы не хотим заряжать себя за это пространство.
Мы решаем эту проблему, вводя k -струнную машину Тьюринга с вводом и выводом. Это то же самое, что и обычная k- струнная машина Тьюринга, за исключением того, что функция перехода δ ограничена так, что входная лента никогда не может быть изменена, а выходная головка никогда не может перемещаться влево. Эта модель позволяет нам определять детерминированные пространственные классы меньшие, чем линейные. Машины Тьюринга с вводом и выводом также имеют такую же временную сложность, как и другие машины Тьюринга; по словам Пападимитриу 1994, Предложение 2.2:
- Для любой k -струнной машины Тьюринга M, работающей в пределах времени, существует -струнная машина Тьюринга M ' с входом и выходом, которая работает в пределах времени .
k -струнные машины Тьюринга с вводом и выводом могут использоваться в формальном определении ресурса сложности DSPACE . [9]
Другие эквивалентные машины и методы [ править ]
- Многомерная машина Тьюринга: Например, модель с Шёнхагом использует четыре команды головного движения { N Orth, S outh, E AST, W EST}. [10]
- Однолента, многоголовочная машина Тьюринга: в доказательстве неразрешимости «проблемы тегов» Мински, Шепердсон и Стерджис описали машины с одной лентой, которая могла бы писать вдоль ленты одной головкой и читать дальше вдоль ленты другой. . [11] [12]
- Алгоритм Маркова - еще одна удивительно простая вычислительная модель, основанная на перезаписи строк, эквивалентная машинам Тьюринга.
- Лямбда-исчисление
- Автомат очереди
Ссылки [ править ]
- ^ Джон Хопкрофт и Джеффри Уллман (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Эддисон – Уэсли, штат Массачусетс, штат Массачусетс, ISBN 0-201-02988-X.
- ^ a b c Питер ван Эмде Боас , Модели машин и симуляторы ; Ян ван Леувен , изд. Справочник по теоретической информатике. Том A: Алгоритмы и сложность , стр. 3-66, MIT Press / Elsevier, 1990. ISBN 0-262-72014-0 (том A). QA76.H279 1990.
- ^ a b c d Марвин Мински , Вычисления: конечные и бесконечные машины , Prentice-Hall, Inc., Нью-Джерси, 1967. См. главу 8, раздел 8.2 «Неразрешимость проблемы остановки».
- ^ Пиппенгер, Николас ; Фишер, Майкл Дж (1979), "отношения между" Меры сложности, J ACM , 26 (3): 361-381, DOI : 10,1145 / 322123,322138 CS1 maint: discouraged parameter (link)
- ^ ZA Melzak , Неформальный арифметический подход к вычислимости и вычислениям , Canadian Mathematical Bulletin, vol. 4, вып. 3. Сентябрь 1961 г., стр. 279–293.
- ^ Стивен А. Кук и Роберт А. Рекхоу (1972), Машины с произвольным доступом с ограничением по времени , Журнал компьютерных систем науки 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. вычислы. Vol. 9, No. 3, август 1980 г.
- ↑ Марвин Мински (15 августа 1960). "Рекурсивная неразрешимость проблемы Поста" тега "и других тем теории машин Тьюринга". Анналы математики . Анналы математики. 74 (3): 437–455. DOI : 10.2307 / 1970290 . JSTOR 1970290 .
- ^ Джон С. Шепердсон и Х. Стерджис получили в декабре 1961 г. « Вычислимость рекурсивных функций» , журнал Ассоциации вычислительной техники (JACM) 10: 217-255, 1963 г.
