Машина с произвольным доступом

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

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

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

Содержание

• 1 Введение в модель
  • 1.1 Формальное определение
  • 1.2 Напоминание: модель счетчика
  • 1.3 Создание «удобных инструкций» из базовых наборов
• 2 «Непрямое» операция
  • 2.1 Пример косвенной адресации
  • 2.2 Зачем нужна косвенная операция: две основные проблемы с моделью счетчика
  • 2.3 Ограниченная косвенность и примитивные рекурсивные функции
  • 2.4 Неограниченная косвенная адресация и частичная рекурсивные функции
  • 2.5 Косвенная инструкция COPY
• 3 Понятие "аккумулятора A"
• 4 Понятие регистра косвенного адреса "N"
• 5 Тьюринговая эквивалентность RAM с косвенным обращением
• 6 Пример : Ограниченное косвенное обращение приводит к машине, которая не является эквивалентом Тьюринга
• 7 Примеры моделей
  • 7.1 Регистр-регистровая («чтение-изменение-запись») модель Кука и Рекхоу (1973)
  • 7.2 RAM0 Шёнхаге и RAM1 (1980)
• 8 Сноски
  • 8.1 Конечное против неограниченного
• 9 См. также
• 10 Внешние ссылки
• 11 Ссылки

Введение Переход к модели

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

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

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

По определению: регистр - это место, имеющее как адрес (уникальное, различимое обозначение / указатель, эквивалентное натуральному числу), так и содержимое - одно натуральное число. Для точности мы будем использовать квазиформальный символизм из 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].

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

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

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

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

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

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

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

Refresher: модель счетчика

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

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

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

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

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

• {Увеличить содержимое регистра r, Обозначить содержимое регистра r, ЕСЛИ содержимое регистра r равно нулю ТОГДА Перейти к инструкции I z Иначе перейти к следующей инструкции}:

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

• {INCREVE содержимое регистра r, CLeaR содержимое регистра r, IF содержимое регистра r j равно содержимому регистра r k THEN Перейти к инструкции I z ELSE перейти к следующей инструкции}

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

• {Увеличьте содержание Регистр r, КОПИРУЙТЕ содержимое регистра r j в регистр r k, ЕСЛИ содержимое регистра r j равно содержимому регистра r k затем перейти к инструкции I z ELSE перейти к следующей инструкции}

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

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

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

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

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

• CLR (r) = Equiv
• цикл: JZ (r, exit)

• DEC (r)
• JZ ( 0, цикл)

• exit: и т. Д.

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

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

• {CLR (r), DEC (r), INC (r), CPY (r s, r d), JZ (r, z), JE (r j, r k, z), J (z)}

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

«косвенная» операция

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

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

Пример: охота за сокровищами.

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

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

(2) Внутри ящика есть карта, указывающая на местонахождение сокровища: «под_фронтовым_полом Тэтчера»

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

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

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

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

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

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

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

• Неограниченная емкость регистров в сравнении с ограниченной емкостью инструкций конечного автомата : Предполагается, что так называемая конечная часть автомата - согласно нормальному определению алгоритма - очень конечна как по количеству "состояний" "(инструкции) и размеры инструкций (их способность содержать символы / знаки). Итак, как конечный автомат перемещает произвольно большую константу непосредственно в регистр, например MOVE (k, r) (перемещает константу k в регистр r) • Если необходимы огромные константы, они должны либо запускаться в самих регистрах, либо создаваться государственным механизмом. e с использованием конечного числа инструкций, например умножайте и складывайте подпрограммы, используя 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».

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

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

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

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

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

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

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

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

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

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

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

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

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

i * [r s ] + (1- i) * r 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

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

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

CPY (d, r s, d, r d) = КОПИРОВАТЬ непосредственно из исходного регистра непосредственно в регистр назначения

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

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

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

. Подобным образом каждая трех регистровая инструкция, которая включает два исходных регистра r s1rs2и a регистр назначения r d приведет к 8 разновидностям, например добавлению:

[rs1] + [r s2 ] → r d

даст:

• ADD (d, r s1, d, r s2, d, r d)
• ADD (i, r sp1, d, r s2, d, r d)
• ADD (d, r s1, i, r sp2, d, r d)
• ADD (i, r sp1, i, r sp2, d, r d)
• ADD (d, r s1, d, r s2, i, r dp)
• ADD (i, r sp1, d, r s2, i, r dp)
• ADD (d, r s1, i, r sp2, i, r dp)
• ADD (i, r sp1, i, r sp2, i, r dp)

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

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

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

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

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

Если мы придерживаемся определенного имени для аккумулятора, например "A", мы можем подразумевать аккумулятор в инструкциях, например,

INC (A) = INCA

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

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

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

Исторически сложилось так, что эти две инструкции CPY получили разные имена; однако никакого соглашения не существует. Традиция (например, воображаемый компьютер Кнута (1973) MIX ) использует два имени: LOAD и STORE. Здесь мы добавляем параметр «i / d»:

LDA (d / i, r s) = def CPY (d / i, r s, d, A)

STA (d / i, r 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, INC A, DECA, ADDA (r s), SUBA (r s), MULA (r s), DIVA (r s) и т.д.)

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

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

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

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

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

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

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

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

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

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

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

Представляя себя минималистами, мы сокращаем все регистры, кроме аккумулятора A и косвенного регистра N, например r = {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:

{ERASE, PRINT, CLRN, RIGHT, LEFT, JZ (i, N, I z), JZ (I z), H}

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

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

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

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

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

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

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

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

"Помимо простого конечного набора правил, который дает последовательность операций для решения определенного типа проблемы, алгоритм имеет пять важные особенности [Конечность, Определенность, Ввод, Вывод, Эффективность] »(курсив добавлен, Кнут, стр. 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"), возвращается в φ (здесь x обозначает некоторый набор параметров, например регистр q и строку r0,... rlast)):

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

• case_0: IF Q 0(x, y) истинно ТОГДА φ 0(x, y) ELSE
• case_1: ЕСЛИ Q 1(x, y) истинно ТОГДА φ 1(x, y) ELSE
• case_2 до case_next_to_last: и т. Д........ ИНАЧЕ
• case_last: ЕСЛИ Q last (x, y) истинно THEN φ last (x, y) ELSE
• по умолчанию: сделать φ по умолчанию (x, y)

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

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

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

• case_0: IF CLR (y), [q] - [y] = 0 THEN CPY (r0, φ), J (exit) ELSE
• case_1: IF INC (y), [q] = [y] = 1 THEN CPY (r1, φ), J (exit) ELSE
• case_2 через case n: IF... ТОГДА... ELSE
• case_n: IF INC (y), [q] = [y] = n THEN CPY (rn, φ), J (exit) ELSE
• case_n + 1 to case_last: IF... ТОГДА... Иначе
• case_last: IF INC (y), [q] = [y] = "last" THEN CPY (rlast, φ), J (exit) ELSE
• по умолчанию: woops

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

• case_0:

• CLR (y); установить регистр y = 0
• JE (q, y, _φ0)
• J (case_1)

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

• case_1: и т. Д.

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

• case_n:

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

• _φn: CPY (rn, φ)
• J (exit)

• case__n + 1: etc.

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

• case_last:

• INC (y)
• JE (q, y, _φlast)
• J (woops)

• _φlast: CPY (rlast, φ)
• J (exit)

• woops: как нам справиться с попыткой выхода за пределы игровой площадки?
• exit: и т. д.

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

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

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

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

• НАГРУЗКА (C, r d); C → r d, C - любое целое число

Пример: LOAD (0, 5)очищает регистр 5.

• ADD (r s1, r s2, r d); [r s1 ] + [r s2 ] → r d, регистры могут быть одинаковыми или разными;

Пример: ADD (A, A, A)удвоит содержимое регистра A.

• SUB (r s1, r s2, r d); [r s1 ] - [r s2 ] → r d, регистры могут быть одинаковыми или разными:

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

