Модель счетчика - Counter-machine model

Эта страница дополняет счетчик машина.

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

Внутри вида «счетчик» существует ряд разновидностей: модели Гермес (1954), Капхенгст (1957), Ершов (1958), Питер (1958), Минский (1961) и Минский (1967), Мелзак (1961), Ламбек (1961), Шепердсон и Стерджис (1963) и Schönhage (1980). Эти модели будут описаны более подробно ниже.

Подробнее о моделях

1954: модель Гермеса

Шепердсон и Стерджис отмечают, что «доказательство этой универсальности [цифровых компьютеров для машин Тьюринга] ... кажется, было впервые записано Гермесом, который показал в [7 - их ссылочный номер], как можно запрограммировать идеализированный компьютер. дублировать поведение любой машины Тьюринга »(Shepherdson and Sturgis, p. 219).

Шепердсон и Стерджис отмечают, что:

«Подход Капхенгста интересен тем, что он дает прямое доказательство универсальности современных цифровых компьютеров, по крайней мере, когда он идеализирован до степени допуска бесконечного количества регистров хранения, каждый из которых способен хранить произвольно длинные слова» (Shepherdson and Sturgis, p. 219)

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

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

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

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

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

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

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

Таким образом, эта модель на самом деле машина с произвольным доступом. Далее «[r]» обозначает «содержимое» регистра r и т. Д.

Действие:Описание
D1:С (г, А)[r] → A, [r] → rСкопируйте содержимое регистра r в аккумулятор A
D2:Машина)[A] → r, [A] → AСкопируйте содержимое аккумулятора A в регистр r
C1:О (А)0 → АНулевой (чистый) аккумулятор A
A1:P (А)[A] + 1 → AУвеличение (прибавление 1 к) содержимого аккумулятора A
F1:J (A) [E1]ЕСЛИ [A] = 0, ТО перейти к "Выходу 1"Перейти, если содержимое аккумулятора A = 0
G1:На)ЕСЛИ [A] = [r] ТО 0 → ИНАЧЕ 1 → AОчистить содержимое A, если содержимое A = содержимое r, иначе "установить" A = 1
G2:О '(А)1 → А"Установить" содержимое A = 1

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

Действие:Описание:
а:P (А)[A] + 1 → AУвеличение (прибавление 1 к) содержимого аккумулятора A
d.C (rj, рk)[ рj ] → rk, [ рj ] → rjСкопируйте содержимое регистра rj зарегистрировать гk
f:J (r) [E1]IF [r] = 0 ТО перейти к "Exit 1" ИНАЧЕ следующая инструкцияПерейти, если содержимое регистра r = 0
c:E (rj, рk)ЕСЛИ [rj ] = [гk ] ТОГДА 0 → E ELSE 1 → EОчистить содержимое регистра E, если содержимое rj = содержимое rk, иначе "установите" E = 1

1958: класс операторных алгоритмов Ершова

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

Действие:Описание:
d.C (rj,рk)[ рj ] → rk, [ рj ] → rjСкопируйте содержимое регистра rj зарегистрировать гk
d '.C '(rj,рk)[ рj ] +1 → rk, [ рj ] → rjКопировать увеличенное содержимое регистра rj зарегистрировать гk
е.J [E1]Перейти к «Выходу 1»Безусловный переход на «Выход №1»
е *:J (rj, рk) [E1, E2]ЕСЛИ [rj ] ≤ [гk ] ЗАТЕМ перейти к "Exit 1" Иначе перейти к "Exit 2"Перейти к выходу из E1, если содержимое регистра rj меньше или равно содержимому rk, иначе перейти к E = 2

1958: "Лечение" Петера

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

