Машина с произвольным доступом - Википедия - Random-access machine

В Информатика, машина с произвольным доступом (баран) является абстрактная машина в общем классе зарегистрировать машины. Оперативная память очень похожа на счетчик машина но с добавленной возможностью «косвенной адресации» своих регистров. Как и машина счетчика, RAM имеет свои инструкции в конечной части машины (так называемая Гарвардская архитектура ).

Эквивалент RAM универсальная машина Тьюринга - с этими программа в регистрах, а также в его данных - называется машина с произвольным доступом к хранимым программам или РАСП. Это пример так называемого фон Неймана архитектура и наиболее близок к общепринятому понятию компьютер.

Вместе с Машина Тьюринга и модели встречных машин, модели RAM и RASP используются для анализ вычислительной сложности. Ван Эмде Боас (1990) называет эти три плюс указатель машины модели "последовательной машины", чтобы отличить их от "параллельная машина с произвольным доступом "модели.

Введение в модель

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

Формальное определение

А машина с произвольным доступом (RAM) - это абстрактная модель вычислительной машины, идентичная многорегистровой счетчик машина с добавлением косвенной адресации. По усмотрению инструкции своего конечный автомат ТАБЛИЦА, машина получает адрес "целевого" регистра либо (i) непосредственно из самой инструкции, либо (ii) косвенно из содержание (например, номер, метка) регистра «указатель», указанного в инструкции.

По определению: A регистр это место с адрес (уникальное, различимое обозначение / указатель, эквивалентное натуральному числу) и содержание - единственное натуральное число. Для точности мы будем использовать квазиформальный символизм из Boolos-Burgess-Jeffrey (2002), чтобы указать регистр, его содержимое и операцию над регистром:

[r] означает «содержимое регистра с адресом r». Метка «r» здесь - это «переменная», которая может быть заполнена натуральным числом, буквой (например, «A») или именем.
→ означает «копировать / депонировать в» или «заменять», но без уничтожения источника

Пример: [3] +1 → 3; означает: «Содержимое исходного регистра с адресом« 3 »плюс 1 помещается в регистр назначения с адресом« 3 »(здесь источник и место назначения совпадают). Если [3] = 37, то есть содержимое регистр 3 - это число "37", тогда 37 + 1 = 38 будет помещено в регистр 3.

Пример: [3] → 5; означает "Содержимое исходного регистра с адресом" 3 "помещается в регистр назначения с адресом" 5 ". Если [3] = 38, то есть содержимое регистра 3 является числом 38, то это число будет помещено в регистр 5. Эта операция не влияет на содержимое регистра 3, поэтому [3] по-прежнему имеет значение 38, то же самое, что и [5].

Определение: A непосредственный инструкция - это та, которая определяет в самой инструкции адрес исходного или целевого регистра, содержимое которого будет предметом инструкции. косвенное указание - это тот, который определяет «регистр указателя», содержимое которого является адресом «целевого» регистра. Целевой регистр может быть либо источником, либо местом назначения (различные инструкции COPY предоставляют примеры этого). Регистр может обращаться к себе косвенно.

Из-за отсутствия стандарта / соглашения в этой статье в качестве параметра (или параметров) в инструкции будет указано «прямой / косвенный», сокращенно «d / i»:

Пример: КОПИРОВАТЬ ( d, А, я, N) означает прямо d получить адрес исходного регистра (регистр "A") из самой инструкции, но косвенно я получить адрес назначения из регистра-указателя N. Предположим, [N] = 3, тогда регистр 3 является адресатом, и инструкция будет делать следующее: [A] → 3.

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

Определение: содержание регистр указателя это адрес "целевого" реестра.

Определение: содержание регистр указателя указывает на целевой регистр - «цель» может быть регистром источника или получателя.

Определение: регистр назначения это место, куда инструкция помещает свой результат. Адрес исходного регистра может быть указан либо (i) непосредственно инструкцией, либо (ii) косвенно регистром указателя, заданным инструкцией. Регистры источника и назначения могут быть одним

Напоминание: модель встречной машины

Мелзак (1961) дает простую визуализацию счетчика: его «регистры» - это отверстия в земле, и эти отверстия удерживают гальку. Согласно инструкции, в эти отверстия и из них «компьютер» (человек или машина) добавляет (INCrements) или удаляет (DECrements) один камешек. По мере необходимости из бесконечного запаса берутся дополнительные камешки, а излишки гальки возвращаются обратно; если яма слишком мала для размещения гальки, «компьютер» выкапывает яму побольше.

Мински (1961) и Хопкрофт-Ульман, 1979 (стр. 171) предлагают визуализацию многоленты. Машина Тьюринга с таким же количеством лент с левым концом, как "регистры". Длина каждой ленты не ограничена справа, и каждый квадрат пустой, за исключением левого конца, который отмечен. В расстояние "головы" ленты от ее левого конца, измеренное в количестве квадратов ленты, представляет собой натуральное число в "регистре". Для определения количества квадратов головка ленты перемещается влево; INCrement он движется вправо. Нет необходимости печатать или стирать метки на ленте; единственные условные инструкции - это проверить, находится ли голова на левом конце, проверяя метку на левом конце с помощью инструкции «Перейти, если отмечена».

Следующая инструкция "мнемоника" например «CLR (r)» произвольны; стандарта не существует.

В зарегистрировать машину имеет для памяти, внешней по отношению к его конечному автомату, - неограниченный (см. сноску | счетное и неограниченное) набор дискретных и однозначно помеченных ячеек с неограниченный емкость, называемая «регистрами». Эти регистры содержат только натуральные числа (ноль и положительные целые числа). В соответствии со списком последовательных инструкций в ТАБЛИЦЕ конечного автомата несколько (например, 2) типов примитивных операций работают с содержимым этих «регистров». Наконец, условное выражение в виде ЕСЛИ-ТО-ЕЩЕ доступен для проверки содержимого одного или двух регистров и "перехода / перехода" конечного автомата из последовательности инструкций по умолчанию.

