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

Не путать с оперативной памятью .

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

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

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

Неофициальное описание

RA-машина состоит из:

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

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

Введение в модель

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

Формальное определение

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

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

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

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

Пример: [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) предлагают визуализацию многоленточной машины Тьюринга с таким количеством лент с левым концом, сколько «регистров». Длина каждой ленты не ограничена справа, и каждый квадрат пуст, за исключением левого конца, который отмечен. Расстояние . «головы» ленты от ее левого конца, измеряемое в количестве квадратов ленты, представляет собой натуральное число в «регистре» Чтобы уменьшить количество квадратов, головка ленты перемещается влево; INCrement он перемещается вправо. Нет необходимости печатать или стирать пометки на ленте; единственные условные инструкции - проверить, находится ли головка на левом конце, проверив отметку левого конца с помощью инструкции «Перейти, если отмечено».

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

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

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

• { INCrement содержимого регистра r, DECrement содержимого регистра r, ЕСЛИ содержимое регистра r равно нулю, ТОГДА переход к инструкции I _z ELSE переход к следующей инструкции }:

Инструкция	Мнемоника	Действие над регистром(ами) "r"	Действие над регистром инструкций конечного автомата, IR
INCrement	ИНК ( р )	[г] + 1 → р	[ИС] + 1 → ЕСТЬ
DECrement	ДЕКАБРЬ ( р )	[г] - 1 → р	[ИС] + 1 → ЕСТЬ
Перейти, если ноль	JZ (р, z)	никто	ЕСЛИ [r] = 0 ТО z → IR ИНАЧЕ [IR] + 1 → IR
Остановиться	ЧАС	никто	[ИСТ] → ЕСТЬ

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

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

Инструкция	Мнемоника	Действие над регистром(ами) "r"	Действие над регистром инструкций конечного автомата, IR
Прозрачный	CLR ( р )	0 → р	[ИС] + 1 → ЕСТЬ
INCrement	ИНК ( р )	[г] + 1 → р	[ИС] + 1 → ЕСТЬ
Перейти, если равно	ИС (r1, r2, z)	никто	ЕСЛИ [r1] = [r2] ТО z → IR ИНАЧЕ [IR] + 1 → IR
Остановиться	ЧАС	никто	[ИСТ] → ЕСТЬ

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

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

Инструкция	Мнемоника	Действие над регистром(ами) "r"	Действие над регистром инструкций конечного автомата, IR
КОПИРОВАТЬ	КОПИРОВАТЬ (r1, r2)	[г1] → г2	[ИС] + 1 → ЕСТЬ
INCrement	ИНК ( р )	[г] + 1 → р	[ИС] + 1 → ЕСТЬ
Перейти, если равно	ИС (r1, r2, z)	никто	ЕСЛИ [r1] = [r2] ТО z → IR ИНАЧЕ [IR] + 1 → IR
Остановиться	ЧАС	никто	[ИСТ] → ЕСТЬ

Создание «удобных инструкций» из базовых наборов

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

