В информатике машина произвольного доступа ( RAM или RA-машина ) — это модель вычислений , описывающая абстрактную машину в общем классе регистровых машин . RA-машина очень похожа на счетную машину , но с добавленной возможностью «косвенной адресации» своих регистров. «Регистры» интуитивно эквивалентны основной памяти обычного компьютера, за исключением дополнительной способности регистров хранить натуральные числа любого размера. Как и машина-счетчик, RA-машина содержит инструкции выполнения в конечной части машины (так называемая Гарвардская архитектура ).
Эквивалент универсальной машины Тьюринга для RA-машины – с ее программой в регистрах, а также с ее данными – называется машиной с произвольным доступом к хранимой программе или RASP-машиной. Это пример так называемой архитектуры фон Неймана , наиболее близкой к общепринятому понятию компьютера .
Вместе с моделями машины Тьюринга и противомашины для анализа сложности вычислений используются модели RA-машины и RASP-машины . Ван Эмде Боас (1990) называет эти три модели вместе с указательной машиной моделями «последовательных машин», чтобы отличить их от моделей « параллельных машин с произвольным доступом ».
RA-машина состоит из:
Описание похожей концепции, но с юмором, см. в «языке программирования» Branflakes . [1]
Концепция машины с произвольным доступом (ОЗУ) начинается с самой простой модели, так называемой модели счетчиковой машины . Однако два дополнения отодвигают его от счетчика. Первый расширяет возможности машины, обеспечивая удобство косвенной адресации; второй приближает модель к более традиционному компьютеру на основе аккумулятора с добавлением одного или нескольких вспомогательных (выделенных) регистров, наиболее распространенный из которых называется «аккумулятор».
Машина с произвольным доступом (ОЗУ) — это абстрактная модель вычислительной машины, идентичная машине с многорегистровым счетчиком, с добавлением косвенной адресации. По усмотрению команды из ТАБЛИЦЫ своего конечного автомата машина получает адрес «целевого» регистра либо (i) непосредственно из самой инструкции, либо (ii) косвенно из содержимого ( например, номера, метки) « указатель», указанный в инструкции.
По определению: Регистр — это место, имеющее как адрес (уникальное, различимое обозначение/указатель, эквивалентный натуральному числу), так и содержимое — одно натуральное число. Для точности мы будем использовать квазиформальный символизм Булоса-Берджесса-Джеффри (2002), чтобы указать регистр, его содержимое и операцию над регистром:
Определение: Прямая инструкция — это инструкция, которая указывает в самой инструкции адрес регистра источника или назначения, содержимое которого будет предметом инструкции. Определение: Косвенная инструкция — это инструкция, которая определяет «регистр указателя», содержимым которого является адрес «целевого» регистра. Целевой регистр может быть либо источником, либо местом назначения (примерами этого служат различные инструкции COPY). Регистр может обращаться к самому себе косвенно.
Определение: Содержимое исходного регистра используется инструкцией. Адрес исходного регистра может быть указан либо (i) непосредственно с помощью инструкции, либо (ii) косвенно с помощью регистра-указателя, указанного инструкцией.
Определение: Содержимое регистра указателя представляет собой адрес «целевого» регистра.
Определение: Содержимое регистра-указателя указывает на целевой регистр – «целевым» может быть регистр источника или регистр назначения.
Определение: Регистр назначения — это место, куда инструкция помещает свой результат. Адрес исходного регистра может быть указан либо (i) непосредственно с помощью инструкции, либо (ii) косвенно с помощью регистра-указателя, указанного инструкцией. Регистры источника и назначения могут быть одними.
Регистровая машина имеет память, внешнюю по отношению к ее конечному автомату, - неограниченный (см. сноску | счетный и неограниченный) набор дискретных и уникально помеченных ячеек с неограниченной емкостью, называемых «регистрами». Эти регистры содержат только натуральные числа (ноль и положительные целые числа). В соответствии со списком последовательных инструкций в ТАБЛИЦЕ конечного автомата, несколько (например, 2) типов примитивных операций оперируют содержимым этих «регистров». Наконец, доступно условное выражение в форме IF-THEN-ELSE для проверки содержимого одного или двух регистров и «разветвления/перехода» конечного автомата из последовательности инструкций по умолчанию.
Базовая модель 1 : модель, наиболее близкая к визуализации Мински (1961) и Ламбека (1961):
Базовая модель 2 : Модель «преемника» (названная в честь функции-преемника аксиом Пеано ):
Базовая модель 3 : использовалась Элготом-Робинсоном (1964) в исследовании ограниченных и неограниченных RASP – модель «преемника» с COPY вместо CLEAR:
Три базовых набора 1, 2 или 3, приведенные выше, эквивалентны в том смысле, что можно создать инструкции одного набора, используя инструкции другого набора (интересное упражнение: подсказка Мински (1967) – объявить зарезервированный регистр, например вызов это «0» (или Z для «ноля» или E для «стирания»), чтобы содержать число 0). Выбор модели будет зависеть от того, какую модель автору легче всего использовать для демонстрации, доказательства и т. д.
Более того, из базовых наборов 1, 2 или 3 мы можем создать любую примитивно -рекурсивную функцию (см. Мински (1967), Булос-Берджесс-Джеффри (2002)). (Как расширить сеть, чтобы охватить полные и частичные мю-рекурсивные функции , будет обсуждаться в контексте косвенной адресации). Однако построение примитивно-рекурсивных функций затруднено, поскольку наборы инструкций настолько... примитивны (крошечны). Одним из решений является расширение определенного набора «удобными инструкциями» из другого набора:
Опять же, все это только для удобства; ничто из этого не увеличивает внутреннюю мощность модели.
Например: наиболее расширенный набор будет включать каждую уникальную инструкцию из трех наборов плюс безусловный переход J (z), т.е.:
Большинство авторов выбирают тот или иной из условных переходов, например, Шепердсон-Стерджис (1963) использует приведенный выше набор минус JE (чтобы быть совершенно точным, они используют JNZ – Перейти, если не ноль вместо JZ; еще одна возможная удобная инструкция).
В нашей повседневной жизни понятие «косвенной операции» не является чем-то необычным.
Косвенность указывает место, идентифицированное как пиратский сундук в «Пещере Тома_&_Бекки...», которое действует как указатель на любое другое место (включая его самого): его содержимое (карта сокровищ) предоставляет «адрес» целевого местоположения «под Тэтчер». 's_front_porch", где происходит настоящее действие.
Далее следует помнить, что эти модели представляют собой абстрактные модели с двумя фундаментальными отличиями от всего физически реального: неограниченное количество регистров, каждый из которых имеет неограниченную емкость. Проблема проявляется наиболее драматично, когда кто-то пытается использовать противомашинную модель для построения RASP, эквивалентного по Тьюрингу , и, таким образом, вычислить любую частичную мю-рекурсивную функцию :
Так как же нам обратиться к регистру за пределами конечного автомата? Один из подходов — изменить инструкции программы (те, которые хранятся в регистрах), чтобы они содержали более одной команды. Но и это может быть исчерпано, если только инструкция не имеет (потенциально) неограниченного размера. Так почему бы не использовать всего одну «сверхинструкцию» – одно действительно большое число – которое содержит все закодированные в нем инструкции программы! Вот как Мински решает проблему, но нумерация Гёделя , которую он использует, представляет большие неудобства для модели, и результат совершенно не похож на наше интуитивное представление о «компьютере с хранимой программой».
Элгот и Робинсон (1964) пришли к аналогичному выводу в отношении RASP, который «конечно определен». Действительно, он может получить доступ к неограниченному числу регистров (например, для извлечения из них инструкций), но только если RASP допускает «самомодификацию» своих программных инструкций и закодировал свои «данные» в число Гёделя (рис. 2, стр. 396). ).
В контексте более похожей на компьютер модели, использующей его инструкцию RPT (повторение), Мински (1967) дразнит нас решением проблемы (ср. стр. 214, стр. 259), но не предлагает твердого решения. Он утверждает:
Он предлагает нам ограниченный RPT, который вместе с CLR(r) и INC(r) может вычислить любую примитивно-рекурсивную функцию , и он предлагает указанный выше неограниченный RPT, играющий роль оператора μ; он вместе с CLR(r) и INC(r) может вычислять рекурсивные функции мю. Но он не обсуждает «косвенность» или модель RAM как таковую.
Из ссылок Хартманиса (1971) следует, что Кук (в своих конспектах лекций в Калифорнийском университете в Беркли, 1970) укрепил идею косвенной адресации. Это становится более ясным в статье Кука и Рекхоу (1973): Кук является руководителем магистерской диссертации Рекхоу. Модель Хартманиса, очень похожая на модель Мелзака (1961), использует сложение и вычитание с двумя и тремя регистрами, а также два копирования параметров; Модель Кука и Рекхоу сокращает количество параметров (регистров, вызываемых в инструкциях программы) до одного вызова за счет использования аккумулятора «AC».
Решение в двух словах: спроектируйте нашу машину/модель с неограниченной косвенностью – обеспечьте неограниченный «адресный» регистр, который потенциально может назвать (вызвать) любой регистр, независимо от того, сколько их. В общем, чтобы это работало, неограниченный регистр требует возможности очищаться, а затем увеличиваться (и, возможно, уменьшаться) с помощью потенциально бесконечного цикла. В этом смысле решение представляет собой неограниченный оператор μ , который может, при необходимости, искать до бесконечности вдоль неограниченной строки регистров, пока не найдет то, что ищет. Регистр указателя точно такой же, как и любой другой регистр, за одним исключением: в обстоятельствах, называемых «косвенной адресацией», он предоставляет свое содержимое, а не операнд-адрес в ТАБЛИЦЕ конечного автомата, в качестве адреса целевого регистра (включая, возможно, самого себя). !).
Если мы откажемся от подхода Мински с одним чудовищным числом в одном регистре и укажем, что наша модель машины будет «похожа на компьютер», нам придется столкнуться с этой проблемой косвенности, если мы хотим вычислить рекурсивные функции (также называемые µ- рекурсивными функциями). функции ) – как полные, так и частичные разновидности.
Наша более простая модель противомашины может выполнять «ограниченную» форму косвенности – и тем самым вычислять подкласс примитивно-рекурсивных функций – используя примитивно-рекурсивный «оператор», называемый «определением по случаям» (определенный в Клини (1952) p). 229 и Булос-Берджесс-Джеффри стр. 74). Такая «ограниченная косвенность» — трудоемкое и утомительное дело. «Определение по регистру» требует, чтобы машина определяла/отличяла содержимое регистра указателя, пытаясь раз за разом до достижения успеха сопоставить это содержимое с числом/именем, которые явно объявляет оператор регистра. Таким образом, определение по случаям начинается, например, с адреса нижней границы и до тошноты продолжается до адреса верхней границы, пытаясь найти совпадение:
«Ограниченная» косвенность не позволит нам вычислять частично рекурсивные функции — для них нам понадобится неограниченная косвенность, известная как оператор μ .
Чтобы быть эквивалентом Тьюринга, счетчиковая машина должна либо использовать неудачный однорегистровый метод чисел Мински-Гёделя , либо быть дополнена возможностью исследовать концы своей строки регистров, до бесконечности, если это необходимо. (Неспособность найти что-то «там» определяет, что означает неспособность алгоритма завершить работу; см. Kleene (1952), стр. 316 и далее, глава XII «Частичные рекурсивные функции» , в частности стр. 323–325.) Дополнительную информацию об этом см. пример ниже.
Для неограниченной косвенности нам требуется «аппаратное» изменение модели нашей машины. Как только мы внесем это изменение, модель перестанет быть счетчиковой машиной, а станет машиной произвольного доступа.
Теперь, когда, например, указано INC, инструкция конечного автомата должна будет указать, откуда будет взят адрес интересующего регистра. Это может быть либо (i) инструкция конечного автомата, которая предоставляет явную метку , либо (ii) регистр-указатель , содержимым которого является интересующий адрес. Всякий раз, когда инструкция указывает адрес регистра, ей теперь также необходимо будет указать дополнительный параметр «i/d» – «косвенный/прямой». В некотором смысле этот новый параметр «i/d» является «переключателем», который переключает один способ получения прямого адреса, как указано в инструкции, или другой способ получения косвенного адреса из регистра указателя (какой регистр указателя – в некоторых случаях модели каждый регистр может быть регистром-указателем – указано в инструкции). Этот «взаимоисключающий, но исчерпывающий выбор» является еще одним примером «определения по случаям», а арифметический эквивалент, показанный в примере ниже, получен из определения в Kleene (1952), с. 229.
Вероятно, самая полезная из добавленных инструкций — COPY. Действительно, Элгот-Робинсон (1964) снабжает свои модели P 0 и P' 0 инструкциями COPY, а Кук-Рекхау (1973) снабжает свою модель на основе аккумулятора только двумя косвенными инструкциями – КОПИРОВАТЬ в аккумулятор косвенно, КОПИРОВАТЬ из аккумулятора косвенно. .
Множество инструкций : поскольку любая инструкция, действующая на один регистр, может быть дополнена ее косвенным «двойным» (включая условные и безусловные переходы, ср. модель Элгота-Робинсона), включение косвенных инструкций удвоит количество одиночных параметров. инструкции регистра (например, INC (d, r), INC (i, r)). Хуже того, каждая инструкция с двумя параметрами/регистрами будет иметь 4 возможных варианта, например:
Аналогичным образом каждая трехрегистровая команда, включающая два исходных регистра r s1 r s2 и регистр назначения rd , приведет к 8 разновидностям, например, к сложению:
будет давать:
Если мы назначим один регистр «аккумулятором» (см. ниже) и наложим строгие ограничения на различные разрешенные инструкции, то мы сможем значительно сократить множество прямых и косвенных операций. Однако нужно быть уверенным, что полученного сокращенного набора команд достаточно, и мы должны осознавать, что сокращение будет происходить за счет большего количества инструкций на «значительную» операцию.
Историческое соглашение отводит регистр аккумулятору, «арифметическому органу», который буквально накапливает свое число во время последовательности арифметических операций:
Однако аккумулятор требует большего количества инструкций на арифметическую «операцию», в частности, в отношении так называемых инструкций «чтение-изменение-запись», таких как «косвенно увеличить содержимое регистра, на который указывает регистр r2». «A» обозначает регистр «аккумулятора» A:
Если мы присвоим аккумулятору определенное имя, например «А», мы можем указать аккумулятор в инструкциях, например:
Однако, когда мы пишем инструкции CPY без вызова аккумулятора, инструкции неоднозначны или должны иметь пустые параметры:
Исторически сложилось так, что эти две инструкции CPY получили разные имена; однако никакой конвенции не существует. Традиция (например, воображаемый компьютер MIX Кнута (1973) ) использует два названия: ЗАГРУЗКА и ХРАНЕНИЕ. Здесь мы добавляем параметр «i/d»:
В типичной модели на основе аккумулятора все арифметические и константные операции с двумя переменными (например, ADD (A, r), SUB (A, r)) используют (i) содержимое аккумулятора вместе с (ii) содержимым указанного регистра. . Операции с одной переменной (например, INC (A), DEC (A) и CLR (A)) требуют только аккумулятора. Оба типа команд записывают результат (например, сумму, разность, произведение, частное или остаток) в аккумулятор.
Если мы захотим, мы можем сократить мнемонику, потому что по крайней мере один исходный регистр и регистр назначения всегда являются аккумулятором A. Таким образом, мы имеем:
Если в нашей модели есть неограниченный аккумулятор, можем ли мы связать все остальные регистры? Не раньше, чем мы обеспечим хотя бы один неограниченный регистр, из которого мы получим наши косвенные адреса.
Минималистский подход заключается в использовании самого себя (это делает Шёнхаге).
Другой подход (Шонхаге тоже делает это) состоит в том, чтобы объявить определенный регистр «регистром косвенного адреса» и ограничить косвенность относительно этого регистра (модель RAM0 Шонхаге использует как регистры A, так и N для косвенных, а также прямых инструкций). Опять же, у нашего нового регистра нет условного имени – возможно, «N» от «iNdex», или «iNdirect», или «Номер адреса».
Для максимальной гибкости, как мы сделали для аккумулятора A, мы будем считать N просто еще одним регистром, который можно увеличивать, уменьшать, очищать, тестировать, напрямую копировать и т. д. Опять же, мы можем сжать инструкцию до одного параметра, который обеспечивает направление и косвенность, например.
Почему это такой интересный подход? Как минимум две причины:
(1) Набор команд без параметров:
Шенхаге делает это, чтобы создать свой набор инструкций RAM0. См. раздел ниже.
(2) Уменьшите ОЗУ до машины Пост-Тьюринга:
Выдавая себя за минималистов, мы сводим все регистры, за исключением аккумулятора A и регистра косвенности N, например, r = { r0, r1, r2, ... }, к неограниченной строке ячеек (очень) ограниченной емкости. Они не будут делать ничего, кроме хранения (очень) ограниченных чисел, например, одиночного бита со значением {0, 1}. Аналогичным образом мы сжимаем аккумулятор до одного бита. Мы ограничиваем любую арифметику регистрами { A, N }, используем косвенные операции для извлечения содержимого регистров в аккумулятор и записи 0 или 1 из аккумулятора в регистр:
Мы продвигаемся дальше и полностью исключаем A, используя два «постоянных» регистра, называемых «ERASE» и «PRINT»: [ERASE]=0, [PRINT]=1.
Переименуйте инструкции COPY и вызовите INC (N) = RIGHT, DEC (N) = LEFT, и мы получим те же инструкции, что и машина Пост-Тьюринга, плюс дополнительный CLRN:
В разделе выше мы неофициально показали, что ОЗУ с неограниченной возможностью косвенности создает машину Пост-Тьюринга . Машина Пост-Тьюринга эквивалентна Тьюрингу, поэтому мы показали, что ОЗУ с косвенностью эквивалентно Тьюрингу.
Мы даем здесь несколько более формальную демонстрацию. Начните с разработки нашей модели с тремя зарезервированными регистрами «E», «P» и «N», а также неограниченным набором регистров 1, 2, ..., n справа. Регистры 1, 2, ..., n будем считать «квадратами ленты». Регистр «N» указывает на «отсканированный квадрат», который в данный момент наблюдает «голова». «Голову» можно рассматривать как находящуюся в условном переходе – обратите внимание, что она использует косвенную адресацию (ср. Элгот-Робинсон, стр. 398). Когда мы уменьшаем или увеличиваем «N», (кажущаяся) голова будет «перемещаться влево» или «вправо» вдоль квадратов. Мы переместим содержимое «E»=0 или «P»=1 в «отсканированный квадрат», на который указывает N, используя косвенный CPY.
Тот факт, что наша лента имеет левый конец, ставит нас перед небольшой проблемой: всякий раз, когда появляется LEFT, нашим инструкциям придется проверять, является ли содержимое «N» нулем; в этом случае нам следует оставить его счетчик равным «0» (это наш выбор как дизайнеров — например, мы можем сделать так, чтобы машина/модель «запускала событие» по нашему выбору).
В следующей таблице определены инструкции Пост-Тьюринга с точки зрения их эквивалентных инструкций в ОЗУ, а также приведен пример их функционирования. (Видимое) расположение головки на ленте регистров r0-r5. . . показан заштрихованным:
На протяжении всей этой демонстрации мы должны помнить, что инструкции в таблице TABLE конечного автомата ограничены , то есть конечны :
Мы построим косвенный CPY (i, q, d, φ) с помощью оператора CASE. Адрес целевого регистра будет определяться содержимым регистра «q»; как только оператор CASE определит это число, CPY напрямую поместит содержимое регистра с этим номером в регистр «φ». Нам понадобится дополнительный регистр, который мы назовем «y» — он выполняет функцию обратного счетчика.
«Оператор» CASE описан у Клини (1952) (стр. 229) и у Булоса-Берджесса-Джеффри (2002) (стр. 74); последние авторы подчеркивают его полезность. Следующее определение дано Клини, но изменено, чтобы отразить знакомую конструкцию «ЕСЛИ-ТО-ЛИБО».
Оператор CASE «возвращает» натуральное число в φ в зависимости от того, какой «case» удовлетворен, начиная с «case_0» и последовательно проходя через «case_last»; если ни один случай не удовлетворен, то число, называемое «по умолчанию» (также известное как «вупс»), возвращается в φ (здесь x обозначает некоторый выбор параметров, например, регистр q и строку r0, ... rlast )):
Определение по случаям φ( x , y):
Клини требует, чтобы все «предикаты» Q n , выполняющие тестирование, были взаимоисключающими: «предикаты» — это функции, которые выдают только { true, false } для вывода; Булос-Берджесс-Джеффри добавляют требование о том, чтобы дела были «исчерпывающими».
Мы начинаем с числа в регистре q, которое представляет адрес целевого регистра. Но что это за число? «Предикаты» проверят это, чтобы выяснить это, одно испытание за другим: JE (q, y, z), за которым следует INC (y). Как только число идентифицировано явно, оператор CASE напрямую/явно копирует содержимое этого регистра в φ:
Case_0 (базовый шаг рекурсии по y) выглядит так:
Case_n (шаг индукции) выглядит следующим образом; помните, что каждый экземпляр "n", "n+1",..., "last" должен быть явным натуральным числом:
Case_last останавливает индукцию и ограничивает оператор CASE (и тем самым ограничивает оператор «косвенного копирования»):
Если бы CASE мог продолжаться до бесконечности, это был бы оператор mu . Но он не может — «регистр состояний» его конечного автомата достиг максимального значения (например, 65365 = 11111111,11111111 2 ) или в его таблице закончились инструкции; в конце концов, это конечная машина.
Часто встречающаяся модель Кука и Речкова немного похожа на модель Мальцека с троичным регистром (написанную с использованием мнемоники Кнута — в исходных инструкциях не было мнемоники, кроме TRA, Read, Print).
LOAD ( C, rd ) ; C → rd
, C — любое целое числоLOAD ( 0, 5 )
очистит регистр 5. ADD ( rs1, rs2, rd ) ; [rs1] + [rs2] → rd
, регистры могут быть одинаковыми или разными;ADD ( A, A, A )
удвоит содержимое регистра А. SUB ( rs1, rs2, rd ) ; [rs1] - [rs2] → rd
, регистры могут быть одинаковыми или разными:SUB ( 3, 3, 3 )
очистит регистр 3. COPY ( i, rp, d, rd ) ; [[rp] ] → rd
, Косвенно скопировать содержимое исходного регистра, на который указывает регистр-указатель r p , в регистр назначения. COPY ( d, rs, i, rp ) ; [rs] → [rp]
. Скопируйте содержимое исходного регистра r s в регистр назначения, на который указывает регистр-указатель r p . JNZ ( r, Iz ) ;
Условный переход, если [r] положительно; т.е. IF [r] > 0 THEN переход к инструкции z, иначе продолжайте последовательность (Кук и Рекхау называют это: «Перенести управление на строку m, если Xj > 0») READ ( rd ) ;
скопировать «вход» в регистр назначения r d PRINT ( rs ) ;
скопируйте содержимое исходного регистра r на «выход».Шёнхаге (1980) описывает очень примитивную атомизированную модель, выбранную для доказательства эквивалентности его модели указателя SMM :
Модель RAM1 : Шёнхаге демонстрирует, как его конструкцию можно использовать для формирования более распространенной и удобной формы оперативной памяти, подобной «преемнику» (используя мнемонику этой статьи):
LDA k ; k --> A
, k — константа, явное число, например «47». LDA ( d, r ) ; [r] → A ;
прямая загрузка А LDA ( i, r ) ; [[r]] → A ;
косвенно загрузить A STA ( d, r ) ; [A] → r ;
напрямую хранить А STA ( i, r ) ; [A] → [r] ;
косвенно сохранить A JEA ( r, z ) ; IF [A] = [r] then Iz else continue
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 then go to Iz
; неоднозначен в своем обращенииКосвенность происходит (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 и т. д.
Мы можем обойти это ограничение, предоставив неограниченный регистр для предоставления адреса регистра, указывающего косвенный адрес.
За некоторыми исключениями, эти ссылки такие же, как и в Register Machine .