Базовая модель 1: Модель, наиболее близкая к визуализации Мински (1961) и Ламбеку (1961):

{INCrement содержимое регистра r, DECrement содержимое регистра r, ЕСЛИ содержимое регистра r равно нулю ТОГДА Перейти к инструкции I_z ЕЩЕ перейти к следующей инструкции}:

Инструкция	Мнемонический	Действие в регистре (ах) "r"	Действие в регистре инструкций конечного автомата, IR
INCrement	INC (r)	[г] + 1 → г	[ИК] + 1 → ИК
ДЕКРЕМЕНТ	DEC (r)	[r] - 1 → r	[ИК] + 1 → ИК
Перейти, если ноль	JZ (г, г)	никто	ЕСЛИ [r] = 0, ТО z → IR ELSE [IR] + 1 → IR
Остановка	ЧАС	никто	[ИК] → ИК

Базовая модель 2: Модель "преемник" (названная в честь функции-преемника Аксиомы Пеано ):

{Увеличьте содержимое регистра r, УБЕДИТЕ содержимое регистра r, ЕСЛИ содержимое регистра r_j Равно содержимому регистра r_k ТОГДА Перейти к инструкции I_z ЕЩЕ перейти к следующей инструкции}

Инструкция	Мнемонический	Действие в регистре (ах) "r"	Действие в регистре инструкций конечного автомата, IR
Чисто	CLR (r)	0 → г	[ИК] + 1 → ИК
INCrement	INC (r)	[г] + 1 → г	[ИК] + 1 → ИК
Перейти, если равно	JE (r1, r2, z)	никто	ЕСЛИ [r1] = [r2] ТО z → IR ELSE [IR] + 1 → IR
Остановка	ЧАС	никто	[ИК] → ИК

Базовая модель 3: Используется Элгот-Робинсоном (1964) в их исследовании ограниченных и неограниченных RASP - модели «преемника» с COPY вместо CLEAR:

{Увеличьте содержимое регистра r, КОПИРУЙТЕ содержимое регистра r_j зарегистрировать г_k, ЕСЛИ содержимое регистра r_j Равно содержимому регистра r_k тогда Перейти к инструкции I_z ЕЩЕ перейти к следующей инструкции}

Инструкция	Мнемонический	Действие в регистре (ах) "r"	Действие в регистре инструкций конечного автомата, IR
КОПИРОВАТЬ	КОПИРОВАТЬ (r1, r2)	[r1] → r2	[ИК] + 1 → ИК
INCrement	INC (r)	[г] + 1 → г	[ИК] + 1 → ИК
Перейти, если равно	JE (r1, r2, z)	никто	ЕСЛИ [r1] = [r2] ТО z → IR ELSE [IR] + 1 → IR
Остановка	ЧАС	никто	[ИК] → ИК

Создание "удобных инструкций" из базовых наборов

Три базовых набора 1, 2 или 3, указанные выше, эквивалентны в том смысле, что можно создавать инструкции одного набора, используя инструкции другого набора (интересное упражнение: подсказка Мински (1967) - объявить зарезервированный регистр, например, вызов это «0» (или Z для «нуля» или E для «стирания»), чтобы содержать число 0). Выбор модели будет зависеть от того, какую из них автору проще всего использовать в демонстрации или доказательстве и т. Д.

Более того, из базовых наборов 1, 2 или 3 мы можем создать любой из примитивные рекурсивные функции (см. Мински (1967), Булос-Берджесс-Джеффри (2002)). (Как забросить сеть шире, чтобы общий и частичный рекурсивные функции mu будет обсуждаться в контексте косвенной адресации). Однако создание примитивных рекурсивных функций сложно, потому что наборы инструкций настолько ... примитивны (крошечные). Одно из решений - расширить конкретный набор «удобными инструкциями» из другого набора:

Это не будут подпрограммы в обычном смысле, а скорее блоки инструкций, созданных из базового набора и снабженных мнемоникой. В формальном смысле, чтобы использовать эти блоки, нам нужно либо (i) «расширить» их до эквивалентов базовых инструкций - они потребуют использования временных или «вспомогательных» регистров, поэтому модель должна это учитывать, либо ( ii) проектировать наши машины / модели с «встроенными» инструкциями.

Пример: Базовый набор 1. Для создания CLR (r) используйте блок инструкций для обратного отсчета регистра r до нуля. Обратите внимание на использование упомянутой выше подсказки:

CLR (г) =_{эквивалент}
петля: JZ (r, выход)

DEC (r)
JZ (0, петля)

выход: так далее.

Опять же, все это только для удобства; ничто из этого не увеличивает внутреннюю мощность модели.

Например: наиболее развернутый набор будет включать каждую уникальную инструкцию из трех наборов плюс безусловный переход J (z), то есть:

{CLR (r), DEC (r), INC (r), CPY (r)_s, р_d ), JZ (r, z), JE (r_j, р_k, z), J (z)}

Большинство авторов выбирают тот или иной условный переход, например Шепердсон-Стерджис (1963) используют вышеуказанный набор минус JE (для большей точности они используют JNZ - Перейти, если Нет Ноль вместо JZ; еще одна возможная инструкция по удобству).

«Непрямая» операция

Пример косвенной адресации

В нашей повседневной жизни понятие «косвенная операция» не является чем-то необычным.

Пример: поиск сокровищ.

В локации "Tom _ & _ Becky's_cave_in_pirate_chest" мы можем найти карту, ведущую нас к "сокровищам":

