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

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Ноябрь 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

RASP - это модель машины с произвольным доступом (RAM), которая, в отличие от RAM, имеет свою программу в своих «регистрах» вместе со своими входными данными. Регистры не ограничены (бесконечны по объему); Конечность числа регистров зависит от модели. Таким образом, RASP является ОЗУ , как универсальная машина Тьюринга является на машине Тьюринга . RASP - это пример архитектуры фон Неймана, тогда как RAM - пример гарвардской архитектуры .

RASP наиболее близка из всех абстрактных моделей к общепринятому понятию компьютера . Но в отличие от реальных компьютеров модель RASP обычно имеет очень простой набор инструкций, значительно сокращенный от инструкций процессоров CISC и даже RISC до простейших арифметических операций, инструкций «перемещений» из регистра в регистр и инструкций «тест / переход». В некоторых моделях есть несколько дополнительных регистров, например, аккумулятор .

Вместе с регистровой машиной , ОЗУ и указательной машиной RASP составляет четыре общие модели последовательной машины , названные так, чтобы отличать их от «параллельных» моделей (например, параллельной машины с произвольным доступом ) [см. ван Эмде Боас (1990)].

Неформальное определение: модель хранимой программы с произвольным доступом (RASP) [ править ]

Краткое описание RASP:

RASP - это универсальная машина Тьюринга (UTM), построенная на шасси RAM машины с произвольным доступом .

Читатель помнит, что UTM - это машина Тьюринга.с «универсальной» таблицей инструкций с конечным числом состояний, которая может интерпретировать любую хорошо сформированную «программу», записанную на ленте, как строку 5-кортежей Тьюринга, отсюда ее универсальность. В то время как классическая модель UTM ожидает найти на своей ленте 5-кортежи Тьюринга, любой вообразимый набор программ может быть помещен туда при условии, что машина Тьюринга ожидает их найти - учитывая, что ее таблица конечных состояний может интерпретировать их и преобразовывать в желаемое действие. Наряду с программой на ленте будут напечатаны входные данные / параметры / числа (обычно справа от программы) и, в конечном итоге, выходные данные / числа (обычно справа от обоих, либо смешанные с вводом, либо заменяющие его. ). «Пользователь» должен расположить голову машины Тьюринга над первой инструкцией,и ввод должен быть помещен в указанное место и формат, соответствующий как программе на магнитной ленте, так и таблице команд конечного автомата.

RASP имитирует эту конструкцию: он помещает «программу» и «данные» в отверстия (регистры). Но, в отличие от UTM, RASP последовательно «извлекает» свои инструкции, если условный тест не отправляет их куда-то еще.

Путаница: два набора инструкций : в отличие от UTM, модель RASP имеет два набора инструкций - таблица инструкций конечного автомата («интерпретатор») и «программа» в отверстиях. Два набора не обязательно должны быть взяты из одного набора.

Пример RAM, работающего как RASP [ править ]

Следующий пример программы переместит содержимое регистра (отверстие) # 18 в регистр (отверстие) # 19, стирая при этом содержимое регистра # 18.

 5:  03  18  15  JZ  18 , 15  ; если [18] равно нулю, перейдите к 15, чтобы завершить программу  02  18  DEC  18  ; Уменьшение [18]  01  19  INC  19  ; Приращение [19]  03  15  05  JZ  15 ,  5  ; Если [15] равно нулю, перейдите к 5, чтобы повторить цикл (используйте Halt для имитации безусловного перехода)  15:  00  H  ; Остановка 18:  n  ; Исходное значение для копии  19  :; Место для копирования

Программа -Инструкции доступны в этой RASP машине будет простой набор , чтобы пример короче:

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

Чтобы упростить пример, мы оснастим конечный автомат RAM-as-RASP примитивными инструкциями, взятыми из того же набора, но дополненными двумя инструкциями косвенного копирования:

Инструкции конечного автомата RAM:

{ Дюйм; DEC h; JZ h, xxx; CPY << h _a >>, <h _a >; CPY <h _a >, << h _a >>}