"с точки зрения как можно более быстрого доказательства вычислимости всех частичные рекурсивные функции Петер, пожалуй, лучший; для доказательства их вычислимости Машины Тьюринга необходим дальнейший анализ операции копирования в соответствии с указанными выше линиями »(Shepherdson and Sturgis (1963), стр. 246).
Действие:Описание:
c:На)0 → [n]Нулевой (очистить) регистр n
d.С (м, п)[m] → n, [m] → [m]Скопируйте содержимое регистра m в регистр n
d '.С '(м, п)[m] + 1 → [n], [m] → [m]Скопируйте увеличенное содержимое регистра m в регистр n
е.J (m, n) [E1, E2]IF [m] = [n] перейти к E1 ELSE перейти к E2Условный переход к E1, если содержимое m равно содержимому n, иначе переход к E2.

1961: Модель частичной рекурсивной функции Мински сведена к «программе» всего из двух инструкций.

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

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

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

Действие:Описание:
а.ДОБАВИТЬ (r, Ij1)[г] + 1 → г; перейти к инструкции Ij1.Увеличить (добавить 1) содержимое регистра r и перейти к инструкции I.j1.
б.SUB (r, Ij1,Яj2)Если [r] ≤ 0 ТО перейдите к инстр. яj2 ИНАЧЕ [r] -1 → r и перейдите к инстр. яj1ЕСЛИ содержимое регистра r равно нулю ТО переход к инструкции Ij2; ИНАЧЕ уменьшает (вычитает 1 из) содержимое регистра r и переходит к instr. яj1.

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

"... представляет любую частично рекурсивную функцию программой, работающей с одним целым числом S [содержащимся в одном регистре r1] с использованием инструкций Ij форм »:
Действие:Описание:
а.MULT (Kj, Яj1)[r1] * Kj → r1; перейти к инструкции Ij1.Умножить содержимое регистра r1 на константу Kj
б.DIV (Kj, Яj1, Яj2)[r1] / Kj = 0 затем перейти к инструкции Ij2 иначе идите к Ij1.Если деление содержимого регистра 1 на константу Kj не имеет остатка, то инстр. яj1 иначе инстр. яj2

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

1961: модель Мелзака: единственная троичная инструкция с сложением и правильным вычитанием

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

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

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

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

Фразы бесконечно большое количество локаций и конечное количество счетчиков здесь важно. Эта модель отличается от модели Мински, которая позволяет конечный количество локаций с неограниченный (фактически бесконечная) емкость для «маркеров».

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

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

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

ПозволилИнструкцияОтверстие "X"Отверстие "Y"Отверстие "Z"Значение инструкции
НетXXX
XXY([X] - [X]) = 0 → X[Y] + [X] → Y[Z] → ZВсе камешки X взяты из X и добавлены к Y
XXS([X] - [X]) = 0 → X[Y] → Y[Z] → ZВсе камешки X взяты из X и помещены в сток / источник S
НетXYX
XYY[X] - [Y] → X[Y] + [Y] → Y[Z] → ZПодсчет камешков Y, взятых из X и помещенных в Y, удвоение количества Y
XYS
НетXSX
НетXSY
НетXSS
XYZ[X] - [Y] → X[Y] → Y[Z] + [Y] → ZКоличество камешков Y, взятых из X и добавленных к Z,
SYY[X] → X[Y] + [Y] → Y[Z] → ZКоличество камешков Y, взятых из S и добавленных к Y, удвоив количество Y
SYZ[X] → X[Y] → Y[Z] + [Y] → [Z]Количество камешков Y, взятых из S и прибавленных к Z

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

  1. Если все отверстия начинаются с 0, то как увеличивать? Очевидно, это невозможно; одна лунка должна содержать единственный камешек.
  2. Условный «прыжок» происходит в каждом экземпляре типа XYZ, потому что: если он не может быть выполнен из-за того, что у X недостаточно счетчиков / камешков, тогда происходит прыжок; в противном случае, если это может быть выполнено, так оно и будет, и инструкции перейдут к следующей последовательности.
  3. Ни SXY, ни XXY не могут вызвать скачок, потому что оба они всегда могут быть выполнены.
  4. Мелзак добавляет к своей модели косвенность (см. машина с произвольным доступом ) и приводит два примера его использования. Но дальше он этим не занимается. Это первый подтвержденный случай «косвенного обращения», появившийся в литературе.
  5. Обе бумаги - З. Александр Мельзак (Математический конкурс Уильяма Лоуэлла Патнэма, победитель 1950 г.) был получен 15 мая 1961 г. и Иоахим Ламбек получены через месяц, 15 июня 1961 г. - содержатся в одном томе один за другим.
  6. Верно ли утверждение Мелзака? - что эта модель «настолько проста, что ее работу, вероятно, сможет понять средний школьник после нескольких минут объяснения» (стр. 282)? Читателю предстоит решить.

