Хотя некоторые авторы используют название « регистровая машина » как синоним « счетной машины », в этой статье будут приведены детали и примеры только самого примитивного вида - «счетной машины» - из рода «регистровая машина».
Внутри видовой «счетной машины» существует ряд разновидностей: модели Гермеса (1954), Капхенгста (1957), Ершова (1958), Петера (1958), Минского (1961) и Минского (1967), Мелзака (1961). ), Ламбек (1961), Шепердсон и Стерджис (1963) и Шёнхаге (1980). Эти модели будут описаны более подробно ниже.
Подробнее о моделях [ править ]
1954: Модель Гермеса [ править ]
Шепердсон и Стерджис отмечают, что «доказательство этой универсальности [цифровых компьютеров для машин Тьюринга] ... похоже, было впервые записано Гермесом, который показал в [7 - их ссылочный номер], как можно запрограммировать идеализированный компьютер. дублировать поведение любой машины Тьюринга »(Shepherdson and Sturgis, p. 219).
Шепердсон и Стерджис отмечают, что:
- «Подход Капхенгста интересен тем, что он дает прямое доказательство универсальности современных цифровых компьютеров, по крайней мере, когда он идеализирован до степени допуска бесконечности регистров хранения, каждый из которых способен хранить произвольно длинные слова» (Shepherdson and Sturgis, p. 219)
Единственные две арифметические инструкции:
- Последующая операция
- Проверка двух чисел на равенство
Остальные операции - это переходы из регистра в аккумулятор или из аккумулятора в регистр или тестовые переходы.
Статья Капхенгста написана на немецком языке; В переводе Шепердсона и Стерджиса используются такие термины, как «мельница» и «заказы».
Машина содержит «мельницу» (аккумулятор). Капхенгст обозначает свою мельницу / аккумулятор символом «бесконечность», но в следующем описании мы будем использовать букву «А». Он также содержит «регистр порядка» («порядок» как в «инструкции», а не как «последовательность»). (Это использование произошло из описания в отчете Буркса – Голдстайна – фон Неймана (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 → <A> ИНАЧЕ 1 → A | Очистить содержимое A, если содержимое A = содержимое r, иначе "установить" A = 1 |
| G2: | О '(А) | 1 → А | "Установить" содержимое A = 1 |
Шепердсон и Стерджис удаляют мельницу / накопитель A и сокращают команды Капхенгста до «копирования» регистр-регистр, арифметической операции «приращения» и «сравнения регистр-регистр». Обратите внимание на отсутствие декремента . Эту модель, почти дословно, можно найти у Минского (1967); подробнее см. в разделе ниже.
| Действие: | Описание: | ||
|---|---|---|---|
| а: | P (А) | [A] + 1 → A | Увеличить (добавить 1 к) содержимое аккумулятора A |
| d. | C (r j , r k ) | [r j ] → r k , [r j ] → r j | Скопируйте содержимое регистра r j в регистр r k |
| f: | J (r) [E1] | IF [r] = 0 ТО перейти к "Exit 1" ИНАЧЕ следующая инструкция | Перейти, если содержимое регистра r = 0 |
| c: | E (r j , r k ) | ЕСЛИ [r j ] = [r k ] ТО 0 → E ELSE 1 → E | Очистить содержимое регистра E, если содержимое r j = содержимое r k , иначе "установить" E = 1 |
1958: класс операторных алгоритмов Ершова [ править ]
Шепердсон и Стерджис (1963) отмечают, что модель Эрсова позволяет хранить программу в регистрах. Они утверждают, что модель Эрсова такова:
| Действие: | Описание: | ||
|---|---|---|---|
| d. | C (r j , r k ) | [r j ] → r k , [r j ] → r j | Скопируйте содержимое регистра r j в регистр r k |
| d '. | C '(r j , r k ) | [r j ] +1 → r k , [r j ] → r j | Скопируйте увеличенное содержимое регистра r j в регистр r k |
| е. | J [E1] | Перейти к «Выходу 1» | Безусловный переход на «Выход №1» |
| е *: | J (r j , r k ) [E1, E2] | ЕСЛИ [r j ] ≤ [r k ] ТО переходите к "Exit 1", Иначе переходите к "Exit 2" | Перейти к выходу из E1, если содержимое регистра r j меньше или равно содержимому r k , иначе перейти к E = 2 |
1958: «Лечение» Петера [ править ]
Шепердсон и Стерджис (1963) отмечают, что «лечение» Петера (здесь они не слишком конкретны) эквивалентно инструкциям, приведенным в следующей таблице. Они специально комментируют эти инструкции, что:
- «С точки зрения как можно более быстрого доказательства вычислимости всех частично рекурсивных функций функция Петера, пожалуй, лучшая; для доказательства их вычислимости машинами Тьюринга необходим дальнейший анализ операции копирования в соответствии с изложенными выше принципами». (Шепердсон и Стерджис (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 «s ( проблемы Гильберта , уравнение Диофантова ) привел к Минскому следующему определению:
- «интересная основа для теории рекурсивных функций, включающая программы только простейших арифметических операций» (Мински (1961), стр. 437).
Его «Теорема Ia» утверждает, что любая частично рекурсивная функция представлена «программой, работающей с двумя целыми числами S1 и S2 с использованием инструкций Ij форм (см. Минский (1961), стр. 449):
| Действие: | Описание: | ||
|---|---|---|---|
| а. | ДОБАВИТЬ (r, I j1 ) | [г] + 1 → г; перейдите к инструкции I j1 . | Увеличьте (прибавьте 1 к) содержимое регистра r и перейдите к инструкции I j1 . |
| б. | SUB (г, я j1 , я j2 ) | Если [r] ≤ 0 ТО перейдите к инстр. I j2 ELSE [r] -1 → r и перейдите к инстр. Я j1 | ЕСЛИ содержимое регистра r равно нулю, ТО переход к инструкции I j2 ; ELSE уменьшает (вычитает 1 из) содержимое регистра r и переходит к instr. Я j1 . |
Первая теорема является контекстом второй «теоремы IIa», что
- "... представляет любую частично рекурсивную функцию программой, работающей с одним целым числом S [содержащимся в единственном регистре r1] с использованием инструкций I j форм":
| Действие: | Описание: | ||
|---|---|---|---|
| а. | МУЛЬТ (K j , I j1 ) | [r1] * K j → r1; перейдите к инструкции I j1 . | Умножить содержимое регистра r1 на константу K j |
| б. | DIV (K j , I j1 , I j2 ) | [r1] / Kj = 0, затем перейти к инструкции I j2, иначе перейти к I j1 . | Если от деления содержимого регистра 1 на константу K j нет остатка, то instr. Я j1 еще инстр. Я j2 |
Во второй форме машина использует числа Геделя для обработки «целого числа S». Он утверждает, что первая машина / модель не должна этого делать, если у нее есть 4 доступных регистра.
1961: Модель Мелзака: единственная троичная инструкция с добавлением и правильным вычитанием [ править ]
- «Наша цель - описать примитивное устройство, которое будет называться Q-машиной, которое достигает эффективной вычислимости с помощью арифметики, а не с помощью логики. Три его операции - это подсчет, сравнение неотрицательных целых чисел и передача» (Мелзак ( 1961) с. 281).
Если мы используем контекст его модели, «ведение счета» означает «прибавление последовательными приращениями» (бросание камешков) или «вычитание последовательными приращениями»; передача означает перемещение (а не копирование) содержимого из отверстия A в отверстие B, и сравнение чисел самоочевидно. Похоже, это смесь трех базовых моделей.
Физическая модель Мелзака - это отверстия {X, Y, Z и т. Д.} В земле вместе с неограниченным запасом гальки в специальном отверстии S (раковина или снабжение или и то, и другое? Мелзак не говорит).
- "Q-машина состоит из неопределенно большого количества ячеек : S, A1, A2, ..., неопределенно большого запаса счетчиков, распределенных по этим локациям, программы и оператора, единственной целью которого является выполнение инструкций. . Изначально все, кроме конечного числа из ячеек ... пусты, и каждая из оставшихся содержит конечное число счетчиков »(стр. 283, жирный шрифт добавлен)
Здесь важны фразы бесконечно большое количество локаций и конечное количество счетчиков . Эта модель отличается от модели Мински, которая учитывает конечное количество мест с неограниченной (фактически бесконечной) емкостью для «маркеров».
Инструкция представляет собой единственную «тернарную операцию», которую он называет «XYZ»:
- «XYZ» обозначает работу
- Подсчитайте количество камешков в лунке Y ,
- верните их в Y ,
- пытаться удалить этот же номер из отверстия X . ЕСЛИ это невозможно, потому что отверстие X будет пустым, ТО ничего не делать и перейти к инструкции #I; ЕЩЕ,
- удалить Y-количество из X и (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 |
Некоторые наблюдения о модели Мелзака :
- Если все отверстия начинаются с 0, то как нам увеличивать? Очевидно, это невозможно; одна лунка должна содержать единственный камешек.
- Условный «прыжок» происходит в каждом экземпляре типа XYZ, потому что: если он не может быть выполнен из-за того, что у X недостаточно счетчиков / камешков, тогда происходит прыжок; в противном случае, если это может быть выполнено, так оно и будет, и инструкции перейдут к следующей последовательности.
- Ни SXY, ни XXY не могут вызвать скачок, потому что оба они всегда могут быть выполнены.
- Мелзак добавляет косвенность к своей модели (см. Машину с произвольным доступом ) и приводит два примера ее использования. Но дальше он этим не занимается. Это первый подтвержденный случай «косвенного обращения», появившийся в литературе.
- Обе статьи - работа З. Александра Мелзака ( математический конкурс Уильяма Лоуэлла Патнэма , победитель 1950 г.) была получена 15 мая 1961 г., а Иоахима Ламбека - месяцем позже, 15 июня 1961 г., - содержатся в одном томе, одна за другой.
- Верно ли утверждение Мелзака? - что эта модель «настолько проста, что ее работу, вероятно, сможет понять средний школьник после нескольких минут объяснения» (стр. 282)? Читателю предстоит решить.
1961: Модель «счеты» Ламбека: преобразование модели Мелзака в X +, X- с помощью теста [ править ]
Оригинальная модель «счеты» Ламбека (1962 г.):
Ламбек ссылается на статью Мелзака. Он разделяет единственную 3-параметрическую операцию Мелзака (на самом деле 4, если мы считаем адреса инструкций) в 2-параметрическое приращение «X +» и 3-параметрическое декремент «X-». Он также дает как неформальное, так и формальное определение «программы». Эта форма практически идентична модели Мински (1961) и была принята Булосом-Берджессом-Джеффри (2002).
| Действие: | Описание: | ||
|---|---|---|---|
| а. | Х + (г, I а ) | [г] + 1 → г; перейдите к инструкции I a . | Увеличить (добавить 1 к) содержимое регистра r |
| б. | X- (г, я а , я б ) | Если [r] ≤ 0, перейдите к instr.I b else [r] -1 → r и перейдите к instr. Я | Сначала проверьте на ноль, затем уменьшите (вычтите 1 из) содержимое регистра r |
Abacus модель Булоса-Берджесса (1970 и др.), Булоса-Берджесса-Джеффри (2002) :
В различных изданиях, начиная с 1970 г., авторы используют модель «бесконечных счётов» Ламбека (1961). В этой серии статей Википедии используется их символика, например, «[r] +1 → r» «содержимое регистра, обозначенного как номер 'r', плюс 1, заменяет содержимое [помещается в] регистр с номером 'r'» .
Они используют имя Ламбека «счеты», но следуют модели «галька в отверстиях» Мелзака, модифицированной ими до модели «камни в коробках». Как и в исходной модели абака Ламбека, их модель сохраняет использование Мински (1961) непоследовательных инструкций - в отличие от «обычного» компьютерного последовательного выполнения инструкций по умолчанию, следующая инструкция I a содержится внутри инструкции.
Обратите внимание, однако, что BB и BBJ не используют переменную «X» в мнемонике с определяющим параметром (как показано в версии Lambek) - т.е. «X +» и «X-» - а, скорее, мнемоника инструкций определяет регистрирует себя, например "2+" или "3-":
| Действие: | Описание: | ||
|---|---|---|---|
| а1. | 1+ (I a ) | [r1] + 1 → r1, затем перейдите к инструкции I a . | Увеличить (добавить 1 к) содержимое регистра # 1 |
| b1. | 1- (I а , I б ) | Если [r1] ≤ 0, ТО перейдите к I b else [r1] -1 → r1 и перейдите к I a . | Перейти к инструкции I b, если содержимое регистра 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. | С (м, п) | [r j ] → r k , [r j ] → r j , | Скопируйте содержимое регистра r j в регистр r k |
| е. | J [E1] | Перейти к «Выходу 1» | Безусловный переход на «Выход №1» |
| f: | J (r) [E1] | IF [r j ] = 0 ТО перейти к "Exit 1" ИНАЧЕ следующая инструкция | ЕСЛИ содержимое регистра r = 0, затем перейти к инструкции "Exit 1", иначе далее инструкция |
Заметки.
- Этот набор инструкций выбран для простоты программирования вычисления частично рекурсивных функций, а не для экономии; в разделе 4 показано, что этот набор эквивалентен меньшему набору.
- В этом списке бесконечно много инструкций, поскольку m, n [содержимое r j и т. Д.] Охватывают все положительные целые числа.
- В инструкциях 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, ТО перейти к "Exit 1" | Если содержимое регистра m 0 ТО перейдите к инструкции "Выход 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
- снимаем нижнюю карту; если напечатано 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, то следующая инструкция |
| е. | [→] | [r j ] → r k , [r j ] → r j | Скопируйте содержимое регистра r j в регистр r k |
| f. | [RPT] | RPT a: [m, n]. Повтор не может работать в пределах своего собственного диапазона. | Выполните, пока содержимое регистра [r] = 0: Повторите инструкции от m до n. Когда [r] = 0, перейдите к следующей инструкции. |
| грамм. | [H] | HALT | |
| час | goto (z) | Перейти к инструкции z | Безусловный переход к инструкции z |
| я. | [≠] | Если [r j ] ≠ [r k ] ТО перейти к z-й инструкции ИНАЧЕ следующая инструкция | Условный переход: если содержимое регистра r j не равно содержимому регистра r k THEN переход к инструкции z ELSE следующая инструкция |
| j. | [RPT] * | RPT a: [m, n]. Repeat может работать в пределах своего собственного диапазона. | * Примечание: RPT должен быть в бесконечном регистре. |
Минский (1967) начинает с модели, состоящей из трех операций плюс HALT:
- {[0], ['], [-], [H]}
Он отмечает, что мы можем обойтись без [0], если допустим конкретный регистр, например, w уже «пустой» (Minsky (1967), стр. 206). Позже (стр. 255 и далее) он сжимает три {[0], ['], [-]} в два {['], [-]}.
Но он признает, что модель будет проще, если он добавит некоторые [псевдо] -инструкции [O-] (объединенные [0] и [-]) и «go (n)». Он строит «go (n)» из регистра w, предварительно установленного в 0, так что [O-] ( w , (n)) является безусловным переходом.
В разделе 11.5 «Эквивалентность программных машин общерекурсивным функциям» он вводит две новые подпрограммы:
- f. [→]
- j. [≠]
- Перейти, если не равно ": IF [r j ] ≠ [r k ] ТО перейти к z-й инструкции ELSE следующая инструкция
Он продолжает показывать, как заменить набор «преемник-предшественник» {[0], ['], [-]} набором «преемник-равенство» {[0], ['], [≠]}. Затем он определяет свой «REPEAT» [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 | Z | 0 → г | Очистить регистр аккумулятора z |
| 2 | А | [z] + 1 → z | Увеличить содержимое регистра аккумулятора z |
| 3 | N | [z] → n, [z] → z | «Установить адрес n»: скопировать содержимое аккумулятора z в регистр адреса n |
| 4 | L | [[z]] → z | Косвенно скопируйте в аккумулятор z содержимое регистра, на который указывает аккумулятор z |
| 5 | S | [z] → [n] | Косвенно сохранить содержимое аккумулятора z в регистр, на который указывает содержимое регистра адреса n |
| 6 | C | Если [z] = 0, пропустить следующую инструкцию (которая должна быть инструкцией перехода I λ ) | Если содержимое аккумулятора z = 0 ТО пропустить следующую инструкцию иначе продолжить |
| 7 | goto I λ | Инструкция безусловного перехода (перехода к) I λ | Инструкция безусловного перехода (перехода к) I λ |
Опять же, вышеупомянутый набор команд предназначен для машины с произвольным доступом , RAM - машина счетчика с косвенной адресацией; инструкция «N» допускает косвенное сохранение аккумулятора, а инструкция «L» допускает косвенную загрузку аккумулятора.
Несмотря на свою странность, модель Шёнхаге показывает, как набор команд «регистр-регистр» или «чтение-изменение-запись» обычного счетчика может быть преобразован в простейшую форму с 0 параметрами.
Ссылки [ править ]
- Джордж Булос , Джон П. Берджесс , Ричард Джеффри (2002), Вычислимость и логика: четвертое издание , Cambridge University Press, Кембридж, Англия. Первоначальный текст Булоса-Джеффри был тщательно отредактирован Берджессом: более продвинутый, чем вводный учебник. Модель "Abacus machine" подробно описана в главе 5 " Вычислимость Abacus" ; это одна из трех моделей, которые тщательно изучаются и сравниваются - машина Тьюринга (все еще в исходной четырехкортежной форме Boolos) и две другие рекурсивные модели.
- Фишер, Патрик К .; Мейер, АР ; Розенберг, Арнольд Л. (1968), "Счетчик машины и языки счетчик", Математическая теория систем , 2 : 265-283, DOI : 10.1007 / bf01694011 , MR 0235932. Разрабатывает теоремы о временной иерархии и пространственной иерархии для счетчиков, аналогичные иерархиям для машин Тьюринга.
- Дональд Кнут (1968), Искусство компьютерного программирования , второе издание 1973, Addison-Wesley, Reading, Massachusetts. См. Страницы 462-463, где он определяет «новый вид абстрактной машины или« автомата », который имеет дело со связанными структурами».
- Иоахим Ламбек (1961, получен 15 июня 1961), Как программировать бесконечные счеты , Математический бюллетень, т. 4, вып. 3. Сентябрь 1961 г., стр. 295–302. В своем Приложении II Ламбек предлагает «формальное определение« программы ». Он ссылается на Мелзака (1961) и Клини (1952)« Введение в метаматематику » .
- ZA Melzak (1961, получено 15 мая 1961 г.), Неформальный арифметический подход к вычислимости и вычислениям , Canadian Mathematical Bulletin, vol. 4, вып. 3. Сентябрь 1961 г., стр. 279–293. Мелзак не дает никаких ссылок, но признает «пользу разговоров с докторами Р. Хэммингом, Д. Макилроем и В. Виссотсом из телефонных лабораторий Bell и с доктором Х. Вангом из Оксфордского университета».
- Марвин Мински (1961 г., получен 15 августа 1960 г.). "Рекурсивная неразрешимость проблемы Поста" тега "и других тем теории машин Тьюринга". Анналы математики . Анналы математики. 74 (3): 437–455. DOI : 10.2307 / 1970290 . JSTOR 1970290 . Проверить значения даты в:
|date=( помощь ) - Марвин Мински (1967). Вычисление: конечные и бесконечные машины (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc.В частности, см. Главу 11: Модели, подобные цифровым компьютерам, и главу 14: Очень простые основы вычислимости . В предыдущей главе он дает определение «Программные машины», а в более поздней главе он обсуждает «Универсальные программные машины с двумя регистрами» и «... с одним регистром» и т. Д.
- Джон С. Шепердсон и Х. Э. Стерджис (1961) получили в декабре 1961 г. « Вычислимость рекурсивных функций» , Journal of the Association of Computing Machinery (JACM) 10: 217-255, 1963. Чрезвычайно ценный справочный документ. В своем Приложении А авторы цитируют еще 4 со ссылкой на «Минимум инструкций, используемых в 4.1: Сравнение с аналогичными системами».
- Kaphengst, Heinz, 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 rekursive Funktionen , Dialectica 12 (1958), 373.
- Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semesterberichte (Göttingen) 4 (1954), 42–53.
- A. Schnhage (1980), Машины для модификации памяти , Общество промышленной и прикладной математики, SIAM J. Comput. Vol. 9, No. 3, август 1980 г. В котором Шенхаге показывает эквивалентность своего SMM «преемнику RAM» (машина произвольного доступа) и т. Д.
- Рич Шроппель , май 1972 г., «Машина с двумя счетчиками не может вычислить 2 N », Массачусетский технологический институт, лаборатория искусственного интеллекта, памятка по искусственному интеллекту № 257. Автор ссылается на Мински 1967 и отмечает, что « Фрэнсис Яо независимо доказала невычислимость, используя аналогичный метод в апреле 1971 года».
- Питер ван Эмде Боас , Machine Models and Simulations, стр. 3–66, появляется в:
- Ян ван Леувен , изд. "Справочник по теоретической информатике. Том A: Алгоритмы и сложность , MIT PRESS / Elsevier, 1990. ISBN 0-444-88071-2 (том A). QA 76.H279 1990.
- Трактовка СММ ван Эмде Боасом приводится на стр. 32-35. Это лечение проясняет Schnhage 1980 - оно близко следует, но немного расширяет лечение Schnhage. Обе ссылки могут потребоваться для эффективного понимания.
- Хао Ван (1957), Вариант теории вычислительных машин Тьюринга, JACM (Журнал Ассоциации вычислительной техники) 4; 63–92. Представлено на заседании Ассоциации 23–25 июня 1954 г.
