Вычислительная машина с произвольной выборкой

Для моделирования компьютерной среды Ф. Лейтольд отталкивался от вычислительной машины с произвольной выборкой (Random Access Machine, RAM), определение которой представлено ниже.

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

• Входная лента, представляющая собой последовательность ячеек, содержащих целые числа и доступных только для последовательного чтения - после чтения ячейки считывающая головка автоматически перемещается вправо
• Выходная лента, представляющая собой последовательность ячеек, доступных только для последовательной записи, по умолчанию эти ячейки пусты
• Программа - последовательность (возможно индексированная, т.е. с возможностью указать адрес некоторых или любых инструкций) инструкций, не находящаяся в памяти и, соответственно, неизменяемая, по умолчанию выполнение программы начинается с первой инструкции (можно ввести счетчик инструкций, указывающий на следующую к выполнению инструкцию, в этом случае по умолчанию счетчик указывает на первую инструкцию)
• Память - неограниченная последовательность регистров r₀, r₁, …, r_i, …, способных хранить целые числа, по умолчанию значения регистров пусты, нулевой регистр r₀ используется для вычислений и часто называется аккумулятором, доступ к регистрам производится непосредственно по их индексам, откуда и происходит название машины.

Как следует из определения, после того как ячейка была прочитана или записана, она не может быть прочитана или записана еще раз. Неизменяемость программы означает в том числе и то, что программа не может менять себя в процессе выполнения. Фактический набор используемых в программе инструкций большого значения не имеет, поскольку вычислительная сложность алгоритма реализованного в разных (разумных) наборах инструкций асимптотически будет совпадать. Один из возможных вариантов инструкций для вычислительной машины с произвольной выборкой представлен в таблице:

Допускается три вида операндов:

• i - обозначает собственно значение целого числа i
• [i] - для неотрицательных i обозначает значение регистра r_i
• [[i]] - косвенная адресация, обозначает значение регистра r_j, где j - значение регистра r_i. Если j<0, машина завершает работу

По умолчанию (см. также определение) значение всех регистров равно нулю, счетчик инструкций указывает на первую инструкцию программы и выходная лента пуста. После выполнения k-й инструкции счетчик либо автоматически увеличивается на единицу и указывает на (k+1)-ю инструкцию, либо, если была выполнена инструкция JUMP или выполнены условия инструкций JGTZ или JZERO, принимает значение метки, либо, если была выполнена инструкция HALT, машина прекращает свою работу.