1961: Модель Lambek "abacus": распыление модели Мелзака до X +, X- с помощью теста

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

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

Действие:Описание:
а.Х + (г, яа)[г] + 1 → г; перейти к инструкции Iа.Увеличить (добавить 1 к) содержимое регистра r
б.Х- (г, яа, Яб)Если [r] ≤ 0, перейдите в инстр. I.б else [r] -1 → r и перейти к инстр. яаСначала проверьте на ноль, затем уменьшите (вычтите 1 из) содержимое регистра r

Abacus модель Булоса-Берджесса (1970 и др.), Булоса-Берджесса-Джеффри (2002):

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

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

Обратите внимание, однако, что B-B и B-B-J не используют переменную «X» в мнемонике с параметром определения (как показано в версии Lambek) - т.е. «X +» и «X-» - а мнемоника инструкций определяет сами регистры, например «2+» или «3-»:

Действие:Описание:
а1.1+ (Iа)[r1] + 1 → r1 затем перейти к инструкции Iа.Увеличить (добавить 1 к) содержимое регистра # 1
b1.1- (Iа, Яб)Если [r1] ≤ 0, ТО перейдите к Iб else [r1] -1 → r1 и перейти к Iа.Перейти к инструкции Iб если содержимое регистра r1 равно нулю Иначе уменьшить (вычесть 1 из) содержимого регистра # 1

1963: модель Шепердсона и Стерджиса

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

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

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

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

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

Они предлагают следующий набор инструкций (стр. 219) и следующие «Примечания»:

Модель URM:Действие:Описание:
а.P (n)[г] + 1 → гУвеличить (добавить 1 к) содержимое регистра r
б.D (п)[r] - 1 → rУменьшить (вычесть 1 из) содержимое регистра r
c:На)0 → гНулевой (чистый) регистр r
d.С (м, п)[ рj ] → rk, [ рj ] → rj,Скопируйте содержимое регистра rj зарегистрировать гk
е.J [E1]Перейти к «Выходу 1»Безусловный переход на «Выход №1»
f:J (r) [E1]ЕСЛИ [rj ] = 0 ЗАТЕМ перейти к "Exit 1" ИНАЧЕ следующая инструкцияЕСЛИ содержимое регистра r = 0, затем перейти к инструкции "Exit 1", иначе далее

инструкция

Заметки.

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

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

Пониженный URM:Действие:Описание:
а1.P (r)[г] + 1 → гУвеличить (добавить 1 к) содержимое регистра r
b1.D (п)[r] - 1 → rУменьшить (вычесть 1 из) содержимое регистра r
~ f1:J (r) [E1]ЕСЛИ [r] ≠ 0 ТО перейти к "Выход 1"Если содержимое регистра m 0 ТО переходите к инструкции "Exit 1" Иначе продолжить

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

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

а. P (i); добавьте ai в конец A
б. D; удалить первую букву A
f '. Ji [E1]; Если A начинается с ai, переходите к выходу 1.

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

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

1967: "Простая универсальная база для программного компьютера" Минского.

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

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

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

