Машина с произвольным доступом к хранимой программе
 | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( Ноябрь 2018 г. ) |
В теоретической информатике абстрактную машину модель машины с хранимой программой произвольного доступа (RASP) представляет собой , используемую для целей разработки алгоритмов и теории сложности алгоритмов .
RASP — это модель машины с произвольным доступом (RAM), которая, в отличие от RAM, имеет свою программу в своих «регистрах» вместе с входными данными. Регистры неограниченны (бесконечная емкость); является ли число регистров конечным, зависит от модели. Таким образом, RASP относится к оперативной памяти так же, как универсальная машина Тьюринга к машине Тьюринга . RASP является примером архитектуры фон Неймана , тогда как RAM является примером Гарвардской архитектуры .
RASP из всех абстрактных моделей ближе всего к общему понятию компьютера . Но в отличие от реальных компьютеров модель RASP обычно имеет очень простой набор инструкций, значительно сокращенный от тех, что используются в процессорах CISC и даже RISC , до простейших арифметических операций, инструкций «перемещения» между регистрами и инструкций «тестирования/перехода». Некоторые модели имеют несколько дополнительных регистров, например аккумулятор .
Вместе с регистровой машиной , ОЗУ и указателем RASP образует четыре общие модели последовательных машин , названные так, чтобы отличать их от «параллельных» моделей (например, параллельной машины произвольного доступа ) [ср. ван Эмде Боас (1990)].
Неформальное определение: модель хранимой программы с произвольным доступом RASP ( )
Краткое описание RASP:
- RASP — это универсальная машина Тьюринга (UTM), построенная на шасси RAM машины с произвольным доступом .
Читатель помнит, что UTM — это машина Тьюринга с «универсальной» таблицей инструкций с конечным числом состояний, которая может интерпретировать любую правильно сформированную «программу», записанную на ленте, как строку из пяти кортежей Тьюринга, отсюда и ее универсальность. В то время как классическая модель UTM предполагает найти на своей ленте кортежи Тьюринга из 5 кортежей, туда можно поместить любой мыслимый набор программ, при условии, что машина Тьюринга ожидает их найти — при условии, что ее таблица конечных состояний может интерпретировать их и преобразовать в желаемое действие. Вместе с программой на ленте будут напечатаны входные данные/параметры/числа (обычно справа от программы) и, в конечном итоге, выходные данные/числа (обычно справа от обоих, либо смешанные с входными данными, либо заменяющие их). ). «Пользователь» должен расположить головку машины Тьюринга над первой инструкцией, а входные данные должны быть размещены в указанном месте и формате, соответствующем как программе на ленте, так и таблице инструкций конечного автомата.
RASP имитирует эту конструкцию: он помещает «программу» и «данные» в отверстия (регистры). Но в отличие от UTM, RASP продолжает «извлекать» свои инструкции последовательно, если только условный тест не отправляет их куда-то еще.
Смущает: два набора инструкций . В отличие от UTM, модель RASP имеет два набора инструкций — таблицу инструкций конечного автомата («интерпретатор») и «программу» в дырках. Два набора не обязательно должны быть взяты из одного и того же набора.
Пример оперативной памяти, RASP как работающей
Следующий пример программы переместит содержимое регистра (отверстия) № 18 в регистр (отверстие) № 19, стирая при этом содержимое № 18.
5: 03 18 15 JZ 18,15 ; if [18] is zero, jump to 15 to end the program
02 18 DEC 18 ; Decrement [18]
01 19 INC 19 ; Increment [19]
03 15 05 JZ 15, 5 ; If [15] is zero, jump to 5 to repeat the loop (use Halt to simulate unconditional jump)
15: 00 H ; Halt
18: n ; Source value to copy
19: ; Destination for copy
Программные инструкции , доступные в этой машине RASP, будут простым набором, чтобы пример был кратким:
| Инструкция | Мнемоника | Действие над регистром «r» | Действие над регистром инструкций конечного автомата, IR |
|---|---|---|---|
| INCrement | ИНК ( р ) | [г] +1 → р | [ИС] +1 → ИС |
| DECrement | ДЕКАБРЬ ( р ) | [г] -1 → р | [ИС] +1 → ИС |
| Перейти, если ноль | JZ (р, z) | никто | ЕСЛИ [r] = 0 ТО z → IR ИНАЧЕ [IR] +1 → IR |
| Остановиться | ЧАС | никто | [ИСТ] → ЕСТЬ |
Чтобы упростить пример, мы снабдим конечный автомат RAM-as-RASP примитивными инструкциями, взятыми из того же набора, но дополненными двумя инструкциями косвенного копирования:
- Инструкции конечного автомата ОЗУ:
- { Дюйм; декабрь ч; JZ ч,ххх; CPY ⟪h а ⟫, ⟨h а ⟩ ; CPY ⟨ч а ⟩ ,⟪ч а ⟫ }
Когда конечный автомат машины RASP интерпретирует программу в регистрах, что именно будет делать конечный автомат? Столбец, содержащий восклицательный знак ! будет перечислять во временной последовательности действия конечного автомата, поскольку он «интерпретирует» — преобразует в действие — программу:
| ПК | И | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| № отверстия → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| программа, параметры → | 5 | Джей Зи | 18 | 15 | Декабрь | 18 | ИНК | 19 | Джей Зи | 15 | 5 | ЧАС | н | ||||||
| закодированная программа → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | н | ||||||
| инструкции конечного автомата ↓ | |||||||||||||||||||
| ! |
Традиция делит действия конечного автомата на две основные «фазы», называемые «Выборка» и «Выполнение» . Ниже мы увидим, что внутри этих двух основных фаз существуют «подфазы». Не существует согласованной конвенции; каждая модель потребует своего точного описания.
Фаза выборки [ править ]
Конечный автомат имеет доступ ко всем регистрам, как напрямую, так и косвенно. Таким образом, он принимает № 1 в качестве ПК «счетчика программ». Роль счетчика программ будет заключаться в том, чтобы «сохранять место» в списке программ; государственная машина имеет свой собственный государственный реестр для частного использования.
При запуске конечный автомат ожидает найти номер в ПК — первую «Программу-инструкцию» в программе (т. е. под номером 5).
(Без использования косвенных COPY задача передачи указанной программной инструкции в № 2 является немного сложной. Конечный автомат будет косвенно уменьшать указанный регистр, одновременно увеличивая (пустой) регистр № 2. Во время на этапе «анализа» он восстановит пожертвованное содержимое #5, пожертвовав счетчиком в #2.)
Цель приведенного выше обходного пути — показать, что жизнь становится намного проще, когда конечный автомат имеет доступ к двум видам косвенного копирования:
- копировать косвенно из i и напрямую в j: CPY ⟪h i ⟫, ⟨h j ⟩
- копировать прямо из i и косвенно в j: CPY ⟨h i ⟩ ,⟪h j ⟫
В следующем примере показано, что происходит на этапе «выборки» конечного автомата. Операции конечного автомата перечислены в столбце «Инструкция конечного автомата ↓». Обратите внимание, что в конце выборки регистр № 2 содержит числовое значение 3 «кода операции» («код операции») первой инструкции JZ :
| ПК | МОСТ | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| № отверстия → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| программа, параметры → | 5 | Джей Зи | 18 | 15 | Декабрь | 18 | ИНК | 19 | Джей Зи | 15 | 5 | ЧАС | н | ||||||||
| закодированная программа → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | н | ||||||||
| шаг | инструкции конечного автомата ↓ | ||||||||||||||||||||
| 1 | выборка_инстр: | 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 | Джей Зи | 18 | 15 | Декабрь | 18 | ИНК | 19 | Джей Зи | 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_рутина | 5 | 0 ! | ||||||||||||||||||
| — | остановка: | ОСТАНОВКА | 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_рутина: | и т. д. | 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) выборку второго операнда. Он просто увеличивает вдвое скорость ПК, а затем безоговорочно возвращается к фазе выборки инструкций, где извлекает программную инструкцию № 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 | Джей Зи | 18 | 15 | Декабрь | 18 | ИНК | 19 | Джей Зи | 15 | 5 | ЧАС | н | ||||||||
| закодированная программа → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | н | ||||||||
| шаг | инструкции конечного автомата ↓ | ||||||||||||||||||||
| 9 | JZ_рутина | ИНК 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 я | [н] | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | [н] | ||||
| 12 | тестовое отверстие: | JZ 3, прыжок | 6 | 18 я | [н] | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | н | ||||
| н | н | ||||||||||||||||||||
| 13 | no_jump: | ИНК 1 | [7] | 18 | н | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | н | ||||
| 14 | ИНК 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 | выборка_инстр: | CPY ⟪1⟫, ⟨2⟩ | 8 я | [2] | н | 3 | 18 | 15 | [2] | 18 | 1 | 19 | 3 | 15 | 5 | 0 | н | ||||
| 2 | разобрать: | и т. д. | |||||||||||||||||||
| 13 | прыжок: | ИНК 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 | выборка_инстр: | CPY ⟪1⟫, ⟨2⟩ | 15 я | [0] | н | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | [0] | н | ||||
| 2 | разобрать: | и т. д. |
Фаза выполнения INC, DEC [ править ]
Следующее завершает автоматную интерпретацию программных инструкций INC h, DEC h в ОЗУ и, таким образом, завершает демонстрацию того, как ОЗУ может «выдавать себя за» RASP:
- Набор инструкций целевой программы: { INC h; декабрь ч; JZ ч,ххх, СТОЛБ }
Без косвенных инструкций конечного автомата 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 | Джей Зи | 18 | 15 | Декабрь | 18 | ИНК | 19 | Джей Зи | 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 | выборка_инстр: | 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, вкл_рутина: | 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: | ИНК 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 | ДЗ 3,*+2 | 9 | 18 | н | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | н | |||||
| 26 | 3 ДЕКАБРЯ | 9 | 18 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | н | |||||
| 27 | CPY ⟨3⟩ ,⟪2⟫ | 9 | 18 я | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 28 | ИНК 1 | 10 | 18 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 29 | J fetch_instr | 10 | 18 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 30 | выборка_инстр: | CPY ⟪1⟫, ⟨2⟩ | 10 я | 1 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | ||||
| 31 | разобрать: | JZ 2, стоп | 10 | 1 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | ||||
| 32 | 2 ДЕКАБРЯ | 10 | 0 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 33 | JZ 2, Inc_Routine: | 10 | 0 ! | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 34 | inc_routine: | ИНК 1 | 11 | 0 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | ||||
| 35 | CPY ⟪1⟫, ⟨2⟩ | 11 я | 19 | n-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | |||||
| 36 | CPY ⟪2⟫, ⟨3⟩ | 11 | 19 я | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
| 37 | ИНК 3 | 11 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
| 38 | CPY ⟨3⟩ ,⟪2⟫ | 11 | 19 я | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 1 | ||||
| 39 | ИНК 1 | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
| 40 | J fetch_instr | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 | ||||
| 41 | выборка_инстр: | и т. д. | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n-1 | 0 |
Альтернативные инструкции : Хотя демонстрация привела к примитивному RASP, состоящему всего из четырех инструкций, читатель может представить, как дополнительную инструкцию, такую как «ADD ⟨h⟩ » или «MULT ⟨h a ⟩ ,⟪h b можно выполнить >.
Самомодифицирующиеся программы RASP [ править ]
Когда ОЗУ действует как RASP, было получено нечто новое: в отличие от ОЗУ, 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 не ограничены. Набор инструкций следующий:
| операция | мнемонический | код операции | описание |
|---|---|---|---|
| постоянная нагрузка | ЛОД, к | 1 | поместить константу k в аккумулятор |
| добавлять | ДОБАВИТЬ, Дж | 2 | добавить содержимое регистра j в аккумулятор |
| вычесть | СУБ,j | 3 | вычесть содержимое регистра j из аккумулятора |
| магазин | СТО, дж | 4 | скопировать содержимое аккумулятора в регистр j |
| ответвление на положительном аккумуляторе | БФА, ххх | 5 | ЕСЛИ содержимое аккумулятора > 0, ТО переход к xxx, ЛИБО следующая инструкция |
| читать | Р.Д., Дж. | 6 | следующий ввод в регистр j |
| распечатать | ПРИ, Дж | 7 | вывести содержимое регистра j |
| остановка | HLT | любое другое - или + целое число | останавливаться |
Ссылки [ править ]
Часто машины RAM и RASP представлены вместе в одной статье. Они были скопированы с машины с произвольным доступом ; за некоторыми исключениями, эти ссылки такие же, как и в Register Machine .
- Джордж Булос , Джон П. Берджесс , Ричард Джеффри (2002), Вычислимость и логика: четвертое издание , Издательство Кембриджского университета, Кембридж, Англия. Оригинальный текст Булоса-Джеффри был тщательно переработан Берджессом: он более продвинут, чем вводный учебник. Модель «счетной машины» подробно описана в главе 5 «Вычислимость счетов» ; это одна из трех моделей, которые тщательно рассматривались и сравнивались: машина Тьюринга (все еще в исходной четырехкортежной форме Булоса) и две рекурсивные модели.
- Артур Беркс , Герман Голдстайн , Джон фон Нейман (1946), Предварительное обсуждение логического проектирования электронного вычислительного прибора , перепечатано на стр. 92 и далее в книге Гордона Белла и Аллена Ньюэлла (1971), Компьютерные структуры: материалы для чтения и примеры , Книга МакГроу-Хилла Компания, Нью-Йорк. 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), «Вычислительная сложность машин с хранимыми программами произвольного доступа», 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): 437–455. дои : 10.2307/1970290 . JSTOR 1970290 .
- Марвин Мински (1967). Вычисления: конечные и бесконечные машины (1-е изд.). Prentice-Hall, Inc. Энглвуд Клиффс, Нью-Джерси: ISBN 0-13-165449-7 . В частности, см. главу 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 (том А). КА 76.H279 1990 г.
- Отношение ван Эмде Боаса к СММ представлено на стр. 32–35. Эта трактовка проясняет Шёнхаге 1980 — она близко следует, но немного расширяет трактовку Шёнхаге. Обе ссылки могут быть необходимы для эффективного понимания.
- Хао Ван (1957), Вариант теории вычислительных машин Тьюринга , JACM (Журнал Ассоциации вычислительной техники) 4; 63–92. Представлено на заседании Ассоциации 23–25 июня 1954 г.