RAM-машина

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

Структура

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

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

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

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

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

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

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

См. также

Литература

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.