Что именно будет делать конечный автомат, когда конечный автомат машины RASP интерпретирует программу в регистрах? Столбец с восклицательным знаком! отобразит во временной последовательности действия конечного автомата, поскольку он «интерпретирует» - преобразует в действие - программу:

	ПК	ИК
отверстие # →	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
программа, параметры →	5				JZ	18	15	DEC	18	INC	19	JZ	15	5	ЧАС			п
закодированная программа →	5				3	18	15	2	18	1	19	3	15	5	0			п
инструкции конечного автомата ↓

!

Традиция делит действия конечного автомата на две основные «фазы», которые называются « выборка» и « выполнение» . Ниже мы увидим, что в этих двух основных фазах есть «подэтапы». Согласованной конвенции нет; каждая модель требует своего точного описания.

Фаза получения [ править ]

Конечный автомат имеет доступ ко всем регистрам как прямо, так и косвенно. Таким образом, он принимает №1 в качестве «программного счетчика» ПК. Роль счетчика программы будет заключаться в том, чтобы «сохранить место» в листинге программы; Государственный автомат имеет собственный государственный реестр для личного пользования.

При запуске конечный автомат ожидает найти номер на ПК - первую «Программу-инструкцию» в программе (то есть в № 5).

(Без использования косвенных копий задача переноса указанной программной инструкции в # 2 является немного сложной. Конечный автомат будет косвенно уменьшать указанный регистр при прямом увеличении (пустого) регистра # 2. на этапе "синтаксического анализа" он восстановит принесенное в жертву содержимое # 5, жертвуя счетчиком в # 2.)

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

копировать косвенно из i и напрямую в j: CPY << h _i >>, <h _j >
копировать прямо из i и косвенно в j: CPY <h _i >, << h _j >>

В следующем примере показано, что происходит во время фазы "выборки" конечного автомата. Операции конечного автомата перечислены в столбце «Инструкция конечного автомата ↓». Обратите внимание, что в конце выборки регистр 2 содержит числовое значение 3 «кода операции» («код операции») первой инструкции JZ :

			ПК	PIR
		отверстие # →	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
		программа, параметры →	5				JZ	18	15	DEC	18	INC	19	JZ	15	5	ЧАС			п
		закодированная программа →	5				3	18	15	2	18	1	19	3	15	5	0			п
шаг		инструкции конечного автомата ↓

1	fetch_instr:	CPY <<1>>, <2>	5 я	[3]			[3]	18	15	2	18	1	19	3	15	5	0			п

Фаза синтаксического анализа [ править ]

Теперь, когда номер программы-инструкции (например, 3 = "JZ") находится в регистре №2 - "Регистр программ-инструкций" PIR - конечный автомат продолжает уменьшать номер до тех пор, пока IR не станет пустым:

Если бы IR был пуст перед декрементом, тогда программная инструкция была бы 0 = HALT, и машина перешла бы к своей подпрограмме «HALT». После первого декремента, если отверстие было пустым, инструкция была бы INC, и машина перешла бы к инструкции "inc_routine". После второго декремента пустой IR будет представлять DEC, и машина перейдет к «dec_routine». После третьего декремента IR действительно пуст, и это вызывает переход к подпрограмме "JZ_routine". Если бы неожиданный номер все еще находился в IR, то машина обнаружила бы ошибку и могла бы ОСТАНОВИТЬСЯ (например).

			ПК	ИК
		отверстие # →	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
		программа, параметры →	5				JZ	18	15	DEC	18	INC	19	JZ	15	5	ЧАС			п
		закодированная программа →	5				3	18	15	2	18	1	19	3	15	5	0			п
		инструкции конечного автомата ↓

		CPY <<1>>, <2>	5 я	[3]			[3]	18	15	2	18	1	19	3	15	5	0			п
		JZ 2, остановка	5	3			3	18	15	2	18	1	19	3	19	5	0			п
3		2 декабря	5	2			3	18	15	2	18	1	19	3	15	5	0			п
4		JZ 2, inc_routine:	5	2			3	18	15	2	18	1	19	3	15	5	0			п
5		2 декабря	5	1			3	18	15	2	18	1	19	3	15	5	0			п
6		JZ 2, dec_routine	5	1			3	18	15	2	18	1	19	3	15	5	0			п
7		2 декабря	5	0			3	18	15	2	18	1	19	3	15	5	0			п
8		JZ 2, JZ_routine	5	0!
-	остановка:	HALT	5	3			3	18	15	2	18	1	19	3	15	5	0			п
-	inc_routine:	и т.п.	5	3			3	18	15	2	18	1	19	3	15	5	0			п
-	dec_routine:	и т.п.	5	3			3	18	15	2	18	1	19	3	15	5	0			п
9	JZ_routine:	и т.п.	5	3			3	18	15	2	18	1	19	3	15	5	0			п

Фаза выполнения, JZ_routine [ править ]

Теперь конечный автомат знает, какую программу-инструкцию выполнять; действительно, он перешел к последовательности инструкций "JZ_routine". Инструкция JZ имеет 2 операнда - (i) номер регистра для проверки и (ii) адрес, по которому нужно перейти, если проверка прошла успешно (отверстие пусто).

(i) Выборка операнда - какой регистр проверять на пустоту? : Аналогично фазе выборки, конечный автомат перемещает содержимое регистра, на который указывает ПК, то есть отверстие №6, в регистр программных инструкций PIR №2. Затем он использует содержимое регистра № 2, чтобы указать на регистр, который нужно проверить на ноль, то есть регистр № 18. Отверстие № 18 содержит номер «n». Теперь для проведения теста конечный автомат использует содержимое PIR для косвенного копирования содержимого регистра № 18 в резервный регистр № 3. Итак, есть две возможности (ia), регистр № 18 пуст, (ib) регистр № 18 не пуст.

(ia): Если регистр № 3 пуст, конечный автомат переходит к (ii) Выборка второго операнда - выбор адреса перехода.

(ib): Если регистр # 3 не пуст, конечный автомат может пропустить (ii) выборку второго операнда. Он просто увеличивает в два раза PC, а затем безоговорочно возвращается к фазе выборки инструкций, где она выбирает программную инструкцию # 8 (DEC).

(ii) Выборка операнда - адрес перехода . Если регистр № 3 пуст, конечный автомат продолжает использовать ПК для косвенного копирования содержимого регистра, на который он указывает (№ 8), в себя . Теперь ПК сохраняет адрес перехода 15. Затем конечный автомат безоговорочно возвращается к фазе выборки инструкций, где он выбирает программную инструкцию # 15 (HALT).

			ПК	ИК
		отверстие # →	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
		программа, параметры →	5				JZ	18	15	DEC	18	INC	19	JZ	15	5	ЧАС			п
		закодированная программа →	5				3	18	15	2	18	1	19	3	15	5	0			п
шаг		инструкции конечного автомата ↓

9	JZ_routine	INC 1	[6]	3			3	18	15	2	18	1	19	3	15	5	0			п
10		CPY <<1>>, <2>	6 я	[18]			3	[18]	15	2	18	1	19	3	15	5	0			п
11	тестовое отверстие:	CPY <<2>>, <3>	6	18 я	[n]		3	18	15	2	18	1	19	3	15	5	0			[n]
12	тестовое отверстие:	JZ 3, прыжок	6	18 я	[n]		3	18	15	2	18	1	19	3	15	5	0			п
					п															п
13	no_jump:	INC 1	[7]	18	п		3	18	15	2	18	1	19	3	15	5	0			п
14		INC 1	[8]	18	п		3	18	15	2	18	1	19	3	15	5	0			п
15		J fetch_instr	8	18	п		3	18	15	2	18	1	19	3	15	5	0			п
1	fetch_instr:	CPY <<1>>, <2>	8 я	[2]	п		3	18	15	[2]	18	1	19	3	15	5	0			п
2	разобрать:	и т.п.

13	Прыжок:	INC 1	[7]	18	п		3	18	15	2	18	1	19	3	15	5	0			п
14		CPY <<1>>, <1>	[15]	18	п		3	18	[15]	2	18	1	19	3	15	5	0			п
15		J fetch_instr	15	18	п		3	18	15	2	18	1	19	3	15	5	0			п
1	fetch_instr:	CPY <<1>>, <2>	15 я	[0]	п		3	18	15	2	18	1	19	3	15	5	[0]			п
2	разобрать:	и т.п.

Выполнить этап INC, DEC [ править ]

Следующее завершает интерпретацию программных инструкций конечным автоматом RAM, INC h, DEC h и, таким образом, завершает демонстрацию того, как RAM может "олицетворять" RASP:

Набор команд целевой программы: {INC h; DEC h; JZ h, xxx, HALT}

Без косвенных инструкций INCi и DECi конечного автомата для выполнения программных инструкций INC и DEC конечный автомат должен использовать косвенную копию, чтобы получить содержимое указанного регистра в резервный регистр # 3, DEC или INC, а затем использовать косвенная копия, чтобы отправить ее обратно в указанный регистр.

			ПК	ИК
		отверстие # →	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
		программа, параметры →	5				JZ	18	15	DEC	18	INC	19	JZ	15	5	ЧАС			п
		закодированная программа →	5				3	18	15	2	18	1	19	3	15	5	0			п
		инструкции конечного автомата ↓

15		J fetch_instr	8	18	п		3	18	15	2	18	1	19	3	15	5	0			п
16	fetch_instr:	CPY <<1>>, <2>	8 я	[2]	п		3	18	15	2	18	1	19	3	15	5	0			п
17	разобрать:	JZ 2, остановка	8	2	п		3	18	15	2	18	1	19	3	15	5	0			п
18		2 декабря	8	[1]	п		3	18	15	2	18	1	19	3	15	5	0			п
19		JZ 2, inc_routine:	8	1	п		3	18	15	2	18	1	19	3	15	5	0			п
20		2 декабря	8	[0]	п		3	18	15	2	18	1	19	3	15	5	0			п
21 год		JZ 2, dec_routine:	8	0!	п		3	18	15	2	18	1	19	3	15	5	0			п
22	dec_routine:	INC 1	9	0	п		3	18	15	2	18	1	19	3	15	5	0			п
23		CPY <<1>>, <2>	9 я	18	п		3	18	15	2	18	1	19	3	15	5	0			п
24		CPY <<2>>, <3>	9	18 я	п		3	18	15	2	18	1	19	3	15	5	0			п
25		JZ 3, * + 2	9	18	п		3	18	15	2	18	1	19	3	15	5	0			п
26		3 ДЕКАБРЯ	9	18	п-1		3	18	15	2	18	1	19	3	15	5	0			п
27		CPY <3>, <<2>>	9	18 я	п-1		3	18	15	2	18	1	19	3	15	5	0			п-1
28 год		INC 1	10	18	п-1		3	18	15	2	18	1	19	3	15	5	0			п-1
29		J fetch_instr	10	18	п-1		3	18	15	2	18	1	19	3	15	5	0			п-1

30	fetch_instr:	CPY <<1>>, <2>	10 я	1	п-1		3	18	15	2	18	1	19	3	15	5	0			п-1
31 год	разобрать:	JZ 2, остановка	10	1	п-1		3	18	15	2	18	1	19	3	15	5	0			п-1
32		2 декабря	10	0	п-1		3	18	15	2	18	1	19	3	15	5	0			п-1
33		JZ 2, inc_routine:	10	0!	п-1		3	18	15	2	18	1	19	3	15	5	0			п-1
34	inc_routine:	INC 1	11	0	п-1		3	18	15	2	18	1	19	3	15	5	0			п-1
35 год		CPY <<1>>, <2>	11 я	19	п-1		3	18	15	2	18	1	19	3	15	5	0			п-1
36		CPY <<2>>, <3>	11	19 я	0		3	18	15	2	18	1	19	3	15	5	0			п-1	0
37		INC 3	11	19	1		3	18	15	2	18	1	19	3	15	5	0			п-1	0
38		CPY <3>, <<2>>	11	19 я	1		3	18	15	2	18	1	19	3	15	5	0			п-1	1
39		INC 1	12	19	1		3	18	15	2	18	1	19	3	15	5	0			п-1	0
40		J fetch_instr	12	19	1		3	18	15	2	18	1	19	3	15	5	0			п-1	0
41 год	fetch_instr:	и т.п.	12	19	1		3	18	15	2	18	1	19	3	15	5	0			п-1	0

Альтернативные инструкции : Хотя в результате демонстрации был получен примитивный RASP, состоящий всего из четырех инструкций, читатель может представить себе, как можно выполнить дополнительную инструкцию, такую как «ADD <h>» или «MULT <h _a >, << h _b >».

Самомодифицирующиеся программы RASP [ править ]

Когда RAM действует как RASP, было получено кое-что новое: в отличие от RAM, RASP обладает способностью к самостоятельной модификации своих программных инструкций (инструкции конечного автомата замораживаются и не могут быть изменены машиной). Кук-Реккау (1971) (стр. 75) комментирует это в своем описании своей модели RASP, как и Хартманис (1971) (стр. 239 и далее).

Раннее описание этого понятия можно найти у Голдстайна-фон Неймана (1946):

«Нам нужен порядок [инструкция], который может подставлять число в заданный порядок ... Посредством такого порядка результаты вычислений могут быть введены в инструкции, управляющие этим или другим вычислением» (стр. 93)

Такая способность делает возможным следующее:

подпрограммы - вызывающая процедура (или, возможно, подпрограмма) сохраняет адрес возврата "return_address" в последней команде подпрограммы, то есть "JMP return_address"
так называемые JUMP-столы
самомодифицирующийся код

Набор программ и инструкций RASP Кука и Рекхоу (1973) [ править ]

В влиятельной статье Стивен А. Кук и Роберт А. Рекхау определяют свою версию RASP:

«Машина с хранимыми программами произвольного доступа (RASP), описанная здесь, аналогична RASP, описанной Хартманисом [1971]» (стр. 74).

Их цель состояла в том, чтобы сравнить время выполнения различных моделей: RAM, RASP и многоленточной машины Тьюринга для использования в теории анализа сложности .

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

Их регистры RASP неограниченны по объему и неограниченному количеству; аналогично их аккумулятор AC и счетчик команд IC не ограничены. Набор инструкций следующий:

операция	мнемонический	код операции	описание
постоянная нагрузки	LOD, k	1	положить константу k в аккумулятор
добавлять	ДОБАВИТЬ, j	2	добавить содержимое регистра j в аккумулятор
вычесть	SUB, j	3	вычесть содержимое регистра j из аккумулятора
хранить	СТО, j	4	скопировать содержимое аккумулятора в регистр j
ветвь на плюсовом аккумуляторе	BPA, xxx	5	ЕСЛИ содержимое аккумулятора> 0 ТО перейти к xxx ELSE следующая инструкция
читать	RD, j	6	следующий ввод в регистр j
Распечатать	PRI, j	7	вывод содержимого регистра j
остановка	HLT	любое другое - или + целое число	останавливаться

Ссылки [ править ]

Часто машины RAM и RASP представлены вместе в одной статье. Они были скопированы с машины произвольного доступа ; за некоторыми исключениями, эти ссылки такие же, как и на машине Register .

Джордж Булос , Джон П. Берджесс , Ричард Джеффри (2002), Вычислимость и логика: четвертое издание , Cambridge University Press, Кембридж, Англия. Первоначальный текст Булоса-Джеффри был тщательно отредактирован Берджессом: он был более продвинутым, чем вводный учебник. Модель "Abacus machine" подробно описана в главе 5 " Вычислимость Abacus" ; это одна из трех моделей, которые тщательно изучаются и сравниваются - машина Тьюринга (все еще в исходной четырехкортежной форме Boolos) и две другие рекурсивные модели.
Артур Беркс , Герман Голдстайн , Джон фон Нейман (1946), Предварительное обсуждение логической конструкции электронного вычислительного инструмента , перепечатано с. 92ff в Гордоне Белле и Аллене Ньюэлле (1971), Компьютерные структуры: чтения и примеры , mcGraw-Hill Book Компания, Нью-Йорк. ISBN 0-07-004357-4 .
Стивен А. Кук и Роберт А. Рекхоу (1972), Машины с произвольным доступом с ограничением по времени , Journal of Computer Systems Science 7 (1973), 354-375.
Мартин Дэвис (1958), « Вычислимость и неразрешимость» , McGraw-Hill Book Company, Inc., Нью-Йорк.
Кальвин Элгот и Абрахам Робинсон (1964), Машины с хранимыми программами с произвольным доступом, подход к языкам программирования , Журнал Ассоциации вычислительной техники, Vol. 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, Addison-Wesley, Reading, Massachusetts. См. Страницы 462-463, где он определяет «новый вид абстрактной машины или« автомата », который имеет дело со связанными структурами».
Иоахим Ламбек (1961, получен 15 июня 1961), Как программировать бесконечные счеты , Математический бюллетень, т. 4, вып. 3. Сентябрь 1961 г., стр. 295–302. В своем Приложении II Ламбек предлагает «формальное определение« программы ». Он ссылается на Мелзака (1961) и Клини (1952)« Введение в метаматематику » .
ZA Melzak (1961, получено 15 мая 1961 г.), Неформальный арифметический подход к вычислимости и вычислениям , Canadian Mathematical Bulletin, vol. 4, вып. 3. Сентябрь 1961 г., стр. 279–293. Мелзак не дает никаких ссылок, но признает «пользу разговоров с докторами Р. Хэммингом, Д. Макилроем и В. Виссотсом из телефонных лабораторий Bell и с доктором Х. Вангом из Оксфордского университета».
Марвин Мински (1961, получен 15 августа 1960). «Рекурсивная неразрешимость проблемы Поста« тега »и других вопросов теории машин Тьюринга». Анналы математики . Анналы математики. 74 (3): 437–455. DOI : 10.2307 / 1970290 . JSTOR 1970290 . Проверить значения даты в: |date=( помощь )
Марвин Мински (1967). Вычисление: конечные и бесконечные машины (1-е изд.). Энглвуд Клиффс, Нью-Джерси: ISBN Prentice-Hall, Inc. 0-13-165449-7.В частности, см. Главу 11: Модели, подобные цифровым компьютерам, и главу 14: Очень простые основы вычислимости . В предыдущей главе он дает определение «Программные машины», а в более поздней главе он обсуждает «Универсальные программные машины с двумя регистрами» и «... с одним регистром» и т. Д.
Джон С. Шепердсон и Х. Э. Стерджис (1961) получили в декабре 1961 г. « Вычислимость рекурсивных функций» , Journal of the Association of Computing Machinery (JACM) 10: 217-255, 1963. Чрезвычайно ценный справочный документ. В своем Приложении А авторы цитируют еще 4 со ссылкой на «Минимум инструкций, используемых в 4.1: Сравнение с аналогичными системами».

Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine ' , Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik: 5 (1959), 366-379.
Ершов А.П. Об операторных алгоритмах // Докл. Акад. АН СССР, 122 (1958), 967-970. Английский перевод, Автомат. Экспресс 1 (1959), 20-23.
Петер, Rózsa Graphschemata und rekursive Funktionen , Dialectica 12 (1958), 373.
Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semsterberichte (Göttingen) 4 (1954), 42-53.

Арнольд Шёнхаге (1980), Машины для модификации памяти , Общество промышленной и прикладной математики, SIAM J. Comput. Vol. 9, No. 3, август 1980. Здесь Шенхаге показывает эквивалентность своего SMM с «преемником RAM» (машина произвольного доступа) и т. Д., Соответственно. Машины для модификации памяти , в Теоретической информатике (1979), стр. 36–37.
Питер ван Эмде Боас , Модели машин и симуляции, стр. 3–66, опубликовано в: Ян ван Леувен , изд. "Справочник по теоретической информатике. Том A: Алгоритмы и сложность , MIT PRESS / Elsevier, 1990. ISBN 0-444-88071-2 (том A). QA 76.H279 1990.

Трактовка СММ ван Эмде Боасом приводится на стр. 32-35. Это лечение проясняет Schnhage 1980 - оно близко следует, но немного расширяет лечение Schnhage. Обе ссылки могут потребоваться для эффективного понимания.

Хао Ван (1957), Вариант теории вычислительных машин Тьюринга, JACM (Журнал Ассоциации вычислительной техники) 4; 63-92. Представлено на заседании Ассоциации 23–25 июня 1954 г.