1.2. МАШИНЫ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ К ПАМЯТИ

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

РАМ состоит из входной ленты, с которой она может только считывать, выходной ленты, на которую она может только записывать, и памяти (рис. 1.3). Входная лента представляет собой последовательность клеток, каждая из которых может содержать целое число (возможно, отрицательное). Всякий раз, когда символ считывается с входной ленты, ее читающая головка сдвигается на одну клетку вправо. Выход представляет собой ленту, на которую машина может только записывать; она разбита на клетки, которые вначале все пусты. При выполнении команды записи в той клетке выходной ленты, которую в текущий момент обозревает ее головка, печатается целое число и головка затем сдвигается на одну клетку вправо. Как только выходной символ записан, его уже нельзя изменить.

Память состоит из последовательности регистров каждый из которых способен хранить произвольное целое

Рис. 1.3. Машина с произвольным доступом к памяти.

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

1) размер задачи достаточно мал, чтобы она поместилась в основную память вычислительной машины,

2) целые числа, участвующие в вычислении, достаточно малы, чтобы их можно было помещать в одну ячейку.

Программа для РАМ (или РАМ-программа) не записывается в память. Поэтому мы предполагаем, что программа не изменяет сама себя. Программа является, в сущности, последовательностью (возможно) помеченных команд. Точный тип команд, допустимых в программе, не слишком важен, пока они напоминают те, которые обычно встречаются в реальных вычислительных машинах. Мы предполагаем, что имеются арифметические команды, команды ввода-вывода, косвенная адресация (например, для индексации массивов) и команды разветвления. Все вычисления производятся в первом регистре называемом сумматором, который, как и всякий другой регистр памяти, может хранить произвольное целое число. Пример набора команд для РАМ показан на рис. 1.4. Каждая команда состоит из двух частей — кода операции и адреса.

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

Операнд может быть одного из следующих типов:

1) означает само целое число и называется литералом,

2) i - содержимое регистра должно быть неотрицательным),

3) означает косвенную адресацию, т. е. значением операнда служит содержимое регистра где целое число, находящееся в регистре если машина останавливается.

Эти команды хорошо знакомы всякому, кто программировал на языке ассемблера. Можно определить значение программы с помощью двух объектов: отображения с из множества неотрицательных целых чисел в множество целых чисел и «счетчика команд», который определяет очередную выполняемую команду. Функция с есть отображение памяти, а именно с целое число, содержащееся в регистре (содержимое регистра ).

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

Рис. 1.4. Таблица команд РАМ.

Чтобы описать действие команды, зададим значение операнда а:

Таблица на рис. 1.5 определяет действие каждой команды из таблицы на рис. 1.4. Команды, действию которых не дано определения (такие, можно считать эквивалентными команде Аналогично деление на нуль останавливает машину.

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

Вообще говоря, РАМ-программа определяет отображение из множества входных лент в множество выходных лент. Так как на некоторых входных лентах программа может не останавливаться, это отображение является частичным (т. е. для некоторых входов оно может быть не определено). Это отображение можно интерпретировать разными способами. Две важные интерпретации — интерпретация в виде функции и интерпретация в виде языка.

Предположим, что программа всегда считывает с входной ленты целых чисел и записывает на выходную ленту не более одного

Рис. 1.5. (см. скан) Действие команд РАМ. Операнд а есть или

целого числа. Пусть целые числа, находящиеся в первых клетках входной ленты, и пусть программа записывает у в первую клетку выходной ленты, а затем через некоторое время останавливается. Тогда говорят, что вычисляет функцию . Легко показать, что РАМ, как и всякая другая разумная

модель вычислительной машины, может вычислять в точности частично рекурсивные функции. Иными словами, для произвольной частично рекурсивной функции можно написать РАМ-программу, вычисляющую и для произвольной РАМ-программы можно указать эквивалентную ей частично рекурсивную функцию. (По поводу рекурсивных функций см. Дэвис [1958] или Роджерс [1967].)

Другой способ интерпретировать программу для РАМ - это посмотреть на нее с точки зрения допускаемого ею языка. Алфавит — это конечное множество символов, язык — множество цепочек (слов) алфавита. Символы алфавита можно представить целыми числами при некотором Данная РАМ допускает (воспринимает) язык в следующем смысле. Пусть на входной ленте находится цепочка причем символ расположен в первой клетке, во второй и т. д., а в клетке расположен символ, который будет использоваться в качестве концевого маркера, т. е. маркера конца входной цепочки.

Входная цепочка допускается РАМ-программой если прочитывает все ее символы и концевой маркер, пишет 1 в первой клетке выходной ленты и останавливается.

Языком, допускаемым программой называется множество всех цепочек (слов), допускаемых ею. Для входных цепочек, не принадлежащих языку, допускаемому программой она может напечатать на выходной ленте символ, отличный от 1, и остановиться, а может даже и не остановиться вообще. Легко показать, что язык

Рис. 1.6. Программа для на Упрощенном Алголе.

Рис. 1.7. (см. скан) РАМ-программа для

допускается некоторой РАМ тогда и только тогда, когда он рекурсивно перечислим. Язык допускается РАМ, останавливающейся на всех входах, тогда и только тогда, когда он рекурсивен (о рекурсивных и рекурсивно перечислимых языках см. Хопкрофт, Ульман [1969]).

Рассмотрим две программы для РАМ. Первая определяет функцию, вторая допускает язык.

Пример 1.1. Пусть

(см. скан)

Программа на Упрощенном Алголе, вычисляющая путем -кратного умножения на приведена на рис. 1.6 1). Соответствующая программа для РАМ дана на рис. 1.7. Переменные хранятся в регистрах 1, 2 и 3 соответственно. Мы специально не сделали очевидных улучшений программы, чтобы яснее было видно соответствие между рис. 1.6 и 1.7.

Пример 1.2. Рассмотрим РАМ-программу, которая допускает язык во входном алфавите состоящий из всех цепочек с одинаковым числом вхождений 1 и 2. Эта программа считывает каждый входной символ в регистр 1, а в регистре 2 оставляет разность между количеством символов 1 и 2, поступивших до текущего момента. Встретив концевой маркер 0, программа сравнивает с нулем и в случае совпадения печатает 1 и останавливается. Мы считаем О, 1 и 2 единственно возможными входными символами.

Основные детали алгоритма приведены в программе на рис. 1.8. Эквивалентная программа для РАМ дана на рис. 1.9; х хранится в регистре 1, a d - в регистре 2.