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

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

Уточним определение операнда и значения операнда. Операнд р — это пара (М), ^гД^е i ~ целое число, a t € {=, Л, *}. Значение v (u) операнда определяется так: г>(=, г) = г, г?(А, г) = г (г), г?(*, г) = г (г (г)). В последнем случае значение не определено при г (г) < 0.

Команда — это отображение на множестве состояний. При описании команд мы будем использовать следующие соглашения: состояние перед началом выполнения команды обозначается (гг, х, г, у), после выполнения — гг', х, г', у', если не указано, как изменяется элемент состояния, то он сохраняет прежнее значение. Входная лента не изменяется никогда.

Опишем вначале команды-операции. Для всех этих команд п' = п + 1.

Команда store и записывает г (0) в ячейку с номером н (н), т. е. r'(v (u)) = г (0).

Команда load и записывает в нулевую ячейку содержимое ячейки с номером v{u)> т. е. г'(0) = г (г?(п)).

Команды add и (сложение), sub и (вычитание), mul и (умножение), div и (целочисленное деление) выполняют арифметические действия с первой ячейкой памяти. Точные правила изменения состояния для этих команд такие: для add и: г'(0) = r (0) + v (u), для sub и: г'(0) = 7'(0) — v (u), для mul и: r'(0) = r (0) — v (u), для div и: г'(0) = [r (0)/n (n)J.

Команда read и читает в нулевую ячейку число из входной ленты: г'(0) = x (v (u)).

Команда write и пишет содержимое нулевой ячейки на выходную ленту: y'{v (u)) = г (0).

Теперь опишем команды-переходы. Они меняют только счётчик команд п. Для команды goto и: п' = v (u); для команды if zero и: если г (0) = 0, то п' = v{u), иначе п! = = п + 1; для команды ifpos и: если г (0) > 0, то п' = v (u), иначе n' = п + 1.

Определение 4.43. RAM — это конечная последовательность команд ci,…, Сщ описанного выше вида.

Из определения ясно, что множество RAM счётно.

Работа RAM М — это последовательность состояний с₀, ci, С2, … Начальное состояние со = (по, я, г,у) удовлетворяет следующим условиям: по = 1, г (к) = у (к) = 0 для всех к. Состояние с*+1 получается из состояния Ck = = {rik, x, r, y) применением команды щ к состоянию с^. Как уже говорилось выше, в некоторых случаях исполнение команды приводит к остановке. Таких случаев три: (1) после применения команды п! < 1 или п! > га; (2) значение операнда не определено; (3) невозможно выполнить операцию деления (для команды div и значение v (u) = 0). В таком случае работа RAM конечна.

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

Например, определим класс функций вида Zⁿ —> Z, вычислимых на RAM, полагая входом конечную последовательность чисел хо, • • •, х_п—, а результатом (в случае конечной работы RAM) значение у (0) первой ячейки выходной ленты. При этом о начальном состоянии делается дополнительное предположение, что х (к) = 0 при к ^ п.

Более общее определение состоит в следующем. Входом для RAM объявляется конечная последовательность положительных чисел оь…, а_п, о начальном состоянии делается предположение, что х (к) = а* при к ^ п и х (к) = 0 при к > п. Результатом работы считается начальная последовательность значений на выходной ленте до первого неположительного числа.