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

Структура

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

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

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

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

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

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

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

См. также

• Машина Тьюринга
• Гарвардская архитектура

Литература

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

Ссылки

• (неопр.) . www.introligator.org. Дата обращения: 11 февраля 2018. 12 февраля 2018 года.
• (недоступная ссылка)
• от 7 августа 2016 на Wayback Machine