Random Access Machine — различия между версиями

Текущая версия на 16:47, 23 октября 2008

Определение

Random Access Machine («машины со произвольным доступом») — теоретическая модель вычислителя (см. например машина Тьюринга), напоминающая современный компьютер, программируемый непосредственно в терминах инструкций процессора (или на языке Assembler) (в теории сложности вычислений под машинами традиционно понимают single-purpose machines), т. е. машины, созданные для решения какой-либо одной фиксированной задачи, а в терминах программиста это скорее программы).

RAM-машина состоит из (См. Рисунок):

• Конечная входная read-only лента, куда записываются входные данные.
• Полубесконечная выходная write-only лента, куда записываются результат работы машины.
• Бесконечное число регистров , каждый из которых может хранить целое число, причем регистр является выделенным, и называется «сумматором» — этот регистр используется при арифметических операциях как накопитель, т. е. как второй операнд и место хранения результата.
• Программа, состоящая из конечного числа инструкций, каждая из которых содержит адрес и команду с операндом. Таблица со списком команд приведена ниже.

Важный, характеристический момент — в качестве операнда можно использовать как произвольный регистр, так и регистр, номер которого храниться в другом регистре — так называемая косвенная адресация.

• Регистр-счетчик «PC», указывающий на текущую команду.

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

Иллюстрация

Список команд