Действие:Описание:
а.[ 0 ]0 → гНулевой (очистить) регистр r
б.[ ' ][г] + 1 → гУвеличение (прибавление 1 к) содержимого регистра r (апостроф означает «преемник»)
c.[ - ]IF [r] = 0 THEN перейти к инструкции z ELSE следующая инструкцияПроверить регистр r и перейти к инструкции z, если содержимое равно нулю; если нет, уменьшите (вычтите 1 из) содержимое регистра r
d.[O-]Если [r] ≠ 0 ТО [r] -1 → r ELSE следующая инструкцияЕсли содержимое регистра r не равно нулю, уменьшает содержимое регистра r и переходит к z-й инструкции, иначе если 0, то следующая инструкция
е.[ → ][ рj ] → rk, [ рj ] → rjСкопируйте содержимое регистра rj зарегистрировать гk
f.[RPT]RPT a: [m, n]. Повтор не может работать в пределах своего собственного диапазона.Выполните, пока содержимое регистра [r] = 0: Повторите инструкции от m до n. Когда [r] = 0, перейдите к следующей инструкции.
г.[H]HALT
часgoto (z)Перейти к инструкции zБезусловный переход к инструкции z
я.[ ≠ ]Если [rj ] ≠ [rk ] THEN перейти к z-й инструкции ELSE следующая инструкцияУсловный переход: если содержимое регистра rj не равно содержимому регистра rk ЗАТЕМ перейти к инструкции z ИНАЧЕ следующая инструкция
j.[RPT] *RPT a: [m, n]. Repeat может работать в пределах своего собственного диапазона.* Примечание: RPT должен быть в бесконечном регистре

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

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

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

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

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

f. [→]
j. [≠]
Перейти, если не равно ": IF [rj ] ≠ [rk ] THEN перейти к z-й инструкции ELSE следующая инструкция

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

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

1980: 0-параметрическая модель Шёнхаге RAM0

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

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

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

В его конкретной модели RAM0 есть только две "арифметические операции" - "Z" для "набора содержимого регистра. z к нулю ", а" А "вместо" добавить единицу к содержимому регистра z". Единственный доступ к адресному регистру п выполняется с помощью инструкции копирования от A к N под названием "установить адрес п". Хранить" данные "в аккумуляторе. z в данном регистре машина использует содержимое п указать адрес реестра и зарегистрироваться z предоставить данные для отправки в регистр.

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

В первую очередь для справки - это модель RAM, а не модель счетчика - следующий набор команд Schönhage RAM0:

ИнструкцияДействие:Описание:
1Z0 → гОчистить регистр аккумулятора z
2А[z] + 1 → zУвеличить содержимое регистра аккумулятора z
3N[z] → n, [z] → z«Установить адрес n»: скопировать содержимое аккумулятора z в регистр адреса n
4L[[z]] → zКосвенно скопируйте в аккумулятор z содержимое регистра, на который указывает аккумулятор z
5S[z] → [n]Косвенно сохранить содержимое аккумулятора z в регистр, на который указывает содержимое регистра адреса n
6CЕсли [z] = 0, пропустить следующую инструкцию (которая должна быть инструкцией перехода Iλ)Если содержимое аккумулятора z = 0 ТО пропустить следующую инструкцию иначе продолжить
7goto IλБезусловный переход к инструкции IλБезусловный переход к инструкции Iλ

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

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

использованная литература

  • Джордж Булос, Джон П. Берджесс, Ричард Джеффри (2002), Вычислимость и логика: четвертое изданиеИздательство Кембриджского университета, Кембридж, Англия. Первоначальный текст Булоса-Джеффри был тщательно отредактирован Берджессом: более продвинутый, чем вводный учебник. Модель "Abacus machine" подробно рассматривается в главе 5. Вычислимость Abacus; это одна из трех моделей, которые тщательно изучаются и сравниваются - машина Тьюринга (все еще в исходной четырехкортежной форме Boolos) и две другие рекурсивные модели.
  • Фишер, Патрик С.; Мейер, А.; Розенберг, Арнольд Л. (1968), "Счетные машины и счетные языки", Математическая теория систем, 2: 265–283, Дои:10.1007 / bf01694011, Г-Н  0235932. Развивается временная иерархия и пространственная иерархия теоремы для счетных машин, аналогичные иерархиям для машин Тьюринга.
  • Дональд Кнут (1968), Искусство программирования, Второе издание 1973 г., Addison-Wesley, Reading, Massachusetts. См. Страницы 462-463, где он определяет «новый вид абстрактной машины или« автомата », который имеет дело со связанными структурами».
  • Иоахим Ламбек (1961 г., получено 15 июня 1961 г.), Как программировать бесконечные счеты, Математический вестник, т. 4, вып. 3. Сентябрь 1961 г., стр. 295–302. В своем Приложении II Ламбек предлагает «формальное определение« программы ». Он ссылается на Мелзака (1961) и Клини (1952). Введение в метаматематику.
  • З. А. Мельзак (1961 г., получено 15 мая 1961 г.), Неформальный арифметический подход к вычислимости и вычислениям, Канадский математический бюллетень, т. 4, вып. 3. Сентябрь 1961 г., стр. 279–293. Мелзак не дает никаких ссылок, но признает «пользу разговоров с докторами Р. Хэммингом, Д. Макилроем и В. Виссотсом из телефонных лабораторий Bell и с доктором Х. Вангом из Оксфордского университета».
  • Марвин Мински (1961 г., получено 15 августа 1960 г.). «Рекурсивная неразрешимость проблемы Поста о« теге »и других тем в теории машин Тьюринга». Анналы математики. Анналы математики. 74 (3): 437–455. Дои:10.2307/1970290. JSTOR  1970290. Проверить значения даты в: | дата = (Помогите)
  • Марвин Мински (1967). Вычисления: конечные и бесконечные машины (1-е изд.). Englewood Cliffs, N.J .: Prentice-Hall, Inc. В частности, см. Главу 11: Модели, похожие на цифровые компьютеры и глава 14: Очень простые основы вычислимости. В предыдущей главе он дает определение «Программные машины», а в следующей главе он обсуждает «Универсальные программные машины с двумя регистрами» и «... с одним регистром» и т. Д.
  • Джон С. Шепердсон и Х. Э. Стерджис (1961) получен в декабре 1961 г. Вычислимость рекурсивных функций, Journal of the Association of Computing Machinery (JACM) 10: 217-255, 1963. Чрезвычайно ценный справочный документ. В своем Приложении А авторы цитируют еще 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.
    • Петер, Рожа Графические схемы и рекурсивные функции, Диалектика 12 (1958), 373.
    • Гермес, Ганс Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semesterberichte (Göttingen) 4 (1954), 42–53.
  • А. Schnhage (1980), Машины для модификации хранения, Общество промышленной и прикладной математики, SIAM J. Comput. Vol. 9, No. 3, август 1980 г. В котором Шенхаге показывает эквивалентность своего SMM «преемнику RAM» (машина произвольного доступа) и т. Д.
  • Рич Шрёппель, Май 1972 г., "Машина с двумя счетчиками не может вычислить 2"N", Массачусетский технологический институт, Лаборатория А. И., Записка по искусственному интеллекту № 257. Автор ссылается на Мински 1967 и отмечает, что"Фрэнсис Яо независимо доказал невычислимость аналогичным методом в апреле 1971 г. "
  • Питер ван Эмде Боас, Модели машин и симуляции стр. 3–66, появляющиеся в:
Ян ван Леувен, изд. Справочник по теоретической информатике. Том A: Алгоритмы и сложность, MIT PRESS / Elsevier, 1990. ISBN  0-444-88071-2 (том А). QA 76.H279 1990.
Трактовка СММ ван Эмде Боасом приводится на стр. 32-35. Это лечение проясняет Schnhage 1980 - оно близко следует, но немного расширяет лечение Schnhage. Обе ссылки могут потребоваться для эффективного понимания.
  • Хао Ван (1957), Вариант теории вычислительных машин Тьюринга, JACM (Журнал Ассоциации вычислительной техники) 4; 63–92. Представлено на заседании Ассоциации 23–25 июня 1954 г.