Модель контрмашины

Существует много вариантов счетной машины , среди них Hermes , Ershov , Péter , Minsky , Lambek , Shepherdson and Sturgis и Schönhage . Они описаны ниже.

Шепердсон и Стерджис (1963) отмечают, что «доказательство этой универсальности [цифровых компьютеров для машин Тьюринга] ... по-видимому, было впервые записано Гермесом, который показал в [7 — их номер ссылки], как идеализированный компьютер может быть запрограммирован для копирования поведения любой машины Тьюринга» , и: «Подход Капенгста интересен тем, что он дает прямое доказательство универсальности современных цифровых компьютеров, по крайней мере, когда они идеализированы до такой степени, что допускают бесконечное число регистров хранения, каждый из которых способен хранить произвольно длинные слова» . ^[1]

Единственные две арифметические инструкции:

1. Операция-преемник
2. Проверка двух чисел на равенство

Остальные операции представляют собой переносы из регистра в аккумулятор или из аккумулятора в регистр или тестовые переходы.

Статья Капенгста написана на немецком языке; в переводе Шепердсона и Стерджиса используются такие термины, как «мельница» и «заказы».

Машина содержит «мельницу» (аккумулятор). Капенгст обозначает свою мельницу/аккумулятор символом «бесконечность», но в следующем описании мы будем использовать «A». Она также содержит «регистр порядка» («порядок» как в «инструкции», а не как в «последовательности»). (Это использование пришло из описания отчета Беркса–Голдстайна–фон Неймана (1946) «...электронного вычислительного прибора».) Регистр порядка/инструкции — это регистр «0». И, хотя это не ясно из описания Шепердсона и Стерджиса, модель содержит «регистр расширения», обозначенный Капенгстом как «бесконечность-простое»; мы будем использовать «E».

Инструкции хранятся в регистрах:

«...поэтому машина, как и настоящий компьютер, способна выполнять арифметические операции по своей собственной программе» (стр. 244).

Таким образом, эта модель фактически является машиной с произвольным доступом . В дальнейшем "[ r ]" указывает на "содержимое" регистра r и т. д.

Шепердсон и Стерджис (1963) удаляют мельницу/аккумулятор A и сокращают инструкции Капенгста до "копирования" регистр-регистр, арифметической операции "инкремент" и "сравнения регистр-регистр". Обратите внимание, что нет декремента . Эту модель, почти дословно, можно найти у Мински (1967); см. больше в разделе ниже.

Шепердсон и Стерджис (1963) отмечают, что модель Эрсова допускает хранение программы в регистрах. Они утверждают, что модель Эрсова выглядит следующим образом:

Шепердсон и Стерджис (1963) отмечают, что "лечение" Петера (они не слишком конкретны здесь) имеет эквивалентность инструкциям, показанным в следующей таблице. Они комментируют эти инструкции конкретно, что:

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

Исследование проблем Эмиля Поста ( система тегов ) и 10-й проблемы Гильберта ( проблемы Гильберта , диофантовы уравнения ) привело Минского к следующему определению:

«интересная основа для теории рекурсивных функций, включающая программы только простейших арифметических операций» (Минский (1961) стр. 437).

Его «Теорема Ia» утверждает, что любая частично рекурсивная функция представлена ​​«программой, работающей с двумя целыми числами S1 и S2, используя инструкции Ij следующего вида (ср. Минский (1961) стр. 449):

Первая теорема является контекстом второй «Теоремы IIa», которая

«...представляет любую частично рекурсивную функцию программой, работающей с одним целым числом S [содержащимся в одном регистре r1], используя инструкции I _j следующих форм»:

Во второй форме машина использует числа Гёделя для обработки «целого числа S». Он утверждает, что первой машине/модели не нужно этого делать, если у нее есть 4 доступных регистра.

«Наша цель — описать примитивное устройство, которое будет называться Q-машиной, которая достигает эффективной вычислимости посредством арифметики, а не посредством логики. Ее три операции — это подсчет, сравнение неотрицательных целых чисел и перенос» (Melzak (1961) стр. 281)

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

