Модель RAM. 
Дискретный анализ. 
Формальные системы и алгоритмы

Использование машин Тьюринга для записи алгоритмов не слишком удобно. В этом разделе мы опишем другую модель вычислений — машины с произвольным доступом к памяти (RAM). Эта аббревиатура означает Random Access.

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

Основанный на модели RAM псевдокод часто используется для записи и анализа алгоритмов. (См. книги [1, 9].).

В отличие от машины Тьюринга, одна ячейка RAM хранит целое число. Ячейки RAM разделяются на три группы: входная лента, память, выходная лента. В каждой группе ячейки занумерованы неотрицательными целыми числами. Помимо этих ячеек RAM включает в себя программу список команд. Команды RAM имеют вид.

(наименование команды)(тип операнда)(операнд) Операнд — это целое число. Команды RAM включают в себя арифметические операции (второй операнд для арифметических операций всегда берётся из фиксированной ячейки памяти, которая имеет номер 0), операции чтения с входной ленты и записи на выходную ленту. Типов операндов три: константы, переменные и указатели, мы их будем обозначать =, Л (пустая строка), * соответственно. Значение операнда зависит от типа. Значение константы совпадает с ней самой. Значение переменной г равно числу, записанному в ячейке памяти с номером г. Значение указателя г равно числу, записанном}' в ячейке с номером, который содержится в ячейке с номером г (если в i записано отрицательное число, значение указателя не определено).

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

Работа заканчивается в одном из следующих случаев: исполнена последняя команда программы и это операция; исполнена команда перехода, но полз’ченное в результате её исполнения число не является номером команды; очередная команда не может быть исполнена (например, машина получает инструкцию разделить на 0).

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

Точные определения работы RAM, результата работы и связанные с ними понятия функции, вычислимой на RAM, и языка, распознаваемого RAM, приводятся в следующем подразделе.