Машина с произвольным доступом

В этой статье есть несколько проблем. Помогите улучшить ее или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти сообщения ) В статье содержится список общих ссылок , но в ней отсутствуют соответствующие встроенные цитаты .Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Декабрь 2017 )( Узнайте, как и когда удалить это сообщение ) Эта статья может оказаться слишком сложной для понимания большинством читателей . Please help improve it to make it understandable to non-experts, without removing the technical details. (December 2017) (Learn how and when to remove this message) This article's tone or style may not reflect the encyclopedic tone used on Wikipedia. See Wikipedia's guide to writing better articles for suggestions. (December 2017) (Learn how and when to remove this message) (Learn how and when to remove this message)

В информатике машина с произвольным доступом ( RAM или RA-машина ) — это модель вычислений , которая описывает абстрактную машину в общем классе регистровых машин . RA-машина очень похожа на счетчиковую машину , но с дополнительной возможностью «косвенной адресации» ее регистров. «Регистры» интуитивно эквивалентны основной памяти обычного компьютера, за исключением дополнительной способности регистров хранить натуральные числа любого размера. Как и счетчиковая машина, RA-машина содержит инструкции выполнения в конечно-частной части машины (так называемая Гарвардская архитектура ).

Эквивалент универсальной машины Тьюринга в RA-машине  – с ее программой в регистрах, а также ее данными – называется машиной с произвольным доступом и хранимой программой или RASP-машиной. Это пример так называемой архитектуры фон Неймана , наиболее близкий к общепринятому представлению о компьютере .

Вместе с моделями машины Тьюринга и контрмашины , модели RA-машины и RASP-машины используются для анализа сложности вычислений . Ван Эмде Боас (1990) называет эти три модели вместе с указателем моделями «последовательной машины», чтобы отличать их от моделей « параллельной машины с произвольным доступом ».

Машина RA состоит из следующих частей:

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

Описание похожей концепции, но с юмором, см. в эзотерическом языке программирования Brainfuck . ^[1]

Концепция машины с произвольным доступом (RAM) начинается с самой простой модели из всех, так называемой модели машины-счетчика . Однако два дополнения отдаляют ее от машины-счетчика. Первое дополняет машину удобством косвенной адресации; второе перемещает модель в сторону более традиционного компьютера на основе аккумулятора с добавлением одного или нескольких вспомогательных (выделенных) регистров, наиболее распространенный из которых называется «аккумулятор».

Машина с произвольным доступом (RAM) — это абстрактная модель вычислительной машины, идентичная многорегистровой машине- счетчику с добавлением косвенной адресации. По усмотрению инструкции из ТАБЛИЦЫ своего конечного автомата машина выводит адрес «целевого» регистра либо (i) непосредственно из самой инструкции, либо (ii) косвенно из содержимого ( например, номера, метки) регистра «указателя», указанного в инструкции.

По определению: Регистр — это местоположение с адресом (уникальное, различимое обозначение/локатор, эквивалентное натуральному числу) и содержимым —  одним натуральным числом. Для точности мы будем использовать квазиформальную символику из Boolos-Burgess-Jeffrey (2002) для указания регистра, его содержимого и операции над регистром:

• [r] означает "содержимое регистра с адресом r". Метка "r" здесь - это "переменная", которая может быть заполнена натуральным числом или буквой (например, "A") или именем.
• → означает «копировать/депонировать» или «заменять», но без уничтожения источника

Пример: [3] +1 → 3; означает «Содержимое исходного регистра с адресом «3» плюс 1 помещается в целевой регистр с адресом «3» (здесь источник и назначение — одно и то же место). Если [3]=37, то есть содержимое регистра 3 — это число «37», то 37+1 = 38 будет помещено в регистр 3.

Пример: [3] → 5; означает «Содержимое исходного регистра с адресом «3» помещается в целевой регистр с адресом «5». Если [3]=38, то есть содержимое регистра 3 представляет собой число 38, то это число будет помещено в регистр 5. Содержимое регистра 3 не нарушается этой операцией, поэтому [3] продолжает быть 38, теперь таким же, как [5].

Определение: Прямая инструкция — это инструкция, которая указывает в самой инструкции адрес исходного или целевого регистра, содержимое которого будет предметом инструкции. Определение: Косвенная инструкция — это инструкция, которая указывает «регистр указателя», содержимое которого является адресом «целевого» регистра. Целевой регистр может быть как источником, так и местом назначения (различные инструкции COPY дают примеры этого). Регистр может адресовать себя косвенно.

Ввиду отсутствия стандарта/соглашения в данной статье в качестве параметра (или параметров) в инструкции будет указано «прямой/косвенный», сокращенно «d/i»:

Пример: COPY ( d , A, i , N ) означает непосредственное получение адреса исходного регистра (регистра «A») из самой инструкции, но косвенное получение адреса назначения из регистра-указателя N. Предположим, что [N]=3, тогда регистр 3 является местом назначения, и инструкция выполнит следующее: [A] → 3.

Определение: Содержимое исходного регистра используется инструкцией. Адрес исходного регистра может быть указан либо (i) непосредственно инструкцией, либо (ii) косвенно регистром указателя, указанным инструкцией.

Определение: Содержимое регистра указателя является адресом «целевого» регистра.

Определение: Содержимое регистра указателя указывает на целевой регистр  – «целью» может быть как исходный, так и целевой регистр.

Определение: Регистр назначения — это место, куда инструкция помещает свой результат. Адрес исходного регистра может быть указан либо (i) непосредственно инструкцией, либо (ii) косвенно регистром указателя, указанным инструкцией. Исходный и целевой регистры могут быть одним.

Мелзак (1961) дает простую визуализацию счетной машины: ее «регистры» — это отверстия в земле, и в этих отверстиях находятся камешки. Согласно инструкции, в эти отверстия и из них «компьютер» (человек или машина) добавляет (INCrements) или удаляет (DECrements) один камешек. По мере необходимости из бесконечного запаса поступают дополнительные камешки, а лишние камешки возвращаются обратно; если отверстие слишком мало для размещения камешков, «компьютер» выкапывает яму большего размера.