(1) Идем в локацию «Пещера Тома _ & _ Бекки ...» и копаемся, пока не находим деревянный ящик.

(2) Внутри коробки находится карта расположения клада: "under_Thatcher's_front_porch"

(3) Мы идем в локацию «under_Thatcher's_front_porch», удаляем отбойным молотком бетон и обнаруживаем «сокровище»: мешок ржавых дверных ручек.

Косвенное обращение указывает местоположение, идентифицированное как пиратский сундук в "Tom _ & _ Becky's_cave ...", которое действует как указатель в любое другое место (включая себя): его содержимое (карта сокровищ) предоставляет "адрес" цель локация "under_Thatcher's_front_porch", где происходит настоящее действие.

Зачем нужна непрямая операция: две основные проблемы с моделью встречной машины

Далее следует помнить, что эти модели являются абстрактными моделями, имеющими два фундаментальных отличия от всего физически реального: неограниченное количество регистров, каждая из которых имеет неограниченную емкость. Проблема проявляется наиболее резко, когда кто-то пытается использовать модель контрмашины для построения RASP, которая Эквивалент Тьюринга и таким образом вычислить любой частичный рекурсивная функция mu:

Мелзак (1961) добавил косвенное обращение к своей модели «дырка и галька», чтобы его модель могла модифицироваться с помощью «вычисляемого goto», и предоставляет два примера его использования («Десятичное представление в масштабе d» и «Сортировка по величина », неясно, используются ли они в его доказательстве эквивалентности модели по Тьюрингу, поскольку« сама программа предоставляется читателю в качестве упражнения »(стр. 292)). Мински (1961, 1967) смог продемонстрировать, что с помощью подходящих (но трудных в использовании) Число Гёделя кодирования, регистровая модель не нуждалась в косвенном обращении, чтобы быть эквивалентом Тьюринга; но для этого нужен был хотя бы один неограниченный регистр. Как указано ниже, Мински (1967) намекает на проблему RASP, но не предлагает решения. Элгот и Робинсон (1964) доказали, что их модель RASP P₀ - у него нет возможности косвенного обращения - он не может вычислять все «рекурсивные последовательные функции» (те, которые имеют параметры произвольной длины), если у него нет возможности изменять свои собственные инструкции, но он может с помощью чисел Гёделя, если он есть (стр. 395 -397; в частности, рисунок 2 и сноска стр. 395). С другой стороны, их модель RASP P '₀ оснащенный «индексным регистром» (косвенная адресация), может вычислять все «частично рекурсивные последовательные функции» (рекурсивные функции mu) (стр. 397-398).

Кук и Рекхоу (1973) говорят об этом очень кратко:

Косвенные инструкции необходимы для того, чтобы фиксированная программа могла получить доступ к неограниченному количеству регистров при изменении входных данных »(стр. 73).

Неограниченный возможности регистров по сравнению с ограниченной емкостью инструкций конечного автомата: Так называемой конечный часть состояния машины должна быть - по нормальному определению алгоритма - очень конечны как по количеству «состояний» (инструкций), так и по размерам инструкций (их способности удерживать символы / знаки). Итак, как конечный автомат перемещает произвольно большую константу непосредственно в регистр, например MOVE (k, r) (переместить константу k в регистр r)? Если необходимы огромные константы, они должны либо начинаться с самих регистров, либо создаваться конечным автоматом с использованием конечного числа инструкций, например. умножайте и складывайте подпрограммы, используя INC и DEC (но не их квазибесконечное количество!).

Иногда константа k будет создана с использованием CLR (r), за которым следует INC (r), повторенная k раз - например, поместить константу k = 3 в регистр r, то есть 3 → r, поэтому в конце инструкции [r] = 3: CLR (r), INC (r), INC (r), INC (r). Этот трюк упоминается Клини (1952) с. 223. Проблема возникает, когда число, которое нужно создать, исчерпывает количество инструкций, доступных для конечный Государственный аппарат; всегда есть константа больше, чем количество инструкций, доступных для конечный Государственный аппарат.

Неограниченный числа регистров по сравнению с ограниченными командами конечного автомата: Это более серьезная проблема, чем первая. В частности, эта проблема возникает, когда мы пытаемся построить так называемую RASP, «универсальную машину» (подробнее см. Универсальная машина Тьюринга ), который использует свой конечный автомат для интерпретации «программы инструкций», хранящейся в его регистрах, то есть мы строим то, что в настоящее время называется компьютер с фон Неймана архитектура.

Обратите внимание, что конечный автомат счетчика должен вызывать регистр явно (непосредственно) по имени / номеру: INC (65,356) вызывает регистрационный номер «65,365» явно. Если количество регистров превышает возможности конечный конечный автомат для их адресации, то регистры за пределами границ будут недоступны. Например, если конечный автомат может достичь только 65 536 = 2¹⁶ Регистры то как может до 65 537-го?

Так как делать адресуем регистр за пределами конечного автомата? Один из подходов - изменить программа-инструкции (хранящиеся в регистрах), чтобы они содержали более одной команды. Но это тоже может быть исчерпано, если инструкция не имеет (потенциально) неограниченного размера. Так почему бы не использовать только одну «сверхинструкцию» - одно действительно очень большое число - которая содержит все в ней закодированы программные инструкции! Так решает проблему Минский, но Гёделевская нумерация он использует представляет собой большое неудобство для модели, и результат совсем не похож на наше интуитивное понятие «компьютер с хранимой программой».

Элгот и Робинсон (1964) приходят к аналогичному выводу в отношении RASP, который «конечно определен». Действительно, он может получить доступ к неограниченному количеству регистров (например, для получения из них инструкций), но только в том случае, если RASP разрешает «самомодификацию» своего программа инструкции, и закодировал свои «данные» в числе Гёделя (рис. 2, стр. 396).

