Модель противомашины
Существует множество вариантов встречной машины , среди них машины Гермеса , Ершова , Петера , Минского , Ламбека , Шепердсона и Стерджиса, а также Шенхаге . Они объяснены ниже.
Модели более подробно
[ редактировать ]1954: модель Гермеса
[ редактировать ]Шепердсон и Стерджис (1963) отмечают, что «доказательство этой универсальности [цифровых компьютеров для машин Тьюринга]… кажется, было впервые записано Гермесом, который показал в [7 – их номер ссылки], как идеализированный компьютер может быть запрограммировано так, чтобы дублировать поведение любой машины Тьюринга» и: «Подход Капенгста интересен тем, что он дает прямое доказательство универсальности современных цифровых компьютеров, по крайней мере, когда он идеализирован до такой степени, что допускает бесконечность памяти. регистры, каждый из которых способен хранить слова произвольной длины» . [1]
Единственные две арифметические инструкции:
- Последующая операция
- Проверка двух чисел на равенство
Остальные операции представляют собой переходы из регистра в аккумулятор или из аккумулятора в регистр или тестовые переходы.
Статья Капенгста написана на немецком языке; В переводе Шепердсона и Стерджиса используются такие термины, как «мельница» и «приказы».
Машина содержит «мельницу» (аккумулятор). Капенгст обозначает свою мельницу/аккумулятор символом «бесконечности», но в следующем описании мы будем использовать букву «А». Он также содержит «регистр заказов» («заказ» означает «инструкция», а не «последовательность»). (Это использование произошло из описания «... электронного вычислительного прибора» в отчете Беркса-Голдстайна-фон Неймана (1946).) Регистром приказов/инструкций является регистр «0». И, хотя это не ясно из изложения Шепердсона и Стерджиса, модель содержит «регистр расширения», обозначенный Капенгстом как «бесконечно-простое число»; мы будем использовать «Е».
Инструкции хранятся в регистрах:
- «...так что машина, как настоящий компьютер, способна выполнять арифметические операции над своей собственной программой» (стр. 244).
Таким образом, эта модель на самом деле является машиной с произвольным доступом . Далее «[ r ]» обозначает «содержимое» регистра r и т. д.
| Действие: | Описание | ||
|---|---|---|---|
| Д1: | С(г, А) | [ р ] → А, [ р ] → р | Скопируйте содержимое регистра r в аккумулятор A. |
| Д2: | Машина) | [ А ] → р, [ А ] → А | Скопируйте содержимое аккумулятора A в регистр r. |
| С1: | 0 → А | Нулевой (очистить) аккумулятор A | |
| А1: | П(А) | [ А ] + 1 → А | Увеличить (прибавить 1) содержимое аккумулятора A. |
| Ф1: | Дж(А) [Е1] | ЕСЛИ [ A ] = 0, ТО переходим к «Выходу 1» | Переход, если содержимое аккумулятора A = 0 |
| Г1: | Вкл.(А) | ЕСЛИ [ A ] = [ r ] ТО 0 → < A > ИНАЧЕ 1 → A | Очистить содержимое A, если содержимое A = содержимое r, иначе «установить» A=1. |
| Г2: | О'(А) | 1 → А | «Установить» содержимое A = 1 |
Шепердсон и Стерджис (1963) удаляют мельницу/аккумулятор A и сокращают инструкции Капенгста до «копирования между регистрами», арифметических операций «приращения» и «сравнения между регистрами». Обратите внимание, что декремента нет . Эту модель, почти дословно, можно найти у Минского (1967); подробнее см. в разделе ниже.
| Действие: | Описание: | ||
|---|---|---|---|
| а: | П(А) | [ А ] + 1 → А | Увеличить (прибавить 1) содержимое аккумулятора A. |
| д. | C(r j , r k ) | [р j ] → р k , [р j ] → р j | Скопировать содержимое регистра r j в регистр r k |
| е: | J(r) [E1] | ЕСЛИ [ r ] = 0 ТО переход к «Выходу 1» ЛИБО следующая инструкция | Переход, если содержимое регистра r = 0 |
| с: | E( rj , rk ) | ЕСЛИ [ r j ] = [ r k ] ТО 0 → E ИНАЧЕ 1 → E | Очистить содержимое регистра E, если содержимое r j = содержимое rk , иначе «установить» E=1. |
1958: Класс операторных алгоритмов Ершова.
[ редактировать ]Шепердсон и Стерджис (1963) отмечают, что модель Эрсова позволяет хранить программу в регистрах. Они утверждают, что модель Ерсова такова:
| Действие: | Описание: | ||
|---|---|---|---|
| д. | C( rj , rk ) | [р j ] → р k , [р j ] → р j | Скопировать содержимое регистра r j в регистр r k |
| д'. | C' ( rj , rk ) | [ р j ] +1 → р k , [ р j ] → р j | Скопировать увеличенное содержимое регистра r j в регистр r k. |
| и. | Дж[Е1] | Перейти к «Выходу 1» | Безусловный переход к «Выходу №1» |
| е*: | J(rj , rk ) [E1, E2] | ЕСЛИ [ r j ] ≤ [ r k ] ТО переходим к «Выходу 1», ЛИБО переходим к «Выходу 2» | Переход к выходу из E1, если содержимое регистра r j меньше или равно содержимому rk , иначе переход к E=2. |
1958: «Лечение» Петера.
[ редактировать ]Шепердсон и Стерджис (1963) отмечают, что «лечение» Петера (здесь оно не слишком конкретно) эквивалентно инструкциям, показанным в следующей таблице. Они особо комментируют эти инструкции, что:
- «с точки зрения возможно более быстрого доказательства вычислимости всех частично рекурсивных функций, метод Петера, пожалуй, лучший; для доказательства их вычислимости с помощью машин Тьюринга необходим дальнейший анализ операции копирования в том же духе, который мы взяли выше». [2]
| Действие: | Описание: | ||
|---|---|---|---|
| с: | На) | 0 → [ п ] | Нулевой (очистить) регистр n |
| д. | С(м,п) | [ м ] → п, [ м ] → [ м ] | Скопировать содержимое регистра m в регистр n. |
| д'. | С'(м,п) | [ м ] + 1 → [ п ], [ м ] → [ м ] | Скопировать увеличенное содержимое регистра m в регистр n. |
| и. | J(m, n)[E1, E2] | ЕСЛИ [m]=[n] переход к E1 ELSE переход к E2 | Условный переход к E1, если содержимое m равно содержимому n, иначе переход к E2. |
1961: Модель Мински частично рекурсивной функции сведена к «программе» всего из двух инструкций.
[ редактировать ]В своем исследовании проблем Эмиля Поста ( система тегов ) и Гильберта 10-й проблемы ( проблемы Гильберта , диофантово уравнение ) Минский привел к следующему определению:
- «интересная основа рекурсивной теории функций, включающая программы только простейших арифметических операций» (Минский (1961), стр. 437).
Его «Теорема Ia» утверждает, что любая частично-рекурсивная функция представлена «программой, оперирующей двумя целыми числами S1 и S2 с использованием инструкций Ij форм (ср. Мински (1961), стр. 449):
| Действие: | Описание: | ||
|---|---|---|---|
| а. | ДОБАВИТЬ (r, I j1 ) | [ р ] + 1 → р; перейти к инструкции I j1 . | Увеличьте (добавьте 1) содержимое регистра r и перейдите к инструкции I j1 . |
| б. | СУБ (r, I j1 , I j2 ) | Если [ r ] ≤ 0, ТОГДА перейдите к инстр. Я j2 ELSE [ r ] -1 → r и иду в инстр. я j1 | ЕСЛИ содержимое регистра r равно нулю, ТОГДА переход к инструкции I j2 ; ИНАЧЕ уменьшить (вычесть 1) содержимое регистра r и перейти к instr. Я j1 . |
Первая теорема является контекстом второй «Теоремы IIa», согласно которой
- «... представляет любую частично рекурсивную функцию программы, работающей с одним целым числом S [содержащимся в одном регистре r1] с использованием инструкций I j форм»:
| Действие: | Описание: | ||
|---|---|---|---|
| а. | MULT (K j , I j1 ) | [ r1 ]*K j → r1; перейти к инструкции I j1 . | Умножить содержимое регистра r1 на константу K j |
| б. | DIV ( Kj , Ij1 , Ij2 ) | [r1]/Kj = 0, затем перейдите к инструкции I j2, иначе перейдите к I j1 . | Если при делении содержимого регистра 1 на константу K j остатка нет, то инстр. Я j1 еще инстр. я j2 |
В этой второй форме машина использует числа Гёделя для обработки «целого числа S». Он утверждает, что первой машине/модели не нужно этого делать, если ей доступны 4 регистра.
1961: Модель Мелзака: одна троичная инструкция со сложением и правильным вычитанием.
[ редактировать ]- «Наша цель — описать примитивное устройство, которое будет называться Q-машиной, которое достигает эффективной вычислимости посредством арифметики, а не логики. Его три операции — подсчет, сравнение неотрицательных целых чисел и передача» (Мельзак ( 1961) с. 281)
Если мы используем контекст его модели, «подсчет» означает «добавление путем последовательных приращений» (бросание камешка) или «вычитание путем последовательных уменьшений»; перенос означает перемещение (а не копирование) содержимого из отверстия А в отверстие Б, а сравнение чисел самоочевидно. Похоже, это смесь трех базовых моделей.
Физическая модель Мелзака — это дыры {X, Y, Z и т. д.} в земле вместе с неограниченным запасом камешков в специальной яме S (Sink или Supply, или и то, и другое? Мелзак не говорит).
- «Q-машина состоит из неопределенно большого числа ячеек : S, A1, A2, ..., неопределенно большого количества счетчиков, распределенных между этими точками, программы и оператора, единственной целью которого является выполнение инструкций. Первоначально все из локаций, кроме конечного числа... пусты и каждая из оставшихся содержит конечное число фишек » (с. 283, жирный шрифт добавлен).
Инструкция представляет собой одну «троичную операцию», которую он называет «XYZ»:
- «XYZ» обозначает операцию
- Посчитайте количество камешков в лунке Y ,
- поместите их обратно в Y ,
- попытайтесь удалить это же число из X. отверстия ЕСЛИ это невозможно, поскольку при этом отверстие X опустеет , ТОГДА ничего не делайте и переходите к инструкции #I; ЕЩЕ,
- удалить количество Y из X и (iv) перенести их, т. е. , к количеству в отверстии Z. добавить
Из всех возможных операций некоторые запрещены, как показано в таблице ниже:
| Допустимый | Инструкция | Отверстие "Х" | Отверстие "Y" | Отверстие "Z" | Значение инструкции |
|---|---|---|---|---|---|
| НЕТ | ХХХ | ||||
| ХХ | ([ X ] - [ X ])=0 → X | [Y] + [X] → Y | [ Я ] → Я | Все камешки X взяты из X и добавлены в Y. | |
| XXS | ([ X ] - [ X ])=0 → X | [Д] → Д | [ Я ] → Я | Все камешки X взяты из X и помещены в раковину/источник S. | |
| НЕТ | XYX | ||||
| XYY | [ Икс ] - [ Y ] → Икс | [Y] + [Y] → Y | [ Я ] → Я | Количество камешков Y, взятых из X и помещенных в Y, удваивает количество Y. | |
| XYS | |||||
| НЕТ | XSX | ||||
| НЕТ | XSY | ||||
| НЕТ | XSS | ||||
| XYZ | [ Икс ] - [ Y ] → Икс | [Д] → Д | [ Z ] + [ Y ] → Z | Количество камешков Y, взятых из X и добавленных к Z, | |
| ПРИЧИНА | [ Икс ] → Икс | [Y] + [Y] → Y | [ Я ] → Я | Количество камешков Y, взятое из S и добавленное к Y, удвоив количество Y. | |
| ТЫ | [ Икс ] → Икс | [Д] → Д | [ Z ] + [ Y ] → [ Z ] | Количество камешков Y, взятых из S и добавленных к Z. |
Некоторые наблюдения о модели Мелзака :
- Если все дырки начинаются с 0, то как нам увеличить число? Очевидно, это невозможно; в одной лунке должен находиться один камешек.
- Условный «переход» происходит в каждом экземпляре типа XYZ, потому что: если его невозможно выполнить из-за того, что в X недостаточно фишек/камешков, происходит переход; в противном случае, если это можно выполнить, оно будет выполнено, и инструкции перейдут к следующим по порядку.
- Ни SXY, ни XXY не могут вызвать скачок, поскольку оба всегда могут быть выполнены.
- Мелзак добавляет в свою модель косвенность (см. машина с произвольным доступом ) и приводит два примера ее использования. Но дальше он этого не преследует. Это первый подтвержденный случай «косвенности», появившийся в литературе.
- Обе статьи - З. Александра Мельзака ( Математическое соревнование Уильяма Лоуэлла Патнэма , победитель 1950 г.) была получена 15 мая 1961 г. и Иоахима Ламбека , полученная месяцем позже, 15 июня 1961 г., - содержатся в одном и том же томе, одна за другой.
- Верно ли утверждение Мельзака? – что эта модель «настолько проста, что ее работу, вероятно, сможет понять средний школьник после нескольких минут объяснения» (с. 282)? Читателю придется принять решение.
1961: Модель «абака» Ламбека: атомизация модели Мельзака до X+, X- с помощью теста
[ редактировать ]Оригинальная модель «абака» Ламбека (1962 г.):
Ламбек ссылается на статью Мельзака. Он разбивает единственную 3-параметрическую операцию Мелзака (на самом деле 4, если считать адреса инструкций) на 2-параметрическое приращение «X+» и 3-параметрическое декремент «X-». Он также дает как неформальное, так и формальное определение «программы». Эта форма практически идентична модели Мински (1961) и была принята Булосом, Берджесом и Джеффри (2007 , стр. 45, Abacus Computability).
| Действие: | Описание: | ||
|---|---|---|---|
| а. | Х+ (г, Iа ) | [ р ] + 1 → р; перейти к инструкции I a . | Увеличить (добавить 1) содержимое регистра r |
| б. | Х- (р, я а , я б ) | Если [ r ] ≤ 0, перейдите к instr.I b else [ r ]-1 → r и перейдите к instr. Я | Сначала проверьте ноль, затем уменьшите (вычтите 1) содержимое регистра r. |
Модель счетов Булоса, Берджесса и Джеффри : [3]
В различных изданиях, начиная с 1970 г., авторы используют модель «бесконечных счетов» Ламбека (1961). В этой серии статей Википедии используется их символика, например: «[ r ] +1 → r» «содержимое регистра, обозначенного как номер 'r' плюс 1, заменяет содержимое [помещается в] регистр номер 'r'» .
Они используют имя Ламбека «абак», но следуют модели «камешки в отверстиях» Мельзака, модифицированной ими до модели «камни в ящиках». Как и исходная модель Ламбека на счетах, их модель сохраняет использование непоследовательных инструкций Мински (1961) - в отличие от «традиционного» компьютерного последовательного выполнения инструкций по умолчанию, следующая инструкция I a содержится внутри инструкции.
Обратите внимание, однако, что BB и BBJ не используют переменную «X» в мнемонике с определяющим параметром (как показано в версии Ламбека) — т. е. «X+» и «X-» — а, скорее, мнемоника инструкций определяет регистрируется, например, «2+» или «3-»:
| Действие: | Описание: | ||
|---|---|---|---|
| а1. | 1+ (от меня к ) | [r1] + 1 → r1, затем перейдите к инструкции Ia . | Увеличить (добавить 1) содержимое регистра №1. |
| б1. | 1- (я а , я б ) | Если [ r1 ] ≤ 0, ТО перейдите к I b else [ r1 ] -1 → r1 и перейдите к I a . | Перейти к инструкции I b , если содержимое регистра r1 равно нулю, ИЛИ уменьшить (вычесть 1) содержимое регистра № 1. |
1963: модель Шепердсона и Стерджиса
[ редактировать ]Шепердсон и Стерджис (1963) ссылаются на Мински (1961), как это было для них в виде отчета лаборатории Линкольна Массачусетского технологического института :
В разделе 10 мы показываем, что теоремы (включая результаты Минского [21, ссылки на них]) о вычислении частично рекурсивных функций с помощью одной или двух лент могут быть довольно легко получены из одной из наших промежуточных форм.
- Шепердсон и Стерджис (1963 , стр. 218)
Их модель находится под сильным влиянием модели и духа Хао Ванга (1957) и его B-машины Ванга (см. также « Машина Пост-Тьюринга» ). Они «подводят итог, говоря»:
... мы попытались сделать еще один шаг вперед в «сближении» между практическими и теоретическими аспектами вычислений, предложенном и начатом Вангом.
Неограниченная регистрация машины URM : [4] Эта их «самая гибкая машина... состоит из счетной последовательности регистров с номерами 1, 2, 3,..., каждый из которых может хранить любое натуральное число... Однако каждая конкретная программа включает в себя только конечное число эти регистры» (с. 219). Другими словами, количество регистров потенциально бесконечно, и «размер» каждого регистра бесконечен.
Они предлагают следующий набор инструкций: [1] и следующие «Примечания»:
| Модель УРМ: | Действие: | Описание: | |
|---|---|---|---|
| а. | П (п) | [ р ] + 1 → р | Увеличить (добавить 1) содержимое регистра r |
| б. | Д(н) | [ р ] - 1 → р | Уменьшить (вычесть 1) содержимое регистра r |
| с: | На) | 0 → р | Нулевой (очистить) регистр r |
| д. | С(м,п) | [ р j ] → р k , [ р j ] → р j , | Скопировать содержимое регистра r j в регистр r k |
| и. | Дж[Е1] | Перейти к «Выходу 1» | Безусловный переход к «Выходу №1» |
| е: | J(r) [E1] | ЕСЛИ [ r j ] = 0 ТО переход к «Выходу 1» ЛИБО следующая инструкция | ЕСЛИ содержимое регистра r = 0, то переход к инструкции «Выход 1», иначе далее.
инструкция |
Примечания.
- Этот набор инструкций выбран из соображений простоты программирования и вычисления частично рекурсивных функций, а не из экономии; в разделе 4 показано, что этот набор эквивалентен меньшему набору.
- В этом списке бесконечно много инструкций, поскольку m, n [содержимое rj и т. д.] варьируются во всех положительных целых числах.
- В инструкциях a, b, c, d предполагается, что содержимое всех регистров, кроме n, остается неизменным; в инструкциях е, f содержимое всех регистров не изменяется (с. 219).
Действительно, они показывают, как еще уменьшить этот набор до следующего (для бесконечного числа регистров, каждый из которых имеет бесконечный размер):
| Уменьшенный URM: | Действие: | Описание: | |
|---|---|---|---|
| а1. | П(р) | [ р ] + 1 → р | Увеличить (добавить 1) содержимое регистра r |
| б1. | Д(н) | [ р ] - 1 → р | Уменьшить (вычесть 1) содержимое регистра r |
| ~f1: | J(r) [E1] | ЕСЛИ [ r ] ≠ 0 ТО переходим к «Выходу 1» | Если содержимое регистра m ≠ 0, ТОГДА перейдите к инструкции «Выход 1», ЛИБО продолжайте. |
Машина с ограниченным регистром LRM : здесь они ограничивают машину конечным числом регистров N, но они также позволяют «вводить» или удалять больше регистров, если они пусты (см. стр. 228). Они показывают, что для инструкции удаления регистра не требуется пустой регистр.
Однорегистровая машина SRM : здесь реализована система тегов Эмиля Поста и тем самым разрешена запись только до конца строки и стирание с начала. На рисунке 1 это показано в виде ленты с головкой чтения слева и головкой записи справа, и она может перемещать ленту только вправо. «А» — их «слово» (с. 229):
- а. P(i) ;добавьте ai в конец A
- б. D ;удалить первую букву A
- е'. Ji[E1] ;Если A начинается с ai, перейдите к выходу 1.
Они также предоставляют модель в виде «стопки карт» с символами { 0, 1 } (стр. 232 и Приложение C, стр. 248):
- добавить карту вверху напечатано 1
- добавить карту вверху напечатано 0
- удалить нижнюю карту; если напечатано 1, переходите к инструкции m, иначе к следующей инструкции.
1967: Мински «Простая универсальная база для программного компьютера».
[ редактировать ]В конце концов, в задаче 11.7-1 Мински отмечает, что из крошечной коллекции можно сформировать множество баз вычислений:
- «Многие другие комбинации типов операций [ 0 ], [ ' ], [ - ], [ O- ], [ → ] и [RPT ] образуют универсальный базис. Найдите некоторые из этих базисов. Какие комбинации трех операций не являются универсальным базисом ? Придумать еще какие-нибудь операции..." (с. 214)
Ниже приведены определения различных инструкций, которые он рассматривает:
| Действие: | Описание: | ||
|---|---|---|---|
| а. | [ 0 ] | 0 → р | Нулевой (очистить) регистр r |
| б. | [ ' ] | [ р ] + 1 → р | Увеличить (добавить 1) содержимое регистра r (апостроф ' означает «преемник») |
| в. | [ - ] | IF [ r ] = 0 THEN переход к инструкции z ELSE следующая инструкция | Проверить регистр r и перейти к инструкции z, если его содержимое равно нулю; если нет, уменьшите (вычтите 1) содержимое регистра r. |
| д. | [О-] | Если [ r ] ≠ 0 THEN [ r ] -1 → r ELSE следующая инструкция | ЕСЛИ содержимое регистра r не равно нулю, уменьшаем содержимое регистра r и переходим к z-й инструкции, иначе, если 0, то следующая инструкция |
| и. | [ → ] | [р j ] → р k , [р j ] → р j | Скопировать содержимое регистра r j в регистр r k |
| ф. | [ РПТ] | RPT a:[m,n]. Повтор не может работать в пределах своего диапазона. | Делайте, пока содержимое регистра [ r ] = 0: Повторяйте инструкции от m до n. Когда [ r ] = 0, переходите к следующей инструкции. |
| г. | [ Ч ] | ОСТАНОВКА | |
| час | перейти к (г) | Перейти к инструкции z | Безусловный переход к инструкции z |
| я. | [ ≠ ] | Если [ r j ] ≠ [ r k ] ТО переход к z-й инструкции, ИЛИ следующая инструкция | Условный переход: если содержимое регистра r j не равно содержимому регистра r k, ТОГДА переход к инструкции z, ИНАЧЕ следующая инструкция. |
| Дж. | [ РПТ]* | RPT a:[m,n]. Повтор может работать в пределах своего диапазона. | * Примечание: RPT должен находиться в бесконечном регистре. |
Мински (1967) начинает с модели, состоящей из трех операций плюс HALT:
- { [ 0 ], [ ' ], [ - ], [ Ч ] }
Он отмечает, что мы можем обойтись без [ 0 ], если допустим определенный регистр, например, w уже «пустой» (Минский (1967), стр. 206). Позже (стр. 255 и далее) он сжимает три { [ 0 ], [ ' ], [ - ] } в два { [ ' ], [ - ] }.
Но он признает, что модель станет проще, если добавить несколько [псевдо]-инструкций [ O- ] (комбинированных [ 0 ] и [ - ]) и «go(n)». Он строит «go(n)» из регистра w, заранее установленного в 0, так что [O-] ( w , (n)) является безусловным переходом.
В разделе 11.5 «Эквивалентность программных машин с общерекурсивными функциями» он вводит две новые подпрограммы:
- ф. [ → ]
- Дж. [ ≠ ]
- Переход, если не равен»: IF [ r j ] ≠ [ r k ] THEN переход к z-й инструкции ELSE следующей инструкции
Он продолжает показывать, как заменить набор «преемник-предшественник» { [ 0 ], [ ' ], [ - ] } на набор «равенство-преемник» { [ 0 ], [ ' ], [ ≠ ] }. А затем он определяет свой «ПОВТОР» [RPT] и показывает, что мы можем определить любую примитивно-рекурсивную функцию с помощью набора «повторение-преемника» { [ 0 ], [ ' ], [RPT] } (где диапазон [ RPT ] не может включать себя. Если это так, мы получаем так называемый оператор mu (см. также рекурсивные функции mu ) (стр. 213)):
- Любая общерекурсивная функция может быть вычислена с помощью программного компьютера, используя только операции [0], ['], [RPT], если мы позволяем операции RPT находиться в ее собственном диапазоне... [однако] в целом операция RPT не может быть инструкцией в конечной части машины... [если бы это было так] это могло бы исчерпать любой конкретный объем памяти, разрешенный в конечной части машины. Операции RPT требуют собственных бесконечных регистров, в общем... и т. д.» (стр. 214).
1980: 0-параметрическая модель Шенхаге RAM0.
[ редактировать ]Шёнхаге (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 с нулем » отличается от модели преемника Шонхаге-RAM1 (или любых других известных моделей-преемников) с более традиционной «сравнить содержимое регистра z с содержимым регистра a на предмет равенства».
В первую очередь для справки – это модель RAM, а не модель противомашины – следующий набор команд Schönhage RAM0:
| Инструкция | Действие: | Описание: | |
|---|---|---|---|
| 1 | С | 0 → г | Очистить регистр-аккумулятор z |
| 2 | А | [ z ] + 1 → z | Увеличить содержимое регистра-аккумулятора z. |
| 3 | Н | [ z ] → п, [ z ] → z | «Установить адрес n»: скопировать содержимое аккумулятора z в адресный регистр n. |
| 4 | л | [ [ z ] ] → z | Косвенно скопировать в аккумулятор z содержимое регистра, на который указывает аккумулятор z. |
| 5 | С | [ z ] → [ п ] | Косвенно сохранить содержимое аккумулятора z в регистр, на который указывает содержимое адресного регистра n. |
| 6 | С | Если [ z ] = 0 пропустите следующую инструкцию (которая должна быть инструкцией перехода I λ ) | Если содержимое аккумулятора z = 0, ТОГДА пропустите следующую инструкцию, иначе продолжайте. |
| 7 | перейти к I λ | Инструкция безусловного перехода (перехода) I λ | Инструкция безусловного перехода (перехода) I λ |
Опять же, приведенный выше набор команд предназначен для машины с произвольным доступом , ОЗУ — машины-счетчика с косвенной адресацией; инструкция «N» позволяет косвенно хранить аккумулятор, а инструкция «L» позволяет косвенно загружать аккумулятор.
Несмотря на свою необычность, модель Шенхаге показывает, как набор команд обычной счетчиковой машины «регистр-регистр» или «чтение-изменение-запись» может быть атомизирован до простейшей формы с 0 параметрами.
Ссылки
[ редактировать ]- ^ Jump up to: а б Шепердсон и Стерджис 1963 , с. 219.
- ^ Шепердсон и Стерджис 1963 , с. 246.
- ^ Булос, Берджесс и Джеффри 2007 , стр. 45. Вычислимость на счетах.
- ^ См. также Катленд (1980 , стр. 9).
Библиография
[ редактировать ]- Булос, Джордж ; Берджесс, Джон П .; Джеффри, Ричард (2007) [1974]. Вычислимость и логика (5-е изд.). Кембридж, Англия: Издательство Кембриджского университета . ISBN 978-0-521-87752-7 . Оригинальный текст Булоса-Джеффри был тщательно переработан Берджессом: он более продвинут, чем вводный учебник. Модель «счетной машины» подробно описана в главе 5 «Вычислимость счетов» ; это одна из трех моделей, которые широко рассматриваются и сравниваются: машина Тьюринга (все еще в исходной четырехкортежной форме Булоса) и две другие рекурсивные модели.
- Катленд, Найджел (1980). Вычислимость: введение в рекурсивную теорию функций (PDF) . Издательство Кембриджского университета . ISBN 0521223849 . Проверено 7 ноября 2023 г.
- Фишер, Патрик С .; Мейер, Арканзас ; Розенберг, Арнольд Л. (1968), «Счетные машины и встречные языки», Теория математических систем , 2 (3): 265–283, doi : 10.1007/bf01694011 , MR 0235932 , S2CID 13006433 . Разрабатывает теоремы временной и пространственной иерархии для счетных машин, аналогичные иерархиям для машин Тьюринга.
- Дональд Кнут (1968), Искусство компьютерного программирования , второе издание, 1973 г., Аддисон-Уэсли, Ридинг, Массачусетс. См. страницы 462–463, где он определяет «новый вид абстрактной машины или «автомата», который имеет дело со связанными структурами».
- Иоахим Ламбек (1961, получено 15 июня 1961 г.), Как запрограммировать бесконечные счеты , Mathematical Bulletin, vol. 4, нет. 3. Сентябрь 1961 г., страницы 295–302. В своем Приложении II Ламбек предлагает «формальное определение «программы». Он ссылается на Melzak (1961) и Kleene (1952) « Введение в метаматематику» .
- З.А. Мельзак (1961, получено 15 мая 1961 г.), Неофициальный арифметический подход к вычислимости и вычислениям , Canadian Mathematical Bulletin , vol. 4, нет. 3. Сентябрь 1961 г., страницы 279–293. Мельзак не приводит никаких упоминаний, но признает «пользу бесед с докторами Р. Хэммингом, Д. Макилроем и В. Высоцем из телефонных лабораторий Bell и с доктором Х. Вангом из Оксфордского университета».
- Марвин Мински (1961). «Рекурсивная неразрешимость проблемы Поста о «теге» и других тем теории машин Тьюринга». Анналы математики . 74 (3): 437–455. дои : 10.2307/1970290 . JSTOR 1970290 .
- Марвин Мински (1967). Вычисления: конечные и бесконечные машины (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc. В частности, см. главу 11: Модели, подобные цифровым компьютерам , и главу 14: Очень простые основы вычислительности . В первой главе он дает определение «программным машинам», а в следующей главе обсуждает «универсальные программные машины с двумя регистрами» и «... с одним регистром» и т. д.
- Шепердсон, Джон К.; Стерджис, HE (1963). «Вычислимость рекурсивных функций». Журнал АКМ . 10 (2): 217–255. дои : 10.1145/321160.321170 . Чрезвычайно ценный справочный документ. В Приложении А авторы цитируют еще 4 со ссылкой на «Минимальность инструкций, используемых в 4.1: Сравнение с аналогичными системами».
- Капенгст, Хайнц, Абстрактная вычислительная машина с программным управлением» , Журнал математической логики и основ математики: 5 (1959), 366–379.
- Ershov, A. P. On operator algorithms , (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
- Петер, Рожа Графовые схемы и рекурсивные функции , Dialectica 12 (1958), 373.
- Гермес, Ганс Универсальность вычислительных машин с программным управлением. Матем.-Физ. Отчеты за семестр (Геттинген) 4 (1954), 42–53.
- А. Шонхаге (1980), Машины для модификации памяти , Общество промышленной и прикладной математики, SIAM J. Comput. Том. 9, № 3, август 1980 г., в котором Шёнхаге показывает эквивалентность своего СММ «преемнику RAM» (машине произвольного доступа) и т. д.
- Рич Шреппель , май 1972 г., «Машина с двумя счетчиками не может вычислить 2». Н «, Массачусетский технологический институт, Лаборатория искусственного интеллекта, Памятка по искусственному интеллекту № 257. Автор ссылается на Мински, 1967 год, и отмечает, что « Фрэнсис Яо независимо доказала невычислимость, используя аналогичный метод в апреле 1971 года».
- Питер ван Эмде Боас , Модели машин и моделирование, стр. 3–66, появляются в:
- Ян ван Леувен , изд. Справочник по теоретической информатике. Том A: Алгоритмы и сложность , MIT PRESSElsevier, 1990. ISBN 0-444-88071-2 (том А). КА 76.H279 1990 г.
- Отношение ван Эмде Боаса к СММ представлено на стр. 32–35. Эта трактовка проясняет Шёнхаге 1980 — она близко следует, но немного расширяет трактовку Шёнхаге. Обе ссылки могут быть необходимы для эффективного понимания.
- Хао Ван (1957), Вариант теории вычислительных машин Тьюринга , JACM (Журнал Ассоциации вычислительной техники) 4; 63–92. Представлено на заседании Ассоциации 23–25 июня 1954 г.