Минский (1961) и Хопкрофт-Ульман 1979 (стр. 171) предлагают визуализацию многоленточной машины Тьюринга с таким количеством лент с левым концом, как и «регистров». Длина каждой ленты не ограничена справа, и каждый квадрат пуст, за исключением левого конца, который отмечен. Расстояние от «головки» ленты до ее левого конца, измеренное в количестве квадратов ленты, представляет собой натуральное число в «регистре». Чтобы уменьшить количество квадратов, головка ленты перемещается влево; чтобы увеличить, она перемещается вправо. Нет необходимости печатать или стирать метки на ленте; единственные условные инструкции — это проверить, находится ли головка на левом конце, путем проверки метки левого конца с помощью инструкции «Jump-if-marked».

Следующие «мнемоники» инструкций, например, «CLR (r)», являются произвольными; стандарта не существует.

Регистровая машина имеет, для памяти, внешней по отношению к ее конечному автомату – неограниченный (ср. сноска|счетные и неограниченные) набор дискретных и уникально помеченных ячеек с неограниченной емкостью, называемых «регистрами». Эти регистры содержат только натуральные числа (ноль и положительные целые числа). Согласно списку последовательных инструкций в ТАБЛИЦЕ конечного автомата, несколько (например, 2) типов примитивных операций работают с содержимым этих «регистров». Наконец, условное выражение в форме IF-THEN-ELSE доступно для проверки содержимого одного или двух регистров и «ветвления/перехода» конечного автомата из последовательности инструкций по умолчанию.

Базовая модель 1 : Модель, наиболее близкая к визуализации Минского (1961) и Ламбека (1961):

• { INУвеличить содержимое регистра r, DEУвеличить содержимое регистра r, ЕСЛИ содержимое регистра r равно нулю, ТО Перейти к инструкции I _z, ИНАЧЕ перейти к следующей инструкции}:

Базовая модель 2 : Модель «преемника» (названная в честь функции преемника аксиом Пеано ):

• { INУвеличить содержимое регистра r, ОЧИСТИТЬ содержимое регистра r, ЕСЛИ содержимое регистра r _j равно содержимому регистра r _k ТО Перейти к инструкции I _z ИНАЧЕ перейти к следующей инструкции }

Базовая модель 3 : использовалась Элготом-Робинсоном (1964) в его исследовании ограниченных и неограниченных RASP – «последующая» модель с COPY вместо CLEAR:

• { INУвеличить содержимое регистра r, КОПИРОВАТЬ содержимое регистра r _j в регистр r _k , ЕСЛИ содержимое регистра r _j равно содержимому регистра r _k, то перейти к инструкции I _z, ИНАЧЕ перейти к следующей инструкции}

Три базовых набора 1, 2 или 3, приведенные выше, эквивалентны в том смысле, что можно создать инструкции одного набора, используя инструкции другого набора (интересное упражнение: подсказка от Мински (1967) – объявить зарезервированный регистр, например, назвав его «0» (или Z для «нуля» или E для «стирания»), чтобы он содержал число 0). Выбор модели будет зависеть от того, какую модель автор посчитает проще всего использовать в демонстрации, доказательстве и т. д.

Более того, из базовых наборов 1, 2 или 3 мы можем создать любую из примитивных рекурсивных функций (см. Minsky (1967), Boolos-Burgess-Jeffrey (2002)). (Как расширить сеть, чтобы охватить полные и частичные мю-рекурсивные функции, будет обсуждаться в контексте косвенной адресации). Однако построение примитивных рекурсивных функций затруднено, поскольку наборы инструкций настолько ... примитивны (крошечные). Одним из решений является расширение определенного набора с помощью «удобных инструкций» из другого набора:

Это не будут подпрограммы в общепринятом смысле, а скорее блоки инструкций, созданные из базового набора и снабженные мнемоникой. В формальном смысле, чтобы использовать эти блоки, нам нужно либо (i) «расширить» их до эквивалентов базовых инструкций – они потребуют использования временных или «вспомогательных» регистров, поэтому модель должна это учитывать, либо (ii) спроектировать наши машины/модели со «встроенными» инструкциями.

Пример: Базовый набор 1. Для создания CLR (r) используйте блок инструкций для обратного отсчета регистра r до нуля. Обратите внимание на использование подсказки, упомянутой выше:

• CLR (r) = _эквив.
• петля : JZ (r, выход )

• ДЕК (р)
• JZ (0, петля )

• выход : и т.д.

Опять же, все это сделано только для удобства; ничто из этого не увеличивает внутреннюю мощность модели.

Например: наиболее расширенный набор будет включать каждую уникальную инструкцию из трех наборов, а также безусловный переход J (z), т.е.:

• { CLR (r), DEC (r), INC (r), CPY (r _s , r _d ), JZ (r, z), JE (r _j , r _k , z ), J(z) }

Большинство авторов выбирают один или другой из условных переходов, например, Шепердсон-Стерджис (1963) использует указанный выше набор за вычетом JE (чтобы быть абсолютно точным, они используют JNZ – Jump if Not Zero вместо JZ; еще одна возможная инструкция для удобства).

В нашей повседневной жизни понятие «непрямая операция» не является чем-то необычным.

Пример: Поиск сокровищ.

В локации «Пещера_Тома_и_Бекки_в_пиратском_сундуке» мы сможем найти карту, указывающую нам путь к «сокровищу»:

(1) Идем в локацию "Пещера_Тома_и_Бекки..." и копаемся, пока не находим деревянный ящик.

(2) Внутри коробки находится карта местонахождения сокровища: «под_крыльцом_дома_Тэтчер».

(3) Идем в локацию «под_крыльцом_Тэтчер», отбиваем отбойным молотком бетон и обнаруживаем «сокровище»: мешок ржавых дверных ручек.