Более того, из базовых наборов 1, 2 или 3 мы можем создать любую ( примитивно-рекурсивную функцию см. Мински (1967), Булос-Берджесс-Джеффри (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 – Перейти, если не ноль вместо JZ; еще одна возможная удобная инструкция).

«Косвенная» операция

Пример косвенной адресации

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

Пример: Охота за сокровищами.

В локации «Tom_&_Becky's_cave_in_pirate_chest» мы сможем найти карту, направляющую нас к «сокровищу»:

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

(2) Внутри коробки находится карта расположения сокровищ: «under_Thatcher's_front_porch».

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

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

Почему необходима непрямая операция: две основные проблемы противомашинной модели

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

• Мелзак (1961) добавил косвенность к своей модели «отверстий и камешков», чтобы его модель могла модифицироваться с помощью «вычисленного перехода», и приводит два примера ее использования («Десятичное представление в масштабе d» и «Сортировка по величина», используются ли они в его доказательстве того, что модель эквивалентна Тьюрингу, неясно, поскольку «сама программа оставлена ​​читателю в качестве упражнения» (стр. 292)). Мински (1961, 1967) смог продемонстрировать, что при подходящем (но сложном в использовании) кодировании чисел Гёделя регистровая модель не нуждается в косвенности, чтобы быть эквивалентной по Тьюрингу; но для этого нужен хотя бы один неограниченный регистр. Как отмечено ниже, Мински (1967) намекает на проблему RASP, но не предлагает решения. Элгот и Робинсон (1964) доказали, что их модель RASP P ₀ – она не имеет возможности косвенного обращения – не может вычислить все «рекурсивные последовательные функции» (те, которые имеют параметры произвольной длины), если она не имеет возможности изменять свои собственные инструкции. но если это так, то это можно сделать с помощью чисел Гёделя (стр. 395-397; в частности, рисунок 2 и сноска, стр. 395). С другой стороны, их модель RASP P' _0, оснащенный «индексным регистром» (косвенная адресация), может вычислять все «частично рекурсивные последовательные функции» (мю-рекурсивные функции) (стр. 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, «универсальную машину» (подробнее см. в разделе « Универсальная машина Тьюринга »), которая использует свой конечный автомат для интерпретации «программы инструкций», расположенных в ее регистрах — т.е. мы создаем то, что сегодня называют компьютером с архитектурой фон Неймана .

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

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

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

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

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

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

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

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

Ограниченная косвенность и примитивно-рекурсивные функции

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

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

Число в регистре 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". Тогда наша машина сможет определить адрес источника следующим образом:

i*[r _s ] + (1-i)*r _s

Например, предположим, что содержимое регистра 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

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

Множество инструкций : поскольку любая инструкция, действующая на один регистр, может быть дополнена ее косвенным «двойным» (включая условные и безусловные переходы, ср. модель Элгота-Робинсона), включение косвенных инструкций удвоит количество одиночных параметров. инструкции регистра (например, 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. _дп )

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

[r _s1 ] + [r _s2 ] → r _d

даст:

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

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

Понятие «аккумулятор А».

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

«Первая часть нашего арифметического органа... должна быть параллельным органом хранения, который может принимать число и добавлять его к уже находящемуся в нем, который также способен очищать его содержимое и который может хранить то, что оно содержит. Мы будем назовите такой орган аккумулятором . В принципе, он вполне условен в прошлых и нынешних вычислительных машинах самых разных типов, например, в настольных умножителях, стандартных счетчиках IBM, более современных релейных машинах, ENIAC» (жирный шрифт в оригинале: Голдстайн и фон Нейман). , 1946; стр. 98 в Белл и Ньюэлл, 1971).

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

Этикетка	Инструкция		А	р2	378 426 рэндов	Описание
			. . .	378,426	17
INci (r2):	CPY ( я, r2, d, A )		17	378,426	17	Содержимое r2 указывает на r378 426 с содержимым «17»: скопируйте это в A.
	ИНК ( А )		18	378,426	17	Содержание цемента A
	CPY (д, А, я, г2)		18	378,426	18	Содержимое r2 указывает на r378 426: скопируйте содержимое A в r378 426.

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

ВКЛЮЧЕНО ( А ) = ВКЛЮЧЕНО

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

CPY ( d, r2, d, A ) = CPY (d, r2, , )

CPY ( d, A, d, r2 ) = CPY ( , , d, r2)

Исторически сложилось так, что эти две инструкции CPY получили разные имена; однако никакой конвенции не существует. Традиция (например, Кнута (1973) воображаемый компьютер MIX ) использует два названия: ЗАГРУЗКА и ХРАНЕНИЕ. Здесь мы добавляем параметр «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 (rs ₎ = [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 ) , и т. д.)

Понятие регистра косвенного адреса «N».

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

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

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

Для максимальной гибкости, как мы это сделали для аккумулятора 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, ERASE, i, N), CPY (d, PRINT, i, N), CLR (N), INC (N), DEC (N), JZ (i, N, I _z ), JZ ( я _з ), Ч }

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

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