Физическая модель Мелзака представляет собой отверстия {X, Y, Z и т. д.} в земле вместе с неограниченным запасом гальки в специальном отверстии S (Сток или Запас, или и то, и другое? Мелзак не говорит).

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

Инструкция представляет собой одну «троичную операцию», которую он называет «XYZ»:

«XYZ» обозначает операцию

1. Подсчитайте количество камешков в лунке Y ,
2. поместите их обратно в Y ,
3. попытаться удалить это же число из отверстия X. ЕСЛИ это невозможно, так как это приведет к опустошению отверстия X, ТО ничего не делать и перейти к инструкции #I; ИНАЧЕ,
4. удалить величину Y из X и (iv) перенести ее, т.е. прибавить ее к величине в отверстии Z.

Из всех возможных операций некоторые не допускаются, как показано в таблице ниже:

Некоторые наблюдения о модели Мелзака :

Оригинальная модель «абака» Ламбека (1962):

Ламбек ссылается на статью Мелзака. Он атомизирует единственную 3-параметрическую операцию Мелзака (на самом деле 4, если считать адреса инструкций) в 2-параметрический инкремент "X+" и 3-параметрический декремент "X-". Он также дает как неформальное, так и формальное определение "программы". Эта форма фактически идентична модели Мински (1961) и была принята Булосом, Берджесом и Джеффри (2007, стр. 45, Abacus Computability).

Модель Абакуса Булоса, Берджесса и Джеффри : ^[3]

В различных изданиях, начиная с 1970 года, авторы используют модель «бесконечного счеты» Ламбека (1961). Эта серия статей Википедии использует их символику, например, «[ r ] +1 → r» «содержимое регистра, идентифицированного как число „r“, плюс 1 заменяет содержимое [помещается в] регистр с числом „r“».

Они используют название Ламбека «абак», но следуют модели «камешки в дырках» Мелзака, модифицированной ими до модели «камни в ящиках». Как и оригинальная модель абака Ламбека, их модель сохраняет использование Мински (1961) непоследовательных инструкций – в отличие от «обычного» последовательного выполнения инструкций по умолчанию, как у компьютеров, следующая инструкция I _a содержится внутри инструкции.

Однако следует отметить, что BB и BBJ не используют переменную «X» в мнемонике с уточняющим параметром (как показано в версии Lambek) — то есть «X+» и «X-» — а вместо этого мнемоника инструкции указывает сами регистры, например «2+» или «3-»:

Шепердсон и Стерджис (1963) ссылаются на работу Мински (1961), представленную им в форме отчета лаборатории Линкольна Массачусетского технологического института :

В разделе 10 мы показываем, что теоремы (включая результаты Мински [21, их ссылка]) о вычислении частично рекурсивных функций с помощью одной или двух лент могут быть довольно легко получены из одной из наших промежуточных форм.

—  Шепердсон и Стерджис (1963, стр. 218)

Их модель находится под сильным влиянием модели и духа Хао Вана (1957) и его B-машины Вана (см. также Машина Пост-Тьюринга ). Они «подводят итог, говоря»:

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

Неограниченная регистровая машина URM : ^[4] Это их «самая гибкая машина... состоит из счетной последовательности регистров, пронумерованных 1, 2, 3, ..., каждый из которых может хранить любое натуральное число... Каждая конкретная программа, однако, включает только конечное число этих регистров» (стр. 219). Другими словами, число регистров потенциально бесконечно, и «размер» каждого регистра бесконечен.

Они предлагают следующий набор инструкций ^[1] и следующие «Примечания»:

Примечания.

1. Этот набор инструкций выбран для простоты программирования вычисления частично рекурсивных функций, а не для экономии; в разделе 4 показано, что этот набор эквивалентен меньшему набору.
2. В этом списке бесконечно много инструкций, поскольку m, n [содержимое r _j и т. д.] охватывают все положительные целые числа.
3. В инструкциях a, b, c, d содержимое всех регистров, кроме n, предполагается оставить неизменным; в инструкциях e, f содержимое всех регистров остается неизменным (стр. 219).

