Random Access Machine
Определение
Random Access Machine («машины со произвольным доступом») — теоретическая модель вычислителя (см. например машина Тьюринга), напоминающая современный компьютер, программируемый непосредственно в терминах инструкций процессора (или на языке Assembler) (в теории сложности вычислений под машинами традиционно понимают single-purpose machines), т. е. машины, созданные для решения какой-либо одной фиксированной задачи, а в терминах программиста это скорее программы).
RAM-машина состоит из (См. Рисунок):
- Конечная входная read-only лента, куда записываются входные данные.
- Полубесконечная выходная write-only лента, куда записываются результат работы машины.
- Бесконечное число регистров , каждый из которых может хранить целое число, причем регистр является выделенным, и называется «сумматором» — этот регистр используется при арифметических операциях как накопитель, т. е. как второй операнд и место хранения результата.
- Программа, состоящая из конечного числа инструкций, каждая из которых содержит адрес и команду с операндом. Таблица со списком команд приведена ниже.
Важный, характеристический момент — в качестве операнда можно использовать как произвольный регистр, так и регистр, номер которого храниться в другом регистре — так называемая косвенная адресация.
- Регистр-счетчик «PC», указывающий на текущую команду.
Обратите внимание, что несмотря на «примитивный ассемблер», RAM-машины потенциально мощней любых существующих компьютеров, и физически нереализуемы — т. к. оперируют бесконечной памятью, доступ к любой ячейке-регистру которой осуществляется мгновенно, при выполнении соответствующей инструкции, и каждая ячейка этой памяти может содержать произвольное целое число (т. е. неограниченна по размеру). Но эта модель уже дает возможность вводить более-менее формальные определения времени выполнения программы, и соответственно, сложности алгоритма.
Иллюстрация
Список команд
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
Репликация: База Знаний «Заказных Информ Систем» → «Random Access Machine»