Тьюринговская эквивалентность оперативной памяти с косвенностью

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

Мы даем здесь несколько более формальную демонстрацию. Начните с разработки нашей модели с тремя зарезервированными регистрами «E», «P» и «N», а также неограниченным набором регистров 1, 2, ..., n справа. Регистры 1, 2, ..., n будем считать «квадратами ленты». Регистр «N» указывает на «отсканированный квадрат», который в данный момент наблюдает «голова». «Голову» можно рассматривать как находящуюся в условном переходе – обратите внимание, что она использует косвенную адресацию (ср. Элгот-Робинсон, стр. 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 }

В следующей таблице определены инструкции Пост-Тьюринга с точки зрения их эквивалентных инструкций в ОЗУ, а также приведен пример их функционирования. (Видимое) расположение головки на ленте регистров r0-r5. . . показан заштрихованным:

Мнемоника	этикетка:			И	П	Н		р0	р1	р2	р3	р4	р5	и т. д.	Действия над регистрами	Действие на конечном автомате Инструкция Регистр IR
	начинать:			0	1	3					1	0
Р	верно:	ИНК ( Н )		0	1	4					1	0			[Н] +1 → Н	[ИС] +1 → ИС
П	распечатать:	CPY (д, П, я, Н)		0	1	4					1	1			[P]=1 → [N]=r4	[ИС] +1 → ИС
И	стереть:	CPY (д, Е, я, Н)		0	1	4					1	0			[Е]=0 → [Н]=r4	[ИС] +1 → ИС
л	левый:	JZ (я, N, конец)		0	1	4					1	0			никто	IF N =r4] =0 THEN «конец» → IR else [IR]+1 → IR
		ДЕКАБРЬ ( Н )		0	1	3					1	0			[Н] -1 → Н
J0 (стоп)	jump_if_blank:	JZ (я, N, конец)		0	1	3					1	0			никто	ЕСЛИ N =r3] =0 ТО «конец» → ИР иначе [ИР]+1 → ИР
J1 (стоп)	jump_if_mark:	JZ (я, Н, хромой)		0	1	3					1	0			N =r3] → А	ЕСЛИ N =r3] =0 ТО «конец» → ИР иначе [ИР]+1 → ИР
	конец	. . . и т. д.		0	1	3					1	0
	остановка:	ЧАС		0	1	3					1	0			никто	[ИС] +1 → ИС

Пример: ограниченная косвенность дает машину, которая не является эквивалентом Тьюринга.

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

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

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

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

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

«Оператор» CASE описан у Клини (1952) (стр. 229) и у Булоса-Берджесса-Джеффри (2002) (стр. 74); последние авторы подчеркивают его полезность. Следующее определение дано Клини, но изменено, чтобы отразить знакомую конструкцию «ЕСЛИ-ТО-ЛИБО».

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

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