• КОПИРОВАТЬ (i, r p, d, r d); [[r p ]] → r d, Косвенно скопируйте содержимое регистра-источника, на которое указывает регистр-указатель r p, в регистр назначения.
• КОПИРОВАТЬ (d, r s, i, r p); [r s ] → [r p]. Скопируйте содержимое исходного регистра r s в регистр-адресат, на который указывает регистр-указатель r p.
• JNZ (r, I z);Условный переход, если [r] положительно; т.е. IF [r]>0 THEN перейти к инструкции z, иначе продолжить последовательность (Cook и Reckhow называют это: «Перенести управление на строку m, если Xj>0»)
• READ (r d);скопировать «вход» в регистр назначения r d
• PRINT (r s);скопировать содержимое исходного регистра r s в «выход».

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

Schönhage (1980) описывает очень примитивную, атомизированную модель, выбранную для его доказательства эквивалентности его SMM указательной машины модели:

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

Модель RAM1 : Шёнхаге демонстрирует, как его конструкция может использоваться для формирования более распространенной, удобной формы ОЗУ, подобной «преемнику» (используя мнемонику этой статьи):

• LDA k; k ->A, 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], то I z иначе продолжить
• INCA; [A] + 1 ->A

Модель RAM0 : машина RAM0 Шёнхаге имеет 6 инструкций, обозначенных одной буквой (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), STAN: [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 "было конечным, хотя он" неограничен "в том смысле, что модель не подразумевает верхнего предела количества регистров, необходимых для выполнения своей работы (s). Например, нам не требуется r < 83,617,563,821,029,283,746 nor r < 2^1,000,001, etc.

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

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

См. Также

• Real RAM
• Transdichotomous model

Внешние ссылки

• Эмулятор машины произвольного доступа
• Эмулятор машины произвольного доступа

Ссылки

С некоторыми за исключением, эти ссылки такие же, как и в Регистрационной машине.

• • Голдстайн, Герман Х. и фон Нейман, Джон, «Планирование и кодирование проблем для электронного вычислительного прибора», Rep. 1947, Институт перспективных исследований, Принстон. Перепечатано на стр. 92–119 в Bell, C. Gordon and Newell, Allen (1971), Computer Structures: Readings and examples, McGraw-Hill Book Company, Нью-Йорк. ISBN 0-07-004357-4 }.
• Джордж Булос, Джон П. Берджесс, Ричард Джеффри (2002), вычислимость и «Логика: четвертое издание», издательство Кембриджского университета, Кембридж, Англия. Первоначальный текст Булоса-Джеффри был тщательно отредактирован Берджессом: более продвинутый, чем вводный учебник. Модель «Abacus machine» подробно описана в главе 5 «Вычислимость Abacus»; это одна из трех моделей, которые тщательно изучаются и сравниваются - машина Тьюринга (все еще в исходной четырехкортежной форме Boolos) и две другие рекурсивные модели.
• Артур Бёркс, Герман Голдстайн, Джон фон Нейман (1946), Предварительное обсуждение логической конструкции электронного вычислительного инструмента, перепечатано с. 92ff в Гордон Белл и Аллен Ньюэлл (1971), Компьютерные структуры: материалы и примеры, Книжная компания McGraw-Hill, Нью-Йорк. ISBN 0-07-004357-4.
• Стивен А. Кук и Роберт А. Рекхоу (1973), Машины с произвольным доступом с ограничением по времени, Журнал компьютерных систем Science 7 (4): 354-375.
• Мартин Дэвис (1958), Computability Unsolvability, McGraw-Hill Book Company, Inc., Нью-Йорк.
• и Abraham Robinson (1964), Машины с хранимыми программами с произвольным доступом, подход к языкам программирования, Журнал Ассоциации вычислительной техники, Vol. 11, No. 4 (октябрь 1964 г.), стр. 365–399.
• (1971), «Вычислительная сложность машин с хранением программ с произвольным доступом», Mathematical Systems Theory 5, 3 (1971) pp. 232 –245.
• Джон Хопкрофт, Джеффри Уллман (1979). Введение в теорию автоматов, языки и вычисления, 1-е изд., Reading Mass: Addison-Wesley. ISBN 0-201-02988-X. Сложная книга, посвященная вопросам машинной интерпретации «языков», NP-полноты и т. Д.
• Стивен Клин (1952), Введение в метаматематику, издательство North-Holland Publishing Company, Амстердам, Нидерланды. ISBN 0-7204-2103-9.
• Дональд Кнут (1968), Искусство компьютерного программирования, второе издание 1973 года, Эддисон-Уэсли, Рединг, Массачусетс. См. Страницы 462-463, где он определяет «новый вид абстрактной машины или« автомата », который имеет дело со связанными структурами».
• Иоахим Ламбек (1961, получено 15 июня 1961 г.), How to Program an Infinite Abacus, Математический вестник, т. 4, вып. 3. Сентябрь 1961 г., стр. 295–302. В своем Приложении II Ламбек предлагает «формальное определение« программы ». Он ссылается на Мелзака (1961) и Клини (1952), Введение в метаматематику.
• (1961, получено 15 мая 1961 г.), неформальный арифметический подход to Computability and Computing, Canadian Mathematical Bulletin, том 4, № 3. Сентябрь 1961 г., страницы 279–293. Р. Хэмминг, Д. Макилрой и В. Виссотс из телефонных лабораторий Bell и с доктором Х. Вангом из Оксфордского университета ».
• Марвин Мински (1961, получено 15 августа 1960 г.).« Рекурсивная неразрешимость Проблема Поста «тега» и другие темы в теории машин Тьюринга ». Annals of Mathematics. The Annals of Mathematics, Vol. 74, No. 3. 74 (3): 437–455. doi : 10.2307 / 1970290. JSTOR 1970290. Проверить значения даты в: | date =()
• Марвин Мински (1967). Вычисления: конечные и бесконечные машины (1-е изд.). Englewood Cliffs, NJ: Prentice-Hall, Inc. В частности, см. глава 11: Модели, подобные цифровым компьютерам и глава 14: Очень простые основы вычислимости. В предыдущей главе он дает определение «Программные машины», а в следующей главе он обсуждает «Универсальные программные машины с двумя регистрами» и «... с одним register "и т. д.
• и (1961) получил в декабре 1961 г. Computability of Recursive Functions, Journa l of the Association of Computing Machinery (JACM) 10: 217-255, 1963. Чрезвычайно ценный справочный документ. В своем Приложении A авторы цитируют еще 4 со ссылкой на «Минимальность инструкций, используемых в 4.1: Сравнение с аналогичными системами».

• Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine ', Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik: 5 ( 1959), 366-379.
• Ершов А.П. Об операторных алгоритмах, Док. Акад. НАУК, 122 (1958), 967-970. Английский перевод, Автомат. Express 1 (1959), 20–23.
• Péter, Rózsa Graphschemata und rekursive Funktionen, Dialectica 12 (1958), 373.
• Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semsterberichte (Göttingen) 4 (1954), 42-53.

• Арнольд Шёнхаге (1980), Машины для модификации хранения, Общество промышленной и прикладной математики, SIAM J. Comput. Vol. 9, No. 3, август 1980. Здесь Шенхаге показывает эквивалентность своего SMM «преемнику RAM» (машина произвольного доступа) и т. Д. Соответственно. Машины для модификации хранилища, в Теоретической информатике (1979), стр. 36–37
• Питер ван Эмде Боас, «Модели машин и симуляции», стр. 3–66, в: Ян ван Левен, изд. Справочник по теоретической информатике. Том A: Алгоритмы и сложность, MIT PRESS / Elsevier, 1990. ISBN 0-444-88071-2 (том A). QA 76.H279 1990. Отношение ван Эмде Боаса к СММ приводится на стр. 32–35. Это лечение проясняет Schnhage 1980 - оно близко следует, но немного расширяет лечение Schnhage. Обе ссылки могут потребоваться для эффективного понимания.
• Хао Ван (1957), Вариант теории вычислительных машин Тьюринга, JACM (Журнал Ассоциации вычислительной техники) 4; 63-92. Представлено на собрании Ассоциации 23–25 июня 1954 г.