В контексте более компьютерной модели, использующей его инструкцию RPT (повторение), Мински (1967) дразнит нас решением проблемы (см. Стр. 214, стр. 259), но не предлагает твердого решения. Он утверждает:

«В общем, операция RPT не может быть инструкцией в конечной части машины ... это может исчерпать любой конкретный объем памяти, разрешенный в конечной части компьютера [sic, его имя для его моделей RAM]. Операции RPT требуют бесконечного количества собственных регистров ». (стр.214).

Он предлагает нам ограниченный RPT, который вместе с CLR (r) и INC (r) может вычислить любые примитивная рекурсивная функция, и он предлагает неограниченный RPT, процитированный выше, который играет роль оператора μ; он вместе с CLR (r) и INC (r) может вычислять рекурсивные функции mu. Но он не обсуждает «косвенное обращение» или модель RAM как таковую.

Из ссылок в Hartmanis (1971) видно, что Кук (в своих конспектах лекций в Калифорнийском университете в Беркли, 1970) укрепил понятие косвенной адресации. Это становится более ясным в статье Кука и Рекхоу (1973) - Кук является руководителем кандидатской диссертации Рекка. Модель Хартманиса - очень похожая на модель Мелзака (1961) - использует двух- и трех регистровое сложение и вычитание и две копии параметра; Модель Кука и Рекхоу сокращает количество параметров (регистров, вызываемых в инструкциях программы) до одного вызова за счет использования аккумулятора «AC».

Решение вкратце: Разработайте нашу машину / модель с неограниченным косвенное обращение - предоставить неограниченный «адресный» регистр, который потенциально может назвать (вызвать) любой регистр, независимо от того, сколько их. Для этого, как правило, неограниченный register требует возможности очистки и последующего увеличения (и, возможно, уменьшения) с помощью потенциально бесконечного цикла. В этом смысле решение представляет собой неограниченный оператор μ который может, при необходимости, искать до бесконечности по неограниченной строке регистров, пока не найдет то, что ищет. Регистр указателя точно такой же, как и любой другой регистр, за одним исключением: в условиях, называемых «косвенной адресацией», он обеспечивает это содержимое, а не адрес-операнд в ТАБЛИЦЕ конечного автомата, чтобы быть адресом целевого регистра (включая, возможно, его самого!).

Ограниченная косвенность и примитивно-рекурсивные функции

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

Наша более простая модель контрмашины может выполнять «ограниченную» форму косвенного обращения - и тем самым вычислять подкласс примитивные рекурсивные функции - с помощью примитивного рекурсивного «оператора», называемого «определение по случаям» (определено в Kleene (1952), стр. 229 и Boolos-Burgess-Jeffrey, стр. 74). Такое «ограниченное косвенное обращение» - дело утомительное и утомительное. «Определение по случаям» требует, чтобы машина определяла / различала содержимое регистра указателя, пытаясь раз за разом до успеха сопоставить это содержимое с числом / именем, которое оператор case явно заявляет. Таким образом, определение по случаям начинается, например, с адрес нижней границы и продолжает до тошноты к адресу верхней границы, пытаясь найти соответствие:

Число в регистре N равно 0? Если нет, то равно ли оно 1? 2? 3? ... 65364? Если нет, то мы на последнем номере 65365, и пусть это будет тот, иначе у нас проблемы!

«Ограниченная» косвенность не позволит нам вычислять частично рекурсивные функции - для тех, которые нам нужны неограниченный косвенное обращение ака оператор μ.

Предположим, мы смогли перейти к номеру 65367, и на самом деле в этом регистре было то, что мы искали. Тогда мы могли бы успешно завершить наш расчет! Но предположим, что у 65367 нет того, что нам нужно. Как далеко мы должны идти дальше?

Быть Эквивалент Тьюринга счетчик должен либо использовать злополучный однорегистровый Minsky Число Гёделя метод, или быть дополненным возможностью исследовать концы его регистровой строки, до бесконечности, если это необходимо. (Неспособность найти что-то «где-то там» определяет, что означает сбой алгоритма; см. Kleene (1952), стр. 316ff Глава XII Частичные рекурсивные функции, в частности п. 323-325.) См. Подробнее об этом в примере ниже.

Неограниченная косвенность и частичные рекурсивные функции

За неограниченный косвенно мы требуем "аппаратного" изменения в нашей модели машины. Как только мы внесем это изменение, модель больше не будет машиной счетчика, а скорее машиной с произвольным доступом.

Теперь, когда, например, INC указан, инструкция конечного автомата должна будет указать куда адрес интересующего реестра будет от. Этот куда может быть либо (i) инструкцией конечного автомата, которая обеспечивает явная метка, или (ii) указатель-регистр чей содержание это интересующий адрес. Всякий раз, когда инструкция указывает адрес регистра, она теперь будет также необходимо указать дополнительный параметр «i / d» - «косвенный / прямой». В некотором смысле этот новый параметр «i / d» является «переключателем», который переключает в одну сторону для получения прямого адреса, как указано в инструкции, или в другую сторону для получения косвенного адреса из регистра указателя (который регистр указателя - в некоторых модели каждый регистр может быть регистром-указателем - указывается в инструкции). Этот «взаимоисключающий, но исчерпывающий выбор» является еще одним примером «определения по случаям», а арифметический эквивалент, показанный в приведенном ниже примере, получен из определения в Kleene (1952) p. 229.

Пример: CPY (косвенный_{источник}, р_{источник}, непосредственный_{пункт назначения}, р_{пункт назначения} )

Назначьте код, чтобы указать прямую адресацию как d = "0" и косвенную адресацию как i = "1". Тогда наша машина может определить адрес источника следующим образом:

я * [г_s] + (1-я) * г_s

Например, предположим, что содержимое регистра 3 равно "5" (т.е. [3] = 5), а содержимое регистра 4 равно "2" (т.е. [4] = 2):

Пример: CPY (1, 3, 0, 4) = CPY (косвенный, reg 3, прямой, reg 4)

1 * [3] + 0 * 3 = [3] = адрес регистра источника 5

0 * [4] + 1 * 4 = 4 = адрес регистра назначения 4

Пример: CPY (0, 3, 0, 4)

0 * [3] + 1 * 3 = 3 = адрес регистра источника 3

0 * [4] + 1 * 4 = 4 = адрес регистра назначения 4

Пример: CPY (0, 3, 1, 4)

0 * [3] + 1 * 3 = 3 = адрес регистра источника 3

1 * [4] + 0 * 4 = [4] = адрес регистра назначения 2

Непрямая инструкция COPY

Вероятно, самая полезная из добавленных инструкций - КОПИРОВАТЬ. Действительно, Элгот-Робинсон (1964) предлагает свои модели P₀ и P '₀ с инструкциями COPY, а Cook-Reckhow (1973) предоставляют свою модель на основе аккумулятора только с двумя косвенными инструкциями - КОПИРОВАТЬ в аккумулятор косвенно и КОПИРОВАТЬ из аккумулятора косвенно.

Множество инструкций: Поскольку любая инструкция, действующая на один регистр, может быть дополнена ее косвенным "двойным" (включая условные и безусловные переходы, см. Модель Элгот-Робинсона), включение косвенных инструкций удвоит количество инструкций с одним параметром / регистром (например, INC (d, r), INC (i, r)). Хуже того, каждые две инструкции параметра / регистра будут иметь 4 возможных варианта, например:

CPY (d, r_s, г, г_d ) = КОПИРОВАТЬ прямо из регистра источника прямо в регистр назначения

CPY (i, r_зр, г, г_d ) = КОПИРОВАТЬ в регистр назначения косвенно, используя адрес источника, который находится в регистре указателя источника r_зр.

CPY (d, r_s, я, г_дп ) = КОПИРОВАТЬ содержимое регистра источника косвенно в регистр, используя адрес назначения, который находится в регистре указателя назначения r_дп.

CPY (i, r_зр, я, г_дп ) = КОПИРОВАТЬ косвенно содержимое регистра источника с адресом, который должен быть найден в регистре указателя источника r_зр, в регистр назначения с адресом, который должен быть найден в регистре указателя назначения r_дп)

Аналогичным образом каждая трех регистровая инструкция, которая включает два исходных регистра r_s1 р_s2 и регистр назначения r_d в результате получится 8 разновидностей, например добавление:

[р_s1] + [r_s2] → r_d

даст:

ДОБАВИТЬ (d, r_s1, г, г_s2, г, г_d )
ДОБАВИТЬ (i, r_sp1, г, г_s2, г, г_d )
ДОБАВИТЬ (d, r_s1, я, г_sp2, г, г_d )
ДОБАВИТЬ (i, r_sp1, я, г_sp2, г, г_d )
ДОБАВИТЬ (d, r_s1, г, г_s2, я, г_дп )
ДОБАВИТЬ (i, r_sp1, г, г_s2, я, г_дп )
ДОБАВИТЬ (d, r_s1, я, г_sp2, я, г_дп )
ДОБАВИТЬ (i, r_sp1, я, г_sp2, я, г_дп )

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

Понятие «аккумулятор А»

Историческое соглашение посвящает регистр аккумулятору, «арифметическому органу», который буквально накапливает его номер во время последовательности арифметических операций:

«Первая часть нашего арифметического органа ... должна быть параллельным органом хранения, который может получать число и добавлять его к уже имеющемуся, который также может очищать свое содержимое и который может хранить то, что он содержит. Мы будем назвать такой орган Аккумулятор. В принципе, это довольно условно для вычислительных машин прошлого и настоящего самых разных типов, например настольные умножители, стандартные счетчики IBM, более современные релейные машины, ENIAC »(жирный шрифт в оригинале: Goldstine and von Neumann, 1946; стр. 98 в Bell and Newell, 1971).

Однако накопление происходит за счет большего количества инструкций на одну арифметическую «операцию», в частности, в отношении так называемых инструкций «чтение-изменение-запись», таких как «косвенное увеличение содержимого регистра, на которое указывает регистр r2». «A» обозначает регистр «аккумулятора» A:

Этикетка	Инструкция	А	r2	378 426 руб.	Описание
		. . .	378,426	17
INCi (r2):	CPY (i, r2, d, A)	17	378,426	17	Содержимое r2 указывает на r378 426 с содержанием «17»: скопируйте это в A
	INC (A)	18	378,426	17	Цемент содержание А
	CPY (d, A, i, r2)	18	378,426	18	Содержимое r2 указывает на r378 426: скопируйте содержимое A в r378 426

Если мы будем использовать конкретное имя для аккумулятора, например «А», мы можем подразумевать аккумулятор в инструкции, например,

INC (A) = INCA

Однако, когда мы пишем инструкции CPY без вызванного аккумулятора, инструкции неоднозначны или они должны иметь пустые параметры:

CPY (d, r2, d, A) = CPY (d, r2,,)

CPY (d, A, d, r2) = CPY (,, d, r2)

Исторически сложилось так, что эти две инструкции CPY получили разные имена; однако никакого соглашения не существует. Традиция (например, Knuth (1973) воображаемый СМЕШИВАНИЕ computer) использует два имени: LOAD и STORE. Здесь мы добавляем параметр «i / d»:

LDA (д / я, г_s ) =_def CPY (d / i, r_s, г, А)