• case_0: ЕСЛИ Q ₀ ( x , y) истинно, ТО φ ₀ ( x , y) ИНАЧЕ
• случай_1: ЕСЛИ Q ₁ ( x , y) истинно, ТО φ ₁ ( x , y) ИНАЧЕ
• от Case_2 до Case_next_to_last: и т. д. . . . . . . . . ЕЩЕ
• case_last: ЕСЛИ Q _{последний} ( x , y) истинно, ТО φ _{последний} ( x , y) ELSE
• по умолчанию: сделать φ _{по умолчанию} ( 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: IF CLR (y), [q] - [y]=0 THEN CPY ( r0, φ ), J (выход) ELSE
• case_1: IF INC (y), [q] = [y]=1 THEN CPY ( r1, φ ), J (выход) ELSE
• от случая_2 до случая n: ЕСЛИ . . . ЗАТЕМ . . . ЕЩЕ
• case_n: IF INC (y), [q] = [y]=n THEN CPY ( rn, φ ), J (выход) ELSE
• от случая_n+1 до случая_последний: ЕСЛИ . . . ЗАТЕМ . . . ЕЩЕ
• case_last: IF INC (y), [q] = [y]="last" THEN CPY ( rlast, φ ), J (выход) ELSE
• по умолчанию: упс

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

• случай_0 :

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

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

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

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

• случай_n :

• ИНК ( у )
• IS ( q, y, _φn )
• J ( case_n+1 )

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

• случай__n+1: и т. д.

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

• случай_последний :

• ИНК ( у )
• Я (q, y, _φlast )
• Джей ( упс )

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

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

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

Примеры моделей

Модель «регистр-регистр» («чтение-изменение-запись») Кука и Рекхау (1973)

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

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

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

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

Пример: ADD ( 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] положительно; т.е. IF [r] > 0 THEN переход к инструкции z, иначе продолжайте последовательность (Кук и Рекхау называют это: «Перенести управление на строку m, если Xj > 0»)
• READ ( rd ) ; скопировать «вход» в регистр назначения r _d
• PRINT ( rs ) ; скопируйте содержимое исходного регистра r _на «выход».

RAM0 и RAM1 Шёнхаге (1980)

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

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

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

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

Модель RAM0 : машина RAM0 Шёнхаге имеет 6 инструкций, обозначаемых одной буквой (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 .

• • Голдстайн, Герман Х. и фон Нейман, Джон, «Планирование и кодирование задач для электронного вычислительного прибора», член палаты представителей 1947 г., Институт перспективных исследований , Принстон. Перепечатано на стр. 92–119 в книгах Белл, К. Гордон и Ньюэлл, Аллен (1971), Компьютерные структуры: материалы для чтения и примеры , McGraw-Hill Book Company, Нью-Йорк. ISBN   0-07-004357-4 }.
• Джордж Булос , Джон П. Берджесс , Ричард Джеффри (2002), Вычислимость и логика: четвертое издание , Издательство Кембриджского университета, Кембридж, Англия. Оригинальный текст Булоса-Джеффри был тщательно переработан Берджессом: он более продвинут, чем вводный учебник. Модель «счетной машины» подробно описана в главе 5 «Вычислимость счетов» ; это одна из трех моделей, которые тщательно рассматривались и сравнивались: машина Тьюринга (все еще в исходной четырехкортежной форме Булоса) и две другие рекурсивные модели.
• Артур Беркс , Герман Голдстайн , Джон фон Нейман (1946), Предварительное обсуждение логического проектирования электронного вычислительного прибора , перепечатано на стр. 92 и далее в книге Гордона Белла и Аллена Ньюэлла (1971), Компьютерные структуры: материалы для чтения и примеры , книга МакГроу-Хилла Компания, Нью-Йорк. ISBN   0-07-004357-4 .
• Стивен А. Кук и Роберт А. Рекхоу (1973), Машины произвольного доступа с ограниченным временем , Журнал компьютерных системных наук 7 (4): 354-375.
• Мартин Дэвис (1958), «Вычислимость и неразрешимость» , McGraw-Hill Book Company, Inc., Нью-Йорк.
• Кэлвин Элгот и Авраам Робинсон (1964), Машины с произвольным доступом к хранимым программам, подход к языкам программирования , Журнал Ассоциации вычислительной техники, Vol. 11, № 4 (октябрь 1964 г.), стр. 365–399.
• Дж. Хартманис (1971), «Вычислительная сложность машин с хранимыми программами произвольного доступа», Mathematical Systems Theory 5, 3 (1971), стр. 232–245.
• Джон Хопкрофт , Джеффри Уллман (1979). Введение в теорию автоматов, языки и вычисления , 1-е изд., Чтение мессы: Аддисон-Уэсли. ISBN   0-201-02988-X . Сложная книга, посвященная вопросам машинной интерпретации «языков», NP-полноты и т. д.
• Стивен Клини (1952), «Введение в метаматематику» , Издательство Северной Голландии, Амстердам, Нидерланды. ISBN   0-7204-2103-9 .
• Дональд Кнут (1968), Искусство компьютерного программирования , второе издание, 1973 г., Аддисон-Уэсли, Ридинг, Массачусетс. См. страницы 462–463, где он определяет «новый вид абстрактной машины или «автомата», который имеет дело со связанными структурами».
• Иоахим Ламбек (1961, получено 15 июня 1961 г.), Как запрограммировать бесконечные счеты , Mathematical Bulletin, vol. 4, нет. 3. Сентябрь 1961 г., страницы 295–302. В своем Приложении II Ламбек предлагает «формальное определение «программы». Он ссылается на Melzak (1961) и Kleene (1952) « Введение в метаматематику» .
• З.А. Мельзак (1961, получено 15 мая 1961 г.), Неофициальный арифметический подход к вычислимости и вычислениям , Canadian Mathematical Bulletin , vol. 4, нет. 3. Сентябрь 1961 г., страницы 279–293. Мельзак не приводит никаких ссылок, но признает «пользу бесед с докторами Р. Хэммингом, Д. Макилроем и В. Высоцем из телефонных лабораторий Bell и с доктором Х. Вангом из Оксфордского университета».
• Марвин Мински (1961). «Рекурсивная неразрешимость проблемы Поста о «теге» и других тем теории машин Тьюринга». Анналы математики . 74 (3). Анналы математики, Vol. 74, № 3: 437–455. дои : 10.2307/1970290 . JSTOR   1970290 .
• Марвин Мински (1967). Вычисления: конечные и бесконечные машины (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc. В частности, см. главу 11: Модели, подобные цифровым компьютерам , и главу 14: Очень простые основы вычислительности . В первой главе он дает определение «программным машинам», а в следующей главе обсуждает «универсальные программные машины с двумя регистрами» и «... с одним регистром» и т. д.
• Джон К. Шепердсон и Х. Э. Стерджис (1961) получили в декабре 1961 года «Вычислимость рекурсивных функций» , журнал Ассоциации вычислительной техники (JACM) 10:217-255, 1963. Чрезвычайно ценный справочный документ. В Приложении А авторы цитируют еще 4 со ссылкой на «Минимальность инструкций, используемых в 4.1: Сравнение с аналогичными системами».

• Капенгст, Хайнц, Абстрактная вычислительная машина с программным управлением» , Журнал математической логики и основ математики: 5 (1959), 366–379.
• Ershov, A. P. On operator algorithms , (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
• Петер, Рожа Графовые схемы и рекурсивные функции , Dialectica 12 (1958), 373.
• Гермес, Ганс Универсальность вычислительных машин с программным управлением. Матем.-Физ. Отчеты за семестр (Геттинген) 4 (1954), 42–53.

• Арнольд Шёнхаге (1980), Машины для модификации памяти , Общество промышленной и прикладной математики, SIAM J. Comput. Том. 9, № 3, август 1980 г., в котором Шёнхаге показывает эквивалентность своего SMM «преемнику RAM» (машине произвольного доступа) и т. д. соотв. Машины для модификации хранилища , в журнале Theoretical Computer Science (1979), стр. 36–37.
• Питер ван Эмде Боас , «Модели машин и моделирование», стр. 3–66, в: Ян ван Леувен , изд. Справочник по теоретической информатике. Том A: Алгоритмы и сложность , MIT PRESS/Elsevier, 1990. ISBN   0-444-88071-2 (том А). QA 76.H279 1990. Подход ван Эмде Боаса к SMM представлен на стр. 32–35. Эта трактовка проясняет Шёнхаге 1980: она близко следует, но немного расширяет трактовку Шёнхаге. Обе ссылки могут быть необходимы для эффективного понимания.
• Хао Ван (1957), Вариант теории вычислительных машин Тьюринга , JACM (Журнал Ассоциации вычислительной техники) 4; 63-92. Представлено на заседании Ассоциации 23–25 июня 1954 г.