Равнодоступная адресная машина

Равнодоступная адресная машина (Random access machine, RAM) — универсальная математическая модель вычислений, которая является хорошим приближением к классу обычных, традиционных вычислительных машин с точки зрения отражения затрат времени и памяти при представлении данных и алгоритмов, целиком помещающихся в оперативной памяти.

Равнодоступная адресная машина моделирует вычислительную машину с одним сумматором, в которой команды программы не могут изменять сами себя.

Равнодоступная адресная машина состоит из входной ленты, с которой она может только считывать, выходной ленты, на которую она может только записывать, и памяти.

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

Память — это последовательность подряд пронумерованных ячеек, каждая из которых способна хранить двоичную запись произвольного целого числа. Обращение к значению, хранимому в некоторой ячейке, осуществляется по адресу (номеру) этой ячейки. Ячейка с номером 0 называется сумматором. Адресация может быть не только абсолютной, когда явно указывается номер ячейки, но и косвенной. При косвенной адресации указывается адрес некоторой другой ячейки (называемой ссылкой, или указателем), содержимое которой рассматривается в качестве абсолютного адреса адресуемой ячейки.

Состояние памяти — это отображение $W$ адресов в двоичные слова, сопоставляющее с каждым адресом $n$ то слово $W(n)$, которое хранится (содержится) в ячейке с адресом $n$.

Программа — это конечная последовательность команд, занумерованных числами $1,2,3,\dots$. Счетчик команд — это переменная, принимающая значение из множества неотрицательных целых чисел.

Состояние вычисления (конфигурация) — это четверка $(x,W,k,y)$, где $x$ — непрочитанная часть входной ленты, $W$ — состояние памяти, $k$ — значение счетчика команд, а $y$ — заполненная часть входной ленты.

Выполнение равнодоступной адресной машины начинается с выполнения первой команды программы, нормально завершается выполнением команды останова и описывается протоколом выполнения — последовательностью конфигураций, в которой конфигурация $(x,W,1,e)$, где $x$ — вход, $e$ — пустая цепочка и $W(k)=0$ для любого $k$, является первой (начальной), а каждая следующая конфигурация, если она имеется, получается из текущей выполнением команды, номер которой указан в текущей конфигурации. Конфигурация, в которой счетчик команд равен нулю (ошибочная конфигурация) или номеру команды останова, может быть только последней (заключительной) конфигурацией протокола выполнения. Если выполнение равнодоступной адресной машины нормально завершается, то его результат — запись на выходной ленте, находящейся слева от печатающей головки.

Каждая команда равнодоступной адресной машины имеет имя (код операции) и операнд. Операнд может быть одного из следующих типов: "$=i$" — означает само число $i$ и называется литералом; "$i$" — содержимое ячейки $i$; "$\ast i$" — используется для косвенной адресации, т.е. значением операнда служит содержимое ячейки, адрес которой имеется в ячейке с номером $i$. Обозначая через $V(a)$ значение операнда $a$, получаем: $V(=i)=i$; $V(i)=W(i)$ и $V(\ast i)=W(W(i))$, где $W$ — текущее состояние памяти. Набор команд равнодоступной адресной машины традиционен для реальных ЭВМ и состоит из команд считывания и запоминания, арифметических и логических команд, команд перехода, команд ввода и вывода и команды останова.

Модель вычислительной машины, получившая название равнодоступной адресной машины с хранимой программой (или РАСП), отличается от равнодоступной адресной машины лишь тем, что ее программа находится в памяти и может изменять себя.

Как при равномерном, так и при логарифмическом весах команд для любой равнодоступной адресной машины (соответственно РАСП) с временной сложностью $T(n)$ существует такая постоянная $k$, что найдется эквивалентная РАСП (соответственно РАМ ), временная сложность которой не превосходит $kT(n)$.

Недетерминированная равнодоступная адресная машина (или НРАМ) получается из равнодоступной адресной машины добавлением команды ВЫБОР$(L_1,L_2,\dots ,L_r)$, означающей, что недетерминированы выбор и последующее выполнение одного из операторов $L_1,L_2,\dots ,L_r.$

Другие названия — Машина с произвольным доступом к памяти, РАМ.

См. также

• Сложность РАМ.

Литература

• Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

• Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.

• Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.