STA (д / я, г_d ) =_def CPY (d, A, d / i, r_d )

Типичная модель на основе аккумулятора будет иметь все свои арифметические операции с двумя переменными и константы (например, ADD (A, r), SUB (A, r)) использовать (i) содержимое аккумулятора вместе с (ii) содержимым указанного регистра. . Для операций с одной переменной (например, INC (A), DEC (A) и CLR (A)) требуется только аккумулятор. Оба типа инструкций помещают результат (например, сумму, разницу, произведение, частное или остаток) в аккумулятор.

Пример: INCA = [A] +1 → A

Пример: ADDA (r_s) = [A] + [r_s] → A

Пример: MULA (r_s) = [A] * [r_s] → A

Если мы так выберем, мы можем сократить мнемонику, потому что по крайней мере один регистр источника и регистр назначения всегда являются аккумулятором A. Таким образом, мы имеем:

{LDA (i / d, r_s), STA (i / d, r_d), CLRA, INCA, DECA, ADDA (r_s), СУБА (r_s), MULA (r_s), ДИВА (r_s), так далее.)

Понятие косвенного адресного регистра "N"

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

Минималистский подход заключается в использовании самого себя (это делает Шёнхаге).

Другой подход (Шёнхаге тоже это делает) - объявить конкретный регистр «регистром косвенного адреса» и ограничить косвенное обращение относительно этого регистра (модель RAM0 Шёнхаге использует регистры A и N как для косвенных, так и для прямых инструкций). Опять же, у нашего нового регистра нет обычного имени - возможно, «N» от «iNdex», «iNdirect» или «номер адреса».

Для максимальной гибкости, как мы сделали для аккумулятора A, мы будем рассматривать N просто как еще один регистр, подлежащий увеличению, уменьшению, очистке, тестированию, прямому копированию и т. Д. Снова мы можем сократить инструкцию до одного параметра, который обеспечивает направление и косвенное обращение, например.

LDAN (i / d) = CPY (i / d, N, d, A); Накопитель LoaD через регистр iNdirection

СТАН (i / d) = CPY (d, A, i / d, N). Хранить накопитель через регистр iNdirection

Почему это такой интересный подход? Как минимум две причины:

(1) Набор команд без параметров:

Шёнхаге делает это для создания своего набора команд RAM0. См. Раздел ниже.

(2) Уменьшите ОЗУ до машины Пост-Тьюринга:

Прикидываясь минималистами, мы сокращаем все регистры, кроме аккумулятора A и косвенного регистра N, например р = {r0, r1, r2, ...} к неограниченной цепочке почтовых ящиков (очень) ограниченной емкости. Они не будут делать ничего, кроме (очень) ограниченных чисел, например. одинокий бит со значением {0, 1}. Точно так же мы уменьшаем аккумулятор до одного бита. Мы ограничиваем любую арифметику регистрами {A, N}, используем косвенные операции для извлечения содержимого регистров в аккумулятор и записи 0 или 1 из аккумулятора в регистр:

{LDA (i, N), STA (i, N), CLR (A / N), INC (A / N), DEC (N), JZ (A / N, I_z), JZ (I_z), H}

Мы продвигаемся дальше и полностью устраняем A с помощью двух «постоянных» регистров, называемых «ERASE» и «PRINT»: [ERASE] = 0, [PRINT] = 1.

{CPY (d, ERASE, i, N), CPY (d, PRINT, i, N), CLR (N), INC (N), DEC (N), JZ (i, N, I_z), JZ (I_z), H}

Переименуйте инструкции COPY и вызовите INC (N) = RIGHT, DEC (N) = LEFT, и у нас будут те же инструкции, что и у машины Пост-Тьюринга, плюс дополнительный CLRN:

{СТЕРЕТЬ, ПЕЧАТЬ, CLRN, ВПРАВО, ВЛЕВО, JZ (i, N, I_z), JZ (I_z), H}

Эквивалентность ОЗУ по Тьюрингу с косвенным обращением

В предыдущем разделе мы неформально показали, что RAM с неограниченной возможностью косвенного обращения производит Машина Пост-Тьюринга. Машина Пост-Тьюринга эквивалентна Тьюрингу, поэтому мы показали, что ОЗУ с косвенным обращением эквивалентно Тьюрингу.

Мы даем здесь немного более формальную демонстрацию. Начнем с разработки нашей модели с тремя зарезервированными регистрами «E», «P» и «N», а также неограниченным набором регистров 1, 2, ..., n справа. Регистры 1, 2, ..., n будут считаться «квадратами ленты». Регистр «N» указывает на «просканированный квадрат», который в данный момент наблюдает «голова». «Голова» может рассматриваться как находящаяся в условном переходе - обратите внимание, что она использует косвенную адресацию (см. Элгот-Робинсон, стр. 398). По мере того, как мы уменьшаем или увеличиваем «N», (кажущаяся) голова будет «перемещаться влево» или «вправо» по квадратам. Мы переместим содержимое «E» = 0 или «P» = 1 в «отсканированный квадрат», как указано N, используя косвенный CPY.

Тот факт, что наша лента имеет левый конец, представляет для нас небольшую проблему: всякий раз, когда встречается LEFT, наши инструкции должны будут проверять, является ли содержимое «N» нулем; в таком случае мы должны оставить его счетчик равным «0» (это наш выбор как дизайнеров - например, мы могли бы заставить машину / модель «запускать событие» по нашему выбору).

Набор команд 1 (расширенный): {INC (N), DEC (N), CLR (N), CPY (d, r_s, i, N), JZ (i, r, z), HALT}

В следующей таблице описываются инструкции Пост-Тьюринга с точки зрения их эквивалентных инструкций в ОЗУ, а также приводится пример их функционирования. (Кажущееся) расположение головки на ленте регистров r0-r5. . . отображается заштрихованным:

Мнемонический	метка:		E	п	N	r0	r1	r2	r3	r4	r5	и Т. Д.	Действия с реестрами	Действие в регистре инструкций конечного автомата IR

	Начните:		0	1	3				1	0

р	верно:	INC (N)	0	1	4				1	0			[N] +1 → N	[ИК] +1 → ИК

п	Распечатать:	CPY (d, P, i, N)	0	1	4				1	1			[P] = 1 → [N] = r4	[ИК] +1 → ИК

E	стереть:	CPY (d, E, i, N)	0	1	4				1	0			[E] = 0 → [N] = r4	[ИК] +1 → ИК

L	оставили:	JZ (i, N, конец)	0	1	4				1	0			никто	ЕСЛИ N = r4] = 0 ТОГДА "конец" → IR else [IR] +1 → IR
		DEC (N)	0	1	3				1	0			[N] -1 → N

J0 (остановка)	jump_if_blank:	JZ (i, N, конец)	0	1	3				1	0			никто	ЕСЛИ N = r3] = 0 ТО "конец" → IR else [IR] +1 → IR

J1 (остановка)	jump_if_mark:	JZ (i, N, остановка)	0	1	3				1	0			N = r3] → А	ЕСЛИ N = r3] = 0 ТО "конец" → IR else [IR] +1 → IR
	конец	. . . и Т. Д.	0	1	3				1	0

	остановка:	ЧАС	0	1	3				1	0			никто	[ИК] +1 → ИК

Пример: ограниченная косвенность дает машину, не эквивалентную Тьюрингу.

На протяжении всей этой демонстрации мы должны помнить, что инструкции в ТАБЛИЦЕ конечного автомата: ограниченный, т.е. конечный:

"Помимо простого бытия конечный набор правил который дает последовательность операций для решения конкретного типа проблемы, алгоритм имеет пять важных функций [Конечность, Определенность, Вход, Выход, Эффективность] »(курсив добавлен, Кнут, стр. 4-7).

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

Мы построим косвенный CPY (i, q, d, φ) с оператором CASE. Адрес целевого регистра будет определяться содержимым регистра «q»; как только оператор CASE определит, что это за номер, CPY напрямую внесет содержимое регистра с этим номером в регистр "φ". Нам понадобится дополнительный регистр, который мы назовем «y» - он служит счетчиком.

Таким образом, следующее на самом деле является конструктивной демонстрацией или доказательством того, что мы действительно можем моделировать косвенный CPY (i, q, d, φ) без изменения «аппаратного» дизайна нашей машины / модели счетчика. Однако обратите внимание, что поскольку этот косвенный CPY «ограничен» размером / экстентом конечного автомата, RASP, использующий этот косвенный CPY, может только вычислить примитивные рекурсивные функции, а не полный набор рекурсивные функции mu.

«Оператор» CASE описан в Kleene (1952) (стр. 229) и в Boolos-Burgess-Jeffrey (2002) (стр. 74); последние авторы подчеркивают его полезность. Следующее определение дано Клини, но изменено, чтобы отразить знакомую конструкцию «ЕСЛИ-ТО-ИНАЧЕ».

Оператор CASE «возвращает» натуральное число в φ в зависимости от того, какой «case» удовлетворяется, начиная с «case_0» и последовательно проходя через «case_last»; если ни один из вариантов не удовлетворен, то число, называемое "default" (также известное как "woops"), возвращается в φ (здесь Икс обозначает некоторый набор параметров, например регистр q и строку r0, ... rlast)):

Определение по случаям φ (Икс, y):

case_0: ЕСЛИ Q₀(Икс, y) истинно ТОГДА φ₀(Икс, y) Иначе
case_1: ЕСЛИ Q₁(Икс, y) истинно ТОГДА φ₁(Икс, y) ELSE
case_2 - case_next_to_last: и т. д. . . . . . . . ЕЩЕ
case_last: ЕСЛИ Q_{последний}(Икс, y) истинно ТОГДА φ_{последний}(Икс, y) Иначе
по умолчанию: do φ_дефолт(Икс, у)

Клини требуют, чтобы «предикаты» Q_п что выполнение тестирования является взаимоисключающим: «предикаты» - это функции, которые производят только {true, false} для вывода; Булос-Берджесс-Джеффри добавляет требование, чтобы дела были «исчерпывающими».

Мы начинаем с числа в регистре q, которое представляет адрес целевого регистра. Но что это за число? «Предикаты» будут проверять это, чтобы выяснить, одно испытание за другим: JE (q, y, z), за которым следует INC (y). Как только номер определен явно, оператор CASE прямо / явно копирует содержимое этого регистра в φ:

Определение по случаям CPY (i, q, d, φ) =_def φ (q, r0, ..., rlast, y) =

case_0: ЕСЛИ CLR (y), [q] - [y] = 0, ТО CPY (r0, φ), J (выход) ELSE
case_1: IF INC (y), [q] = [y] = 1 THEN CPY (r1, φ), J (exit) ИНАЧЕ
от case_2 до case n: IF. . . ТОГДА . . . ЕЩЕ
case_n: IF INC (y), [q] = [y] = n THEN CPY (rn, φ), J (выход) ИНАЧЕ
case_n + 1 до case_last: IF. . . ТОГДА . . . ЕЩЕ
case_last: IF INC (y), [q] = [y] = "last" THEN CPY (rlast, φ), J (выход) ELSE
по умолчанию: woops

Case_0 (базовый шаг рекурсии по y) выглядит так:

case_0:

CLR (y); установить регистр y = 0
JE (q, y, _φ0 )
J ( Случай 1 )