Косвенно указывается местоположение, идентифицированное как пиратский сундук в «Пещере_Тома_и_Бекки...», которое действует как указатель на любое другое местоположение (включая само себя): его содержимое (карта сокровищ) предоставляет «адрес» целевого местоположения «под_крыльцом_Тэтчер», где происходят реальные действия.

В дальнейшем следует помнить, что эти модели являются абстрактными моделями с двумя фундаментальными отличиями от чего-либо физически реального: неограниченное количество регистров, каждый с неограниченной емкостью. Проблема проявляется наиболее драматично, когда кто-то пытается использовать модель контрмашины для построения RASP, эквивалентного Тьюрингу , и, таким образом, вычислить любую частичную мю-рекурсивную функцию :

• Melzak (1961) добавил косвенность к своей модели «дырка и камешек», чтобы его модель могла модифицировать себя с помощью «вычисляемого goto», и приводит два примера ее использования («Десятичное представление в масштабе d» и «Сортировка по величине», используются ли они в его доказательстве того, что модель эквивалентна Тьюрингу, неясно, поскольку «сама программа оставлена ​​читателю в качестве упражнения» (стр. 292)). Minsky (1961, 1967) смог продемонстрировать, что с подходящим (но сложным в использовании) кодированием чисел Гёделя регистровая модель не нуждается в косвенности, чтобы быть эквивалентной Тьюрингу; но ей нужен был по крайней мере один неограниченный регистр. Как отмечено ниже, Minsky (1967) намекает на проблему для RASP, но не предлагает решения. Элгот и Робинсон (1964) доказали, что их модель RASP P ₀  – она не имеет возможности косвенной адресации – не может вычислить все «рекурсивные последовательные функции» (те, которые имеют параметры произвольной длины), если она не имеет возможности изменять свои собственные инструкции, но она может это сделать с помощью чисел Гёделя, если она имеет (стр. 395-397; в частности, рисунок 2 и сноска на стр. 395). С другой стороны, их модель RASP P' ₀ , оснащенная «индексным регистром» (косвенная адресация), может вычислить все «частично рекурсивные последовательные функции» (рекурсивные функции mu) (стр. 397-398).

Кук и Рекхоу (1973) выражаются наиболее лаконично:

Косвенные инструкции необходимы для того, чтобы фиксированная программа могла получить доступ к неограниченному числу регистров при изменении входных данных." (стр. 73)

• Неограниченные емкости регистров против ограниченных емкостей инструкций конечного автомата : так называемая конечная часть автомата должна быть — по обычному определению алгоритма — очень конечной как по количеству «состояний» (инструкций), так и по размерам инструкций (их емкости для хранения символов/знаков). Так как же конечный автомат перемещает произвольно большую константу непосредственно в регистр, например, MOVE (k, r) (переместить константу k в регистр r)? Если необходимы огромные константы, они должны либо начинаться в самих регистрах, либо создаваться конечным автоматом с использованием конечного числа инструкций, например, подпрограмм умножения и сложения с использованием INC и DEC (но не квазибесконечного числа из них!).

Иногда константа k создается с помощью CLR ( r ), за которым следует INC ( r ), повторяющееся k раз – например, чтобы поместить константу k=3 в регистр r, т. е. 3 → r, так что в конце инструкции [r]=3: CLR (r), INC (r), INC (r), INC (r). Этот трюк упоминается Клини (1952) на стр. 223. Проблема возникает, когда создаваемое число исчерпывает количество инструкций, доступных конечному автомату; всегда есть большая константа, чем количество инструкций, доступных конечному автомату.

• Неограниченное количество регистров против ограниченных инструкций конечного автомата : Это более серьезная проблема, чем первая. В частности, эта проблема возникает, когда мы пытаемся построить так называемый RASP, «универсальную машину» (подробнее см. в Универсальная машина Тьюринга ), которая использует свой конечный автомат для интерпретации «программы инструкций», размещенной в ее регистрах – т.е. мы строим то, что в настоящее время называется компьютером с архитектурой фон Неймана .

Обратите внимание, что конечный автомат счетчика должен явно (напрямую) вызывать регистр по его имени/номеру: INC (65,356) явно вызывает регистр с номером "65,365" . Если количество регистров превышает возможности конечного автомата по их адресу, то регистры за пределами границ будут недостижимы. Например, если конечный автомат может достичь только 65,536 = 2 ¹⁶ регистров, то как он может достичь 65,537-го?

Так как же нам обратиться к регистру за пределами конечного автомата? Одним из подходов было бы изменение программных инструкций (те, что хранятся в регистрах) так, чтобы они содержали более одной команды. Но это тоже может быть исчерпано, если только инструкция не имеет (потенциально) неограниченного размера. Так почему бы не использовать всего одну «убер-инструкцию» — одно действительно очень большое число — которое содержит все программные инструкции, закодированные в нем! Вот как Мински решает проблему, но нумерация Геделя, которую он использует, представляет собой большое неудобство для модели, и результат совсем не похож на наше интуитивное представление о «компьютере с хранимой программой».

Элгот и Робинсон (1964) приходят к аналогичному выводу относительно RASP, который является «конечно определенным». Действительно, он может получить доступ к неограниченному числу регистров (например, для извлечения из них инструкций), но только если RASP допускает «самомодифицирование» своих программных инструкций и закодировал свои «данные» в числе Гёделя (рис. 2, стр. 396).

В контексте более компьютерной модели, использующей его инструкцию RPT (повторить), Минский (1967) дразнит нас решением проблемы (ср. стр. 214, стр. 259), но не предлагает твердого решения. Он утверждает:

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

Он предлагает нам ограниченный RPT, который вместе с CLR (r) и INC (r) может вычислить любую примитивную рекурсивную функцию , и он предлагает неограниченный RPT, процитированный выше, который играет роль оператора μ; он вместе с CLR (r) и INC (r) может вычислить рекурсивные функции mu. Но он не обсуждает «косвенность» или модель RAM как таковую.

