RAM-машина

Машина с произвольным доступом к памяти (Random Access Machine, сокращённо RAM-машина) — модель машины с одним сумматором, команды программы не могут изменять сами себя. Служит теоретической моделью, в частности, для анализа алгоритмов.

Структура

RAM-машина состоит из:

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

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

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

Память состоит из последовательности регистров r₀, r₁, ..., r_i, ..., каждый из которых может хранить произвольное целое число.

Программа для RAM-машины хранится не в её памяти. Поэтому предполагают, что программа не способна изменять саму себя. Программа состоит из последовательности (возможно) помеченных команд. Список команд зависит от постановки задачи, но похож на типичный язык ассемблера.

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

См. также

Литература

А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов = The Design and Analysis of Computer Algorithms. — М.: «Мир», 1979.

Ссылки

2.2. Машина с произвольным доступом к памяти (неопр.). www.introligator.org. Дата обращения: 11 февраля 2018. Архивировано 12 февраля 2018 года.
Равнодоступная адресная машина на WikiGrapp (недоступная ссылка)
Эмулятор РАМ-машины Архивная копия от 7 августа 2016 на Wayback Machine