_φ0: CPY (r0, φ)
J ( выход )

Случай 1: и Т. Д.

Case_n (шаг индукции) выглядит так; помните, что каждый экземпляр «n», «n + 1», ..., «last» должен быть явным натуральным числом:

case_n:

INC (г)
JE (q, y, _φn )
J ( case_n + 1)

_φn: CPY (rn, φ)
J ( выход )

case__n + 1: и Т. Д.

Case_last останавливает индукцию и ограничивает оператор CASE (и тем самым ограничивает оператор «косвенного копирования»):

case_last:

INC (г)
JE (q, y, _φlast )
J ( шепчет )

_φlast: CPY (rlast, φ)
J ( выход )

woops: как нам справиться с попыткой выхода в аут?
выход: и Т. Д.

Если бы CASE можно было продолжать до бесконечности, это было бы оператор mu. Но не может - "регистр состояний" его конечного автомата достиг максимального числа (например, 65365 = 11111111,11111111₂ ) или в его таблице закончились инструкции; это конечный машина, в конце концов.

Примеры моделей

Модель "регистр-регистр" ("чтение-изменение-запись") Кука и Рекхоу (1973)

Часто встречающаяся модель Кука и Речкова немного похожа на модель Мальзека с троичными регистрами (написанная с использованием мнемоники Кнута - исходные инструкции не имели мнемоник, кроме TRA, Read, Print).

НАГРУЗКА (C, r_d ); С → г_d, C - любое целое число

Пример: ЗАГРУЗИТЬ (0, 5) очистит регистр 5.

ДОБАВИТЬ (r_s1, р_s2, р_d ); [р_s1] + [r_s2] → r_d, регистры могут быть одинаковыми или разными;

Пример: ДОБАВИТЬ (A, A, A) удвоит содержимое регистра A.

SUB (r_s1, р_s2, р_d ); [р_s1] - [р_s2] → r_d, регистры могут быть одинаковыми или разными:

Пример: SUB (3, 3, 3) очистит регистр 3.

КОПИЯ (i, r_п, г, г_d ); [[р_п]] → r_d, Косвенно скопируйте содержимое регистра-источника, на которое указывает регистр-указатель r_п в регистр назначения.
КОПИЯ (d, r_s, я, г_п ); [р_s] → [r_п]. Скопируйте содержимое регистра источника r_s в регистр-адресат, на который указывает регистр-указатель r_п.
JNZ (г, я_z ) ; Условный переход, если [r] положительно; то есть ЕСЛИ [r]> 0 ТО перейти к инструкции z, иначе продолжить в последовательности (Кук и Рекхоу называют это: «Перенести управление на строку m, если Xj> 0»)
ПРОЧИТАТЬ (r_d ) ; скопировать "вход" в регистр назначения r_d
ПЕЧАТЬ (r_s ) ; скопировать содержимое исходного регистра r_s к «выходу».

RAM0 и RAM1 Шёнхаге (1980)

Шёнхаге (1980) описывает очень примитивную, атомизированную модель, выбранную им для доказательства эквивалентности его SMM. указатель машины модель:

"Чтобы избежать какой-либо явной адресации, RAM0 имеет аккумулятор с содержимым z и дополнительный адресный регистр с текущим содержимым п (изначально 0) »(стр. 494)

RAM1 модель: Schönhage демонстрирует, как его конструкция может быть использована для формирования более общей, удобной формы "преемника" -подобной RAM (используя мнемонику этой статьи):

LDA k; к -> А , k - постоянная, явное число, например "47"
LDA (d, r); [r] → A; напрямую загрузить A
LDA (i, r); [[r]] → A; косвенно нагрузка A
STA (d, r); [A] → r; напрямую хранить A
STA (i, r); [A] → [r]; косвенно хранить A
JEA (r, z); ЕСЛИ [A] = [r], то я_z иначе продолжить
INCA; [A] + 1 -> A

RAM0 модель: Машина RAM0 Шёнхаге имеет 6 инструкций, обозначенных одной буквой (шестой «C xxx», кажется, подразумевает «пропустить следующий параметр». Шёнхаге обозначил аккумулятор буквой «z», «N» - «n» и т. Д.). Мнемоника Шёнхаге мы будем использовать развитую выше мнемонику.

(Z), CLRA: 0 → A
(A), INCA: [A] +1 → A
(N), CPYAN: [A] → N
(A), LDAA: [[A]] → A ; содержимое A указывает на адрес регистрации; поместить содержимое реестра в A
(S), СТАН: [A] → [N] ; содержимое N точек на адрес регистра; поместить содержимое A в регистр, на который указывает N
(C), JAZ (z): [A] = 0, затем перейти к I_z; неоднозначно в его обращении

Косвенное обращение происходит (i) из CPYAN (копирование / передача содержимого A в N), работающего с store_A_via_N STAN, и из (ii) специфической инструкции косвенного обращения LDAA ([[A]] → [A]).

Сноски

Конечное против неограниченного

Определяющий факт, что любой вид счетной машины без неограниченного регистра-"адресного" регистра должен указывать регистр "r" по имени, указывает на то, что модель требует, чтобы "r" было конечный, хотя он «неограничен» в том смысле, что модель не подразумевает верхнего предела количества регистров, необходимых для выполнения своей работы (й). Например, нам не требуется ни r <83,617,563,821,029,283,746, ни r <2 ^ 1,000,001 и т. Д.

Таким образом, наша модель может «расширить» количество регистров, если это необходимо для выполнения определенного вычисления. Однако это делает означают, что любое число, до которого расширяется модель, должно быть конечный - он должен индексироваться натуральным числом: ω не вариант.

Мы можем обойти это ограничение, предоставив неограниченный регистр для предоставления адреса регистра, который указывает косвенный адрес.