Из ссылок в Hartmanis (1971) следует, что Кук (в своих лекционных заметках во время учебы в Калифорнийском университете в Беркли, 1970) закрепил понятие косвенной адресации. Это становится более ясно в статье Кука и Рекхова (1973) — Кук является руководителем магистерской диссертации Рекхова. Модель Хартманиса — весьма похожая на модель Мелзака (1961) — использует двух- и трехрегистровые сложения и вычитания и два копирования параметров; модель Кука и Рекхова сокращает количество параметров (регистров, вызываемых в инструкциях программы) до одного вызова с помощью аккумулятора «AC».

Решение в двух словах: Разработайте нашу машину/модель с неограниченной косвенной адресацией  – предоставьте неограниченный «адресный» регистр, который может потенциально называть (вызывать) любой регистр независимо от того, сколько их. Чтобы это работало, в общем случае неограниченный регистр должен иметь возможность очищаться, а затем увеличиваться (и, возможно, уменьшаться) потенциально бесконечным циклом. В этом смысле решение представляет собой неограниченный оператор μ , который может, при необходимости, охотиться до бесконечности по неограниченной строке регистров, пока не найдет то, что ищет. Регистр указателя точно такой же, как и любой другой регистр, за одним исключением: в обстоятельствах, называемых «косвенной адресацией», он предоставляет свое содержимое, а не адрес-операнд в ТАБЛИЦЕ конечного автомата, в качестве адреса целевого регистра (включая, возможно, себя самого!).

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

Наша более простая модель контрмашины может выполнять «ограниченную» форму косвенности — и тем самым вычислять подкласс примитивных рекурсивных функций  — используя примитивный рекурсивный «оператор», называемый «определением по случаям» (определен в Kleene (1952) стр. 229 и Boolos-Burgess-Jeffrey стр. 74). Такая «ограниченная косвенная адресация» — это трудоемкое, утомительное дело. «Определение по случаям» требует, чтобы машина определяла/различала содержимое регистра указателя, пытаясь раз за разом до успеха сопоставить это содержимое с числом/именем, которое оператор case явно объявляет. Таким образом, определение по случаям начинается, например, с нижнего граничного адреса и продолжается до тошноты в направлении верхнего граничного адреса, пытаясь выполнить сопоставление:

Число в регистре N равно 0? Если нет, то равно ли оно 1? 2? 3? ... 65364? Если нет, то мы находимся на последнем числе 65365, и лучше бы это было оно, иначе у нас проблема!

«Ограниченная» косвенная адресация не позволит нам вычислить частично рекурсивные функции — для них нам нужна неограниченная косвенная адресация, также известная как оператор μ .

Предположим, что мы смогли продолжить до числа 65367, и на самом деле в этом регистре было то, что мы искали. Тогда мы могли бы успешно завершить наши вычисления! Но предположим, что в 65367 нет того, что нам нужно. Как далеко мы должны продолжать идти?

Чтобы быть эквивалентной по Тьюрингу, счетчиковая машина должна либо использовать неудачный метод чисел Мински-Геделя с одним регистром , либо быть дополнена способностью исследовать концы своей регистровой строки, до бесконечности, если это необходимо. (Неспособность найти что-то «там» определяет, что означает для алгоритма неспособность завершиться; см. Kleene (1952) стр. 316 и далее, Глава XII Частично рекурсивные функции , в частности стр. 323-325.) Подробнее об этом см. в примере ниже.

Для неограниченной косвенности нам требуется «аппаратное» изменение в нашей модели машины. Как только мы сделаем это изменение, модель перестанет быть машиной-счетчиком, а станет машиной с произвольным доступом.

Теперь, когда указано, например, INC, инструкция конечного автомата должна будет указать, откуда будет получен адрес интересующего регистра. Это может быть либо (i) инструкция конечного автомата, которая предоставляет явную метку , либо (ii) регистр указателя , содержимое которого является интересующим адресом. Всякий раз, когда инструкция указывает адрес регистра, теперь ей также нужно будет указать дополнительный параметр «i/d» – «косвенный/прямой». В некотором смысле этот новый параметр «i/d» является «переключателем», который переключает один способ получения прямого адреса, как указано в инструкции, или другой способ получения косвенного адреса из регистра указателя (какой регистр указателя – в некоторых моделях каждый регистр может быть регистром указателя – указывается инструкцией). Этот «взаимоисключающий, но исчерпывающий выбор» является еще одним примером «определения по случаям», а арифметический эквивалент, показанный в примере ниже, выведен из определения в Kleene (1952) стр. 229.

Пример: CPY (косвенный _{источник} , r- _{источник} , прямое _{назначение} , r _{-назначение} )

Назначьте код для указания прямой адресации как d="0" и косвенной адресации как i="1". Тогда наша машина сможет определить исходный адрес следующим образом:

я*[р _с ] + (1-и)*р _с

Например, предположим, что содержимое регистра 3 равно «5» (т.е. [3]=5), а содержимое регистра 4 равно «2» (т.е. [4]=2):

Пример: CPY ( 1, 3, 0, 4 ) = CPY ( косвенный, рег 3, прямой, рег 4 )

1*[3] + 0*3 = [3] = адрес исходного регистра 5

0*[4] + 1*4 = 4 = адрес регистра назначения 4

Пример: CPY ( 0, 3, 0, 4 )

0*[3] + 1*3 = 3 = адрес исходного регистра 3

0*[4] + 1*4 = 4 = адрес регистра назначения 4

Пример: CPY ( 0, 3, 1, 4 )

0*[3] + 1*3 = 3 = адрес исходного регистра 3

1*[4] + 0*4 = [4] = адрес регистра назначения 2

Вероятно, наиболее полезной из добавленных инструкций является COPY. Действительно, Элгот-Робинсон (1964) снабжает свои модели P ₀ и P' ₀ инструкциями COPY, а Кук-Рекхоу (1973) снабжает свою модель на основе аккумулятора только двумя косвенными инструкциями – COPY в аккумулятор косвенно, COPY из аккумулятора косвенно.

