RAM-машина

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

Структура

править

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

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

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

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

Память состоит из последовательности регистров r0, r1, ..., ri, ..., каждый из которых может хранить произвольное целое число.

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

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

См. также

править

Литература

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

Ссылки

править