Действительно, они показывают, как можно еще больше сократить этот набор до следующего (для бесконечного числа регистров, каждый из которых имеет бесконечный размер):

Машина с ограниченным регистром LRM : Здесь они ограничивают машину конечным числом регистров N, но также позволяют «вводить» или удалять больше регистров, если они пусты (ср. стр. 228). Они показывают, что инструкция удаления регистра не обязательно требует пустого регистра.

Однорегистровая машина SRM : Здесь они реализуют систему тегов Эмиля Поста и тем самым позволяют записывать только до конца строки и стирать с начала. Это показано на их рисунке 1 как лента с головкой чтения слева и головкой записи справа, и она может перемещать ленту только вправо. «A» — это их «слово» (стр. 229):

а. P(i) ;добавляем ai в конец A

б. D ;удалить первую букву A

f'. Ji[E1] ;Если A начинается с ai, перейти к выходу 1.

Они также предлагают модель в виде «стопки карт» с символами {0, 1} (стр. 232 и Приложение C, стр. 248):

1. добавить карточку вверху напечатано 1
2. добавить карту вверху напечатано 0
3. удалите нижнюю карту; если напечатано 1, перейдите к инструкции m, иначе следующая инструкция.

В конечном счете, в задаче 11.7-1 Мински замечает, что многие базы вычислений могут быть сформированы из небольшого набора:

«Многие другие комбинации типов операций [ 0 ], [ ' ], [ - ], [ O- ], [ → ] и [ RPT ] образуют универсальный базис. Найдите некоторые из этих базисов. Какие комбинации из трех операций не являются универсальным базисом? Придумайте другие операции...» (стр. 214)

Ниже приведены определения различных инструкций, которые он рассматривает:

Минский (1967) начинает с модели, состоящей из трех операций плюс HALT:

{ [ 0 ], [ ' ], [ - ], [ Н ] }

Он замечает, что мы можем обойтись без [ 0 ], если допустим, что определенный регистр, например, w уже «пустой» (Minsky (1967) стр. 206). Позже (стр. 255 и далее) он сжимает три { [ 0 ], [ ' ], [ - ] } в два { [ ' ], [ - ] }.

Но он признает, что модель становится проще, если добавить несколько [псевдо]-инструкций [ O- ] (объединенных [ 0 ] и [ - ]) и "go(n)". Он строит "go(n)" из регистра w, предварительно установленного в 0, так что [O-] ( w , (n)) является безусловным переходом.

В разделе 11.5 «Эквивалентность программных машин с общерекурсивными функциями» он вводит две новые подпрограммы:

ф. [ → ]

к. [ ≠ ]

Переход, если не равно": ЕСЛИ [ r _j ] ≠ [ r _k ] ТО переход к z-й инструкции ИНАЧЕ следующая инструкция

Он продолжает показывать, как заменить набор "последователь-предшественник" { [ 0 ], [ ' ], [ - ] } на набор "последователь-равенство" { [ 0 ], [ ' ], [ ≠ ] }. А затем он определяет свой "REPEAT" [RPT] и показывает, что мы можем определить любую примитивную рекурсивную функцию с помощью набора "последователь-повтор" { [ 0 ], [ ' ], [RPT] } (где диапазон [RPT] не может включать себя. Если это так, мы получаем то, что называется оператором mu (см. также mu рекурсивные функции ) (стр. 213)):

Любая общая рекурсивная функция может быть вычислена программным компьютером, использующим только операции [ 0 ], [ ' ], [ RPT ], если мы позволим операции RPT лежать в ее собственном диапазоне ... [однако] в общем случае операция RPT не могла бы быть инструкцией в конечной части машины... [если бы это было так] это могло бы исчерпать любой конкретный объем памяти, разрешенный в конечной части машины. Операции RPT требуют бесконечных собственных регистров, в общем случае... и т. д.» (стр. 214)

Шёнхаге (1980) разработал свою вычислительную модель в контексте «новой» модели, которую он назвал моделью модификации машины хранения (SMM), его разновидностью указателя . Его разработка описала модель RAM ( машина с произвольным доступом ) с замечательным набором инструкций, не требующим никаких операндов вообще, за исключением, возможно, «условного перехода» (и даже его можно было достичь без операнда):

«...версия RAM0 заслуживает особого внимания из-за своей чрезвычайной простоты; ее набор инструкций состоит всего из нескольких однобуквенных кодов, без какой-либо (явной) адресации» (стр. 494)

Интересно, как это сделал Шёнхаге. Он (i) разбивает обычный регистр «адрес:датум» на две части: «адрес» и «датум», и (ii) генерирует «адрес» в определенном регистре n, к которому инструкции конечного автомата (т. е. «машинный код») будут иметь доступ, и (iii) предоставляет регистр «аккумулятор» z , где должны происходить все арифметические операции.

В его конкретной модели RAM0 есть только две «арифметические операции» – «Z» для «установки содержимого регистра z в ноль» и «A» для «прибавления единицы к содержимому регистра z ». Единственный доступ к адресному регистру n осуществляется через инструкцию копирования из A в N, называемую «установка адреса n ». Чтобы сохранить «данные» в аккумуляторе z в заданном регистре, машина использует содержимое n для указания адреса регистра и регистра z для предоставления данных, которые должны быть отправлены в регистр.

Особенности: Первая особенность Schönhage RAM0 заключается в том, как он «загружает» что-либо в регистр z : регистр z сначала предоставляет адрес регистра, а затем, во-вторых, получает данные из регистра — форма косвенной «загрузки». Вторая особенность заключается в спецификации операции COMPARE. Это «переход, если регистр-аккумулятор z = ноль» (а не, например, «сравнить содержимое z с содержимым регистра, на который указывает n »). Очевидно, если тест не пройден, машина пропускает следующую инструкцию, которая всегда должна быть в форме «goto λ», где «λ» — адрес перехода. Инструкция — «сравнить содержимое z с нулем » отличается от модели Schonhage successor-RAM1 (или любой другой известной модели-преемника) более традиционной «сравнить содержимое регистра z с содержимым регистра a на равенство».

В первую очередь для справки — это модель ОЗУ, а не модель контрмашины — ниже приведен набор инструкций Schönhage RAM0:

Опять же, приведенный выше набор инструкций предназначен для машины с произвольным доступом , ОЗУ  – счетчиковой машины с косвенной адресацией; инструкция «N» позволяет осуществлять косвенное сохранение аккумулятора, а инструкция «L» позволяет осуществлять косвенную загрузку аккумулятора.

Несмотря на свою необычность, модель Шёнхаге показывает, как набор инструкций «регистр-регистр» или «чтение-модификация-запись» обычной счетной машины можно свести к простейшей форме с 0 параметрами.

• Булос, Джордж ; Берджесс, Джон П.; Джеффри , Ричард (2007) [1974]. Вычислимость и логика (5-е изд.). Кембридж, Англия: Cambridge University Press . ISBN 978-0-521-87752-7.Оригинальный текст Булоса-Джеффри был значительно переработан Берджессом: он стал более продвинутым, чем вводный учебник. Модель «машины Абак» подробно описана в Главе 5 «Вычислимость Абак» ; это одна из трех моделей, которые были подробно рассмотрены и сравнены — машина Тьюринга (все еще в исходной форме 4-кортежа Булоса) и рекурсия — две другие.

• Катланд, Найджел (1980). Вычислимость: Введение в теорию рекурсивных функций (PDF) . Cambridge University Press . ISBN 0521223849. Получено 7 ноября 2023 г. .

• Фишер, Патрик К.; Мейер , А. Р .; Розенберг, Арнольд Л. (1968), «Счетные машины и счетные языки», Математическая теория систем , 2 (3): 265–283 , doi :10.1007/bf01694011, MR  0235932, S2CID  13006433Разрабатывает теоремы об иерархии времени и иерархии пространства для счетных машин, аналогичные иерархиям для машин Тьюринга.
• Дональд Кнут (1968), Искусство программирования компьютеров , второе издание 1973, Эддисон-Уэсли, Рединг, Массачусетс. См. страницы 462-463, где он определяет «новый вид абстрактной машины или «автомата», который имеет дело со связанными структурами».
• Иоахим Ламбек (1961, получено 15 июня 1961), Как программировать бесконечный абак , Математический вестник, т. 4, № 3. Сентябрь 1961 г., страницы 295–302. В своем Приложении II Ламбек предлагает «формальное определение „программы“». Он ссылается на Melzak (1961) и Kleene (1952) Введение в метаматематику .
• ZA Melzak (1961, получено 15 мая 1961), Неформальный арифметический подход к вычислимости и вычислениям , Canadian Mathematical Bulletin , т. 4, № 3. Сентябрь 1961 г., страницы 279-293. Melzak не приводит ссылок, но признает «польза бесед с докторами Р. Хэммингом, Д. Макилроем и В. Высотсом из Bell Telephone Laborators и с доктором Х. Вангом из Оксфордского университета».
• Марвин Мински (1961). «Рекурсивная неразрешимость проблемы Поста «Тэг» и другие темы в теории машин Тьюринга». Annals of Mathematics . 74 (3): 437– 455. doi :10.2307/1970290. JSTOR  1970290.
• Марвин Мински (1967). Вычисления: Конечные и бесконечные машины (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc.В частности, см. главу 11: Модели, подобные цифровым компьютерам и главу 14: Очень простые основы вычислимости . В первой главе он определяет «Программные машины», а в последней главе обсуждает «Универсальные программные машины с двумя регистрами» и «...с одним регистром» и т. д.

• Шепердсон, Джон К.; Стерджис, Х. Э. (1963). «Вычислимость рекурсивных функций». Журнал ACM . 10 (2): 217– 255. doi :10.1145/321160.321170.Чрезвычайно ценная справочная статья. В своем Приложении A авторы цитируют 4 других со ссылкой на "Минимальность инструкций, используемых в 4.1: Сравнение с похожими системами".
• Капенгст, Хайнц, Eine Abstrakte programmgesteuerte Rechenmaschine' , Zeitschrift Fur Mathematische Logik und Grundlagen der Mathematik: 5 (1959), 366-379.
• Ершов, А. П. Об операторных алгоритмах , ДАН 122 (1958), 967-970. Перевод на английский язык, Автомат. Экспресс 1 (1959), 20-23.
• Петер, Rózsa Graphschemata und recursive Funktionen , Dialectica 12 (1958), 373.
• Гермес, Ганс Die Universalität programmgesteuerter Rechenmaschinen. Матем.-Физ. Semesterberichte (Геттинген) 4 (1954), 42–53.
• А. Шёнхаге (1980), Машины модификации памяти , Общество промышленной и прикладной математики, SIAM J. Comput. Vol. 9, No. 3, август 1980 г. При этом Шёнхаге показывает эквивалентность своей МММ с «преемницей RAM» (машиной с произвольным доступом) и т. д.
• Rich Schroeppel , май 1972 г., «Двухсчетная машина не может вычислить 2 ^N », Массачусетский технологический институт, Лаборатория искусственного интеллекта, Меморандум по искусственному интеллекту № 257. Автор ссылается на Minsky 1967 и отмечает, что « Фрэнсис Яо независимо доказала невычислимость, используя аналогичный метод в апреле 1971 г.».
• Питер ван Эмде Боас , Модели машин и симуляции, стр. 3–66, опубликовано в:

Ян ван Леувен , редактор. Справочник по теоретической информатике. Том A: Алгоритмы и сложность , MIT PRESSElsevier, 1990. ISBN 0-444-88071-2 (том A). QA 76.H279 1990. 

Трактовка SMM ван Эмде Боаса представлена ​​на стр. 32-35. Эта трактовка проясняет Schōnhage 1980 — она близко следует, но немного расширяет трактовку Schōnhage. Обе ссылки могут быть необходимы для эффективного понимания.

• Хао Ван (1957), Вариант теории вычислительных машин Тьюринга , JACM (Журнал Ассоциации вычислительной техники) 4; 63–92. Представлено на заседании Ассоциации 23–25 июня 1954 г.