Множество инструкций : поскольку любая инструкция, действующая на один регистр, может быть дополнена ее косвенным «дуалом» (включая условные и безусловные переходы, см. модель Элгота-Робинсона), включение косвенных инструкций удвоит количество инструкций с одним параметром/регистром (например, INC (d, r), INC (i, r)). Хуже того, каждая инструкция с двумя параметрами/регистром будет иметь 4 возможных варианта, например:

CPY (d, r _s , d, r _d ) = КОПИРОВАТЬ напрямую из исходного регистра напрямую в целевой регистр

CPY (i, r _sp , d, r _d ) = КОПИРОВАТЬ в регистр назначения косвенно, используя исходный адрес, который можно найти в регистре указателя источника r _sp .

CPY (d, r _s , i, r _dp ) = косвенно копировать содержимое исходного регистра в регистр, используя адрес назначения, который можно найти в регистре указателя назначения r _dp .

CPY (i, r _sp , i, r _dp ) = косвенно копировать содержимое исходного регистра с адресом, который находится в исходном указателе регистра r _sp , в целевой регистр с адресом, который находится в целевом указателе регистра r _dp )

Аналогичным образом каждая трехрегистровая инструкция, включающая два исходных регистра r _s1 r _s2 и целевой регистр r _d, приведет к 8 разновидностям, например, сложению:

[р _с1 ] + [р _с2 ] → р _д

даст:

• ДОБАВИТЬ ( д, р _с1 , д, р _с2 , д, р _д )
• ДОБАВИТЬ ( я, р _sp1 , д, р _s2 , д, р _d )
• ДОБАВИТЬ ( д, р _с1 , я, р _сп2 , д, р _д )
• ДОБАВИТЬ ( я, р _sp1 , я, р _sp2 , д, р _d )
• ДОБАВИТЬ ( д, р _с1 , д, р _с2 , я, р _дп )
• ДОБАВИТЬ ( i, r _sp1 , d, r _s2 , i, r _dp )
• ДОБАВИТЬ ( д, р _с1 , я, р _сп2 , я, р _дп )
• ДОБАВИТЬ ( я, р _sp1 , я, р _sp2 , я, р _dp )

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

Исторически сложилось так, что аккумулятору, «арифметическому органу», буквально накапливающему свое число в ходе последовательности арифметических операций, отводится отдельный регистр:

«Первая часть нашего арифметического органа... должна быть параллельным органом хранения, который может принимать число и прибавлять его к тому, которое уже в нем находится, который также может очищать свое содержимое и который может сохранять то, что он содержит. Мы будем называть такой орган Накопителем . Он в принципе вполне обычен в прошлых и настоящих вычислительных машинах самых разных типов, например, настольных умножителях, стандартных счетчиках IBM, более современных релейных машинах, ENIAC» (жирный шрифт в оригинале: Goldstine and von Neumann, 1946; стр. 98 в Bell and Newell 1971).

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

Если мы придерживаемся определенного имени для аккумулятора, например, «A», мы можем подразумевать аккумулятор в инструкциях, например,

INC ( А ) = ИНКА

Однако когда мы пишем инструкции CPY без вызова аккумулятора, инструкции становятся неоднозначными или должны иметь пустые параметры:

КПЮ ( д, р2, д, А ) = КПЮ (д, р2, , )

КПЮ ( д, А, д, р2 ) = КПЮ ( , , д, р2)

Исторически сложилось так, что эти две инструкции CPY получили различные названия; однако, никакого соглашения не существует. Традиция (например, воображаемый компьютер MIX Кнута (1973) ) использует два названия: LOAD и STORE. Здесь мы добавляем параметр "i/d":

LDA ( d/i, r _s ) = _def CPY ( d/i, r _s , d, A )

STA ( d/i, r _d ) = _def CPY ( d, A, d/i, r _d )

Типичная модель на основе аккумулятора будет иметь все свои арифметические и константные операции с двумя переменными (например, ADD (A, r), SUB (A, r)) использующие (i) содержимое аккумулятора вместе с (ii) содержимым указанного регистра. Операции с одной переменной (например, INC (A), DEC (A) и CLR (A)) требуют только аккумулятор. Оба типа инструкций помещают результат (например, сумму, разность, произведение, частное или остаток) в аккумулятор.

Пример: INCA = [A] +1 → A

Пример: ADDA (r _s ) = [A] + [r _s ] → A

Пример: MULA (r _s ) = [A] * [r _s ] → A

Если мы того пожелаем, мы можем сократить мнемонику, поскольку по крайней мере один исходный регистр, а регистр назначения всегда является аккумулятором A. Таким образом, мы имеем:

{ LDA (i/d, r _s ), STA (i/d, r _s ), CLRA, INCA, DECA, ADDA (r _s ), SUBA (r _s ), MULA (r _s ), DIVA (r _s ) , и т. д.)

Если в нашей модели есть неограниченный аккумулятор, можем ли мы связать все остальные регистры? Нет, пока мы не предоставим хотя бы один неограниченный регистр, из которого мы получим наши косвенные адреса.

Минималистский подход заключается в использовании самого себя (так делает Schönhage).

Другой подход (Шёнхаге делает это тоже) заключается в объявлении определенного регистра «косвенным адресным регистром» и ограничении косвенности относительно этого регистра (модель RAM0 Шёнхаге использует как регистры A, так и N для косвенных, а также прямых инструкций). И снова наш новый регистр не имеет общепринятого имени – возможно, «N» от «iNdex», или «iNdirect» или «address Number».

Для максимальной гибкости, как мы это сделали для аккумулятора A, мы будем считать N просто еще одним регистром, подлежащим увеличению, уменьшению, очистке, тестированию, прямому копированию и т. д. Опять же, мы можем сократить инструкцию до одного параметра, который обеспечивает, например, направление и косвенность.

LDAN (i/d) = CPY (i/d, N, d, A); Загрузка аккумулятора через регистр iNdirection

STAN (i/d) = CPY (d, A, i/d, N). Аккумулятор STore через регистр iNdirection

Почему это такой интересный подход? По крайней мере, по двум причинам:

(1) Набор инструкций без параметров:

Шёнхаге делает это для создания своего набора инструкций RAM0. См. раздел ниже.

(2) Уменьшить ОЗУ до машины Пост-Тьюринга:

Выдавая себя за минималистов, мы сокращаем все регистры, за исключением аккумулятора A и регистра косвенности N, например r = { r0, r1, r2, ... }, до неограниченной строки ячеек (очень) ограниченной емкости. Они не будут делать ничего, кроме как хранить (очень) ограниченные числа, например, один бит со значением { 0, 1 }. Аналогично мы сокращаем аккумулятор до одного бита. Мы ограничиваем любую арифметику регистрами { A, N }, используем косвенные операции для извлечения содержимого регистров в аккумулятор и записываем 0 или 1 из аккумулятора в регистр:

{ LDA (i, N), STA (i, N), CLR (A/N), INC (A/N), DEC(N), JZ (A/N, I _z ), JZ (I _z ), H }

Мы идем дальше и полностью устраняем A, используя два «константных» регистра, называемых «ERASE» и «PRINT»: [ERASE]=0, [PRINT]=1.

{ CPY (d, СТИРАНИЕ, i, N), CPY (d, ПЕЧАТЬ, i, N), CLR (N), INC (N), DEC (N), JZ (i, N, I _z ), JZ (I _z ), H }

Переименуем инструкции COPY и назовем INC (N) = RIGHT, DEC (N) = LEFT, и у нас будут те же инструкции, что и у машины Пост-Тьюринга, плюс дополнительная CLRN:

{ СТИРАНИЕ, ПЕЧАТЬ, CLRN, ВПРАВО, ВЛЕВО, JZ (i, N, I _z ), JZ (I _z ), H }

В разделе выше мы неформально показали, что RAM с неограниченной возможностью косвенной адресации создает машину Пост-Тьюринга . Машина Пост-Тьюринга эквивалентна машине Тьюринга, поэтому мы показали, что RAM с косвенной адресацией эквивалентна машине Тьюринга.

Мы приводим здесь немного более формальную демонстрацию. Начнем с проектирования нашей модели с тремя зарезервированными регистрами "E", "P" и "N", а также неограниченным набором регистров 1, 2, ..., n справа. Регистры 1, 2, ..., n будут считаться "квадратами ленты". Регистр "N" указывает на "сканируемый квадрат", который в данный момент наблюдает "головка". "Головку" можно рассматривать как находящуюся в условном переходе - обратите внимание, что она использует косвенную адресацию (ср. Elgot-Robinson, стр. 398). Когда мы уменьшаем или увеличиваем "N", (кажущаяся) головка будет "двигаться влево" или "вправо" вдоль квадратов. Мы переместим содержимое "E"=0 или "P"=1 в "сканируемый квадрат", на который указывает N, используя косвенный CPY.

Тот факт, что наша лента имеет левый конец, создает для нас небольшую проблему: всякий раз, когда появляется LEFT, наши инструкции должны будут проверить, равно ли содержимое «N» нулю; если это так, мы должны оставить его счетчик равным «0» (это наш выбор как проектировщиков — например, мы можем заставить машину/модель «вызвать событие» по нашему выбору).

Набор инструкций 1 (расширенный): { INC (N), DEC (N), CLR (N), CPY (d, r _s ,i, N), JZ ( i, r, z ), HALT }

Следующая таблица определяет инструкции Post-Turing в терминах их эквивалентных инструкций RAM и дает пример их функционирования. (Видимое) расположение головки вдоль ленты регистров r0-r5 . . . показано затененным:

На протяжении всей этой демонстрации мы должны помнить, что инструкции в таблице конечного автомата ограничены , т.е. конечны :

«Помимо того, что алгоритм представляет собой просто конечный набор правил , который задает последовательность операций для решения определенного типа задач, он обладает пятью важными характеристиками [Конечность, Определенность, Вход, Выход, Эффективность]» (курсив добавлен, Кнут, стр. 4-7).

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

Мы построим косвенный CPY (i, q, d, φ) с помощью оператора CASE. Адрес целевого регистра будет указан содержимым регистра "q"; как только оператор CASE определит, что это за число, CPY напрямую поместит содержимое регистра с этим числом в регистр "φ". Нам понадобится дополнительный регистр, который мы назовем "y" — он служит в качестве счетчика вверх.

Итак, нижеследующее на самом деле является конструктивной демонстрацией или доказательством того, что мы действительно можем смоделировать косвенный CPY (i, q, d, φ) без изменения «аппаратного» дизайна нашей машины/модели счетчика. Однако следует отметить, что поскольку этот косвенный CPY «ограничен» размером/объемом конечного автомата, RASP, использующий этот косвенный CPY, может вычислять только примитивные рекурсивные функции , а не полный набор рекурсивных функций mu .

"Оператор" CASE описан в работах Kleene (1952) (стр. 229) и Boolos-Burgess-Jeffrey (2002) (стр. 74); последние авторы подчеркивают его полезность. Следующее определение дано по Клини, но изменено, чтобы отразить знакомую конструкцию "IF-THEN-ELSE".

Оператор CASE «возвращает» натуральное число в φ в зависимости от того, какой «case» выполняется, начиная с «case_0» и последовательно проходя через «case_last»; если ни один случай не выполняется, то число, называемое «default» (также известное как «woops»), возвращается в φ (здесь x обозначает некоторый набор параметров, например, регистр q и строку r0, ... rlast )):

Определение по случаям φ( x , y):

• case_0: ЕСЛИ Q ₀ ( x , y) истинно, ТО φ ₀ ( x , y) ИНАЧЕ
• case_1: ЕСЛИ Q ₁ ( x , y) истинно, ТО φ ₁ ( x , y) ИНАЧЕ
• cases_2 по case_next_to_last: и т.д. . . . . . . . . ИНАЧЕ
• case_last: ЕСЛИ Q _last ( x , y) истинно, ТО φ _last ( x , y) ИНАЧЕ
• по умолчанию: do φ _default ( x , y)

Клини требует, чтобы все «предикаты» Q _n , которые выполняют тестирование, были взаимоисключающими – «предикаты» – это функции, которые выдают только { true, false } на выходе; Булос-Берджесс-Джеффри добавляют требование, чтобы случаи были «исчерпывающими».

Мы начинаем с числа в регистре q, которое представляет адрес целевого регистра. Но что это за число? «Предикаты» будут проверять его, чтобы узнать, одно испытание за другим: JE (q, y, z), за которым следует INC (y). Как только число определено явно, оператор CASE напрямую/явно копирует содержимое этого регистра в φ:

Определение по случаям CPY (i, q, d, φ) = _def φ (q, r0, ..., rlast, y) =

• case_0: ЕСЛИ CLR (y), [q] - [y]=0 ТО CPY ( r0, φ ), J (выход) ИНАЧЕ
• case_1: ЕСЛИ INC (y), [q] = [y]=1 ТО CPY (r1, φ), J (выход) ИНАЧЕ
• case_2 через case n: ЕСЛИ . . . ТО . . . ИНАЧЕ
• case_n: ЕСЛИ INC (y), [q] = [y]=n ТО CPY ( rn, φ ), J (выход) ИНАЧЕ
• case_n+1 to case_last: ЕСЛИ . . . ТО . . . ИНАЧЕ
• case_last: ЕСЛИ INC (y), [q] = [y]="last" ТО CPY ( rlast, φ ), J (выход) ИНАЧЕ
• по умолчанию: упс

Case_0 (базовый шаг рекурсии по y) выглядит так:

• случай_0 :

• CLR(y); установить регистр y = 0
• JE ( q, y, _φ0 )
• J ( случай_1 )

• _φ0: CPY (r0, φ)
• J ( выход )

• случай_1: и т.д.

Case_n (шаг индукции) выглядит следующим образом; помните, что каждое вхождение «n», «n+1», ..., «last» должно быть явным натуральным числом:

• случай_н :

• INC ( г )
• JE ( q, y, _φn )
• J ( case_n+1 )

• _φn: CPY ( rn, φ )
• J ( выход )

• case__n+1: и т.д.

Case_last останавливает индукцию и ограничивает оператор CASE (и тем самым ограничивает оператор «косвенного копирования»):

• case_last :

• INC ( г )
• JE ( q, y, _φlast )
• J ( упс )

• _φlast : CPY ( rlast, φ )
• J ( выход )

• упс: как нам справиться с попыткой выхода за пределы поля?
• выход: и т.д.

Если бы CASE мог продолжаться до бесконечности, это был бы оператор mu . Но он не может – «регистр состояний» его конечного автомата достиг своего максимального значения (например, 65365 = 11111111,11111111 ₂ ) или в его таблице закончились инструкции; в конце концов, это конечный автомат.

Распространенная модель Кука и Речкова немного похожа на модель Малцека с троичным регистром (написанную с использованием мнемоники Кнута — в исходных инструкциях не было мнемоники, за исключением TRA, Read, Print).

• LOAD ( C, rd ) ; C → rd, C — любое целое число

Пример: LOAD ( 0, 5 )очистит регистр 5.

• ADD ( rs1, rs2, rd ) ; [rs1] + [rs2] → rdрегистры могут быть одинаковыми или разными;

Пример: ADD ( A, A, A )удвоит содержимое регистра A.

• SUB ( rs1, rs2, rd ) ; [rs1] - [rs2] → rdрегистры могут быть одинаковыми или разными:

Пример: SUB ( 3, 3, 3 )очистит регистр 3.

• COPY ( i, rp, d, rd ) ; [[rp] ] → rd, Косвенно копирует содержимое исходного регистра, на который указывает регистр-указатель r _p, в целевой регистр.
• COPY ( d, rs, i, rp ) ; [rs] → [rp]. Скопировать содержимое исходного регистра r _s в целевой регистр, на который указывает регистр-указатель r _p .
• JNZ ( r, Iz ) ;Условный переход, если [r] положительно; т.е. ЕСЛИ [r] > 0 ТО перейти к инструкции z, иначе продолжить последовательность (Кук и Рекхоу называют это: «Передать управление строке m, если Xj > 0»)
• READ ( rd ) ;копировать «вход» в регистр назначения r _d
• PRINT ( rs ) ;скопировать содержимое исходного регистра r _s на «выход».

Шёнхаге (1980) описывает очень примитивную, атомизированную модель, выбранную им для доказательства эквивалентности его модели указателя SMM :

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

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

• LDA k ; k --> A , k — константа, явное число, например «47»
• LDA ( d, r ) ; [r] → A ;прямая загрузка А
• LDA ( i, r ) ; [[r]] → A ;косвенно нагружать А
• STA ( d, r ) ; [A] → r ;напрямую хранить A
• STA ( i, r ) ; [A] → [r] ;косвенно хранить A
• JEA ( r, z ) ; IF [A] = [r] then Iz else continue
• INCA ; [A] + 1 --> A

Модель RAM0 : машина RAM0 Шёнхаге имеет 6 инструкций, обозначенных одной буквой (шестая «C xxx», по-видимому, подразумевает «пропустить следующий параметр»). Шёнхаге обозначил аккумулятор буквой «z», «N» — «n» и т. д. Вместо мнемоники Шёнхаге мы будем использовать мнемонику, разработанную выше.

• (Z), CLRA: 0 → A
• (A), INCA: [A] +1 → A
• (N), CPYAN: [A] → N
• (A), LDAA: [[A]] → A ; содержимое A указывает на адрес регистра; поместить содержимое регистра в A
• (S), STAN: [A] → [N] ; содержимое N указывает на адрес регистра; поместить содержимое A в регистр, на который указывает N
• (C), JAZ ( z ): [A] = 0 then go to Iz ; неоднозначный в своем обращении

Косвенность происходит (i) от CPYAN (копирование/передача содержимого A в N), работающего с store_A_via_N STAN, и от (ii) особой инструкции косвенности LDAA ( [[A]] → [A] ).

Факт определения, что любая машина счетчика без неограниченного регистра-"адресного" регистра должна указывать регистр "r" по имени, указывает на то, что модель требует, чтобы "r" было конечным , хотя оно "неограниченно" в том смысле, что модель не подразумевает верхнего предела для количества регистров, необходимых для выполнения ее работы(работ). Например, мы не требуем r < 83 617 563 821 029 283 746, ни r < 2^1 000 001 и т. д.

Таким образом, наша модель может «расширять» число регистров, если это необходимо для выполнения определенного вычисления. Однако это означает , что любое число, до которого расширяется модель, должно быть конечным  – оно должно индексироваться натуральным числом: ω не является вариантом .

Мы можем обойти это ограничение, предоставив неограниченный регистр для указания адреса регистра, который указывает косвенный адрес.

• Реальная оперативная память
• Трансдихотомическая модель

• Эмулятор машины произвольного доступа
• Эмулятор машины произвольного доступа
• Эмулятор машины произвольного доступа

За некоторыми исключениями, эти ссылки совпадают со ссылками на Register machine .

• • Голдстайн, Герман Х. и фон Нейман, Джон, «Планирование и кодирование задач для электронного вычислительного прибора», Rep. 1947, Институт перспективных исследований , Принстон. Перепечатано на стр. 92–119 в Bell, C. Gordon и Newell, Allen (1971), Computer Structures: Readings and Examples , McGraw-Hill Book Company, Нью-Йорк. ISBN 0-07-004357-4 }. 
• Джордж Булос , Джон П. Берджесс , Ричард Джеффри (2002), Вычислимость и логика: четвертое издание , Cambridge University Press, Кембридж, Англия. Оригинальный текст Булоса-Джеффри был значительно переработан Берджессом: более продвинутый, чем вводный учебник. Модель «машины Abacus» подробно разработана в Главе 5 Вычислимость Abacus ; это одна из трех моделей, которые были подробно рассмотрены и сравнены – машина Тьюринга (все еще в исходной форме 4-кортежа Булоса) и рекурсия, две другие.
• Артур Беркс , Герман Голдстайн , Джон фон Нейман (1946), Предварительное обсуждение логического проектирования электронного вычислительного прибора , перепечатано на стр. 92 и далее в книге Гордона Белла и Аллена Ньюэлла (1971), Структуры компьютеров: материалы для чтения и примеры , издательство mcGraw-Hill Book Company, Нью-Йорк. ISBN 0-07-004357-4 . 
• Стивен А. Кук и Роберт А. Рекхоу (1973), Машины с ограниченным временем случайного доступа , Журнал компьютерных системных наук 7(4):354-375.
• Мартин Дэвис (1958), Вычислимость и неразрешимость , McGraw-Hill Book Company, Inc. Нью-Йорк.
• Кэлвин Элгот и Абрахам Робинсон (1964), Машины с произвольным доступом и хранимыми программами, подход к языкам программирования , Журнал Ассоциации вычислительной техники, т. 11, № 4 (октябрь 1964 г.), стр. 365–399.
• Дж. Хартманис (1971), «Вычислительная сложность машин с произвольным доступом и хранимыми программами», Математическая теория систем 5, 3 (1971) стр. 232–245.
• Джон Хопкрофт , Джеффри Ульман (1979). Введение в теорию автоматов, языки и вычисления , 1-е изд., Reading Mass: Addison-Wesley. ISBN 0-201-02988-X . Сложная книга, посвященная вопросам машинной интерпретации «языков», NP-полноты и т. д. 
• Стивен Клини (1952), Введение в метаматематику , North-Holland Publishing Company, Амстердам, Нидерланды. ISBN 0-7204-2103-9 . 
• Дональд Кнут (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). «Рекурсивная неразрешимость проблемы Поста «Тэг» и другие темы в теории машин Тьюринга». Анналы математики . 74 (3). Анналы математики, т. 74, № 3: 437– 455. doi :10.2307/1970290. JSTOR  1970290.
• Марвин Мински (1967). Вычисления: Конечные и бесконечные машины (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc.В частности, см. главу 11: Модели, подобные цифровым компьютерам и главу 14: Очень простые основы вычислимости . В первой главе он определяет «Программные машины», а в последней главе обсуждает «Универсальные программные машины с двумя регистрами» и «...с одним регистром» и т. д.
• Джон К. Шепердсон и Х. Э. Стерджис (1961) получили в декабре 1961 г. Computability of Recursive Functions , Journal of the Association for Computing Machinery (JACM) 10:217-255, 1963. Чрезвычайно ценная справочная статья. В своем Приложении А авторы цитируют 4 других со ссылкой на "Minimality of Instructions Used in 4.1: Comparison with Similar Systems".

• Капенгст, Хайнц, 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. Матем.-Физ. Семстерберихте (Геттинген) 4 (1954), 42–53.

• Арнольд Шёнхаге (1980), Машины модификации памяти , Общество промышленной и прикладной математики, SIAM J. Comput. Том 9, № 3, август 1980 г. При этом Шёнхаге показывает эквивалентность своей МММ с «преемницей RAM» (машиной с произвольным доступом) и т. д., соответственно. Машины модификации памяти , в Теоретической информатике (1979), стр. 36–37
• Peter van Emde Boas , "Machine Models and Simulations" стр. 3–66, в: Jan van Leeuwen , ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity , The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (volume A). QA 76.H279 1990. Трактовка SMMs ван Эмде Боаса представлена ​​на стр. 32–35. Эта трактовка проясняет Schōnhage 1980 – она близко следует, но немного расширяет трактовку Schōnhage. Обе ссылки могут быть необходимы для эффективного понимания. 
• Хао Ван (1957), Вариант теории вычислительных машин Тьюринга , JACM (Журнал Ассоциации вычислительной техники) 4; 63-92. Представлено на заседании Ассоциации 23–25 июня 1954 г.