В математической логике и теоретической информатике регистровая машина — это общий класс абстрактных машин , аналогичный машине Тьюринга и, таким образом, полный по Тьюрингу . В отличие от машины Тьюринга, которая использует ленту и головку, регистровая машина использует несколько уникально адресуемых регистров для хранения неотрицательных целых чисел. Существует несколько подклассов регистровых машин, включая счетчиковые машины , указатели , машины с произвольным доступом (RAM) и машину с произвольным доступом и хранимой программой (RASP) , каждый из которых отличается по сложности. Эти машины, особенно в теоретических исследованиях, помогают в понимании вычислительных процессов. Концепция регистровых машин также может быть применена к виртуальным машинам в практической информатике в образовательных целях и для снижения зависимости от конкретных аппаратных архитектур.
Регистровая машина получила свое название из-за использования одного или нескольких « регистров ». В отличие от ленты и головки, используемых машиной Тьюринга , модель использует несколько уникально адресуемых регистров , каждый из которых содержит одно неотрицательное целое число .
В литературе встречается по крайней мере четыре подкласса . В порядке возрастания сложности:
Любая правильно определенная модель регистровой машины является полной по Тьюрингу . Скорость вычислений сильно зависит от специфики модели.
В практической информатике иногда используется связанная концепция, известная как виртуальная машина , чтобы уменьшить зависимость от базовой архитектуры машины. Эти виртуальные машины также используются в образовательных учреждениях. В учебниках термин «регистровая машина» иногда используется взаимозаменяемо для описания виртуальной машины. [1]
Регистровая машина состоит из:
Подробнее об условном выражении «ЕСЛИ r=0 ТО z истинно ИНАЧЕ z ложно » см. в «Формализме Маккарти» [5]
В начале 1950-х годов появились две тенденции. Первая заключалась в том, чтобы охарактеризовать компьютер как машину Тьюринга. Вторая заключалась в том, чтобы определить компьютероподобные модели — модели с последовательными последовательностями инструкций и условными переходами — с мощью машины Тьюринга, так называемая эквивалентность Тьюринга. Необходимость в этой работе была выполнена в контексте двух «трудных» проблем: неразрешимой проблемы слов, поставленной Эмилем Постом [6] — его проблемы «тега» — и очень «трудной» проблемы проблем Гильберта — 10-го вопроса вокруг диофантовых уравнений . Исследователи искали модели, эквивалентные Тьюрингу, которые были бы менее «логическими» по своей природе и более «арифметическими». [2] : 281 [7] : 218
Первый шаг к характеристике компьютеров был сделан [nb 3] Гансом Гермесом (1954), [8] Рожей Петером (1958), [9] и Хайнцем Капхенгстом (1959), [10] второй шаг — Хао Ваном (1954, [11] 1957 [12] ) и, как отмечено выше, продолжен Здзиславом Александром Мельцаком (1961), [2] Иоахимом Ламбеком (1961) [4] и Марвином Мински (1961, [3] 1967 [13] ).
Последние пять имен Юрий Матиясевич перечисляет именно в таком порядке . Далее он пишет:
Ламбек, Мельзак, Мински, Шепердсон и Стерджис независимо друг от друга открыли одну и ту же идею в одно и то же время. См. примечание о приоритете ниже.
История начинается с модели Вана.
Работа Вана основывалась на статье Эмиля Поста (1936) [6] и привела Вана к определению его B-машины Вана — двухсимвольной модели вычислений Пост-Тьюринговой машины, содержащей всего четыре атомарных инструкции:
{ ВЛЕВО, ВПРАВО, ПЕЧАТЬ, ПЕРЕХОД_если_отмечен_к_инструкции_z }К этим четырём и Ван (1954, [11] 1957 [12] ), и затем CY Lee (1961) [15] добавили ещё одну инструкцию из набора Поста {ERASE}, а затем безусловный переход Поста {JUMP_to_instruction_z} (или, для простоты, условный переход JUMP_IF_blank_to_instruction_z, или и то, и другое. Ли назвал это моделью «W-машины»:
{ ВЛЕВО, ВПРАВО, ПЕЧАТЬ, СТИРАНИЕ, JUMP_if_marked, [возможно JUMP или JUMP_IF_blank] }Ван выразил надежду, что его модель станет «сближением» : 63 между теорией машин Тьюринга и практическим миром компьютеров.
Работа Вана была очень влиятельной. Мы находим, что на него ссылаются Минский (1961) [3] и (1967), [13] Мелзак (1961), [2] Шепердсон и Стерджис (1963). [7] Действительно, Шепердсон и Стерджис (1963) отмечают, что:
Мартин Дэвис в конечном итоге развил эту модель в (2-символьную) пост-Тьюринговскую машину.
Трудности с моделью Вана/Пост-Тьюринга :
За исключением того, что была проблема: модель Вана (шесть инструкций 7-инструкционной машины Пост-Тьюринга) все еще была одноленточным устройством типа Тьюринга, каким бы хорошим ни был ее последовательный поток инструкций программы . И Мелзак (1961) [2] , и Шепердсон и Стерджис (1963) [7] наблюдали это (в контексте определенных доказательств и исследований):
Действительно, как показывают примеры машин Тьюринга , пост-машин Тьюринга и частичных функций , работа может быть «сложной».
Первоначальная мысль приводит к «разрезанию ленты» так, чтобы каждая была бесконечно длинной (чтобы вместить целое число любого размера), но заканчивалась слева. Эти три ленты называются «лентами пост-Тьюринга (т. е. лентами типа Вана)». Отдельные головки движутся влево (для уменьшения) и вправо (для увеличения). В некотором смысле головки указывают «вершину стопки» конкатенированных меток. Или в Мински (1961) [3] и Хопкрофте и Ульмане (1979), [16] : 171ff лента всегда пуста, за исключением метки на левом конце — головка никогда не печатает и не стирает.
Необходимо внимательно писать инструкции, чтобы перед декрементом происходила проверка на ноль и переход, в противном случае машина «упадет с конца» или «упрется в конец», создавая экземпляр частичной функции .
Минский (1961) [3] и Шепердсон–Стерджис (1963) [7] доказывают, что только несколько лент — всего одна — все еще позволяют машине быть эквивалентной по Тьюрингу, если данные на ленте представлены как число Гёделя (или какое-либо другое уникально кодируемое число Encodable-decodable); это число будет меняться по мере выполнения вычислений. В версии с одной лентой с кодированием числа Гёделя счетчик должен уметь (i) умножать число Гёделя на константу (числа «2» или «3») и (ii) делить на константу (числа «2» или «3») и переходить, если остаток равен нулю. Минский (1967) [13] показывает, что необходимость в этом странном наборе инструкций может быть смягчена до { INC (r), JZDEC (r, z) } и удобных инструкций { CLR (r), J (r) }, если доступны две ленты. Однако простая Гёделизация все еще требуется. Похожий результат появляется в работе Элгота–Робинсона (1964) [17] относительно их модели RASP.
Модель Мелзака (1961) [2] существенно отличается. Он взял свою собственную модель, перевернул ленты вертикально, назвал их «ямками в земле», которые нужно заполнить «счетчиками камешков». В отличие от «приращения» и «уменьшения» Мински, Мелзак допускал правильное вычитание любого количества камешков и «прибавление» любого количества камешков.
Он определяет косвенную адресацию для своей модели [2] : 288 и приводит два примера ее использования; [2] : 89 его «доказательство» [2] : 290–292 того, что его модель эквивалентна модели Тьюринга, настолько схематично, что читатель не может сказать, намеревался ли он сделать косвенную адресацию обязательным условием доказательства.
Наследием модели Мелзака является упрощение Ламбека и повторное появление его мнемонических соглашений в работе Кука и Рекхова 1973 года. [18]
Ламбек (1961) [4] взял троичную модель Мелзака и разложил ее на две унарные инструкции — X+, X−, если возможно, иначе переход — точно такие же две, которые придумал Мински (1961) [3] .
Однако, как и модель Мински (1961) [3] , модель Ламбека выполняет свои инструкции последовательно по умолчанию — как X+, так и X− несут идентификатор следующей инструкции, а X− также несет инструкцию перехода, если нулевой тест пройден успешно.
Машина RASP или машина с произвольной выборкой и хранимой программой начинается как счетная машина с ее "программой инструкций", размещенной в ее "регистрах". Аналогично, но независимо от "регистра инструкций" конечного автомата, по крайней мере один из регистров (называемый "счетчиком программ" (PC)) и один или несколько "временных" регистров поддерживают запись и работают с номером текущей инструкции. ТАБЛИЦА инструкций конечного автомата отвечает за (i) выборку текущей инструкции программы из соответствующего регистра, (ii) разбор инструкции программы , (iii) выборку операндов, указанных инструкцией программы , и (iv) выполнение инструкции программы .
За исключением проблемы: если базироваться на шасси машины -счетчика, эта машина фон Неймана , похожая на компьютер , не будет эквивалентна Тьюрингу. Она не может вычислить все, что вычислимо. По сути, модель ограничена размером инструкций ее (очень-) конечного автомата. RASP на основе машины-счетчика может вычислить любую примитивную рекурсивную функцию (например, умножение), но не все мю-рекурсивные функции (например, функцию Аккермана ).
Элгот–Робинсон исследуют возможность позволить своей модели RASP «самомодифицировать» свои программные инструкции. [17] Идея была старой, предложенной Берксом–Голдстайном–фон Нейманом (1946–1947), [19] и иногда называемой «вычисляемым goto». Мелзак (1961) [2] специально упоминает «вычисляемый goto» по имени, но вместо этого предоставляет своей модели косвенную адресацию.
Вычисляемый goto: программа инструкций RASP , которая изменяет «адрес goto» в инструкции программы условного или безусловного перехода .
Но это не решает проблему (если только не прибегнуть к числам Гёделя ). Необходим метод извлечения адреса инструкции программы, которая лежит (далеко) «за/выше» верхней границы регистра инструкций конечного автомата и ТАБЛИЦЫ.
Минский (1967) [13] намекает на эту проблему в своем исследовании счетной машины (он называет их «программными компьютерными моделями»), снабженной инструкциями { CLR (r), INC (r) и RPT («a» умножить на инструкции m до n) }. Он не говорит нам, как решить эту проблему, но он замечает, что:
Но Элгот и Робинсон решают эту проблему: [17] Они дополняют свой P 0 RASP индексированным набором инструкций — несколько более сложной (но более гибкой) формой косвенной адресации. Их модель P' 0 адресует регистры, добавляя содержимое «базового» регистра (указанного в инструкции) к «индексу», явно указанному в инструкции (или наоборот, меняя местами «базу» и «индекс»). Таким образом, индексирующие инструкции P' 0 имеют на один параметр больше, чем неиндексирующие инструкции P 0 :
К 1971 году Хартманис упростил индексацию до косвенной для использования в своей модели RASP. [20]
Косвенная адресация: Указатель-регистр предоставляет конечному автомату адрес целевого регистра, необходимого для инструкции. Другими словами: содержимое указателя -регистра является адресом "целевого" регистра, который будет использоваться инструкцией. Если указатель-регистр не ограничен, ОЗУ и подходящий RASP, построенный на его шасси, будут эквивалентны Тьюрингу. Целевой регистр может служить как исходным, так и целевым регистром, как указано в инструкции.
Обратите внимание, что конечный автомат не должен явно указывать адрес этого целевого регистра. Он просто говорит остальной части машины: дай мне содержимое регистра, на который указывает мой указатель-регистр, а затем сделай с ним xyz. Он должен явно указать по имени, через свою инструкцию, этот указатель-регистр (например, "N", или "72", или "PC" и т. д.), но ему не нужно знать, какое число на самом деле содержит указатель-регистр (возможно, 279 431).
Кук и Рекхов (1973) [18] цитируют Хартманиса (1971) [20] и упрощают его модель до того, что они называют машиной с произвольным доступом (RAM — т.е. машина с косвенностью и архитектурой Гарварда). В некотором смысле мы возвращаемся к Мелзаку (1961) [2], но с гораздо более простой моделью, чем у Мелзака.
Минский работал в лаборатории Линкольна Массачусетского технологического института и опубликовал свою работу там; его статья была получена для публикации в Annals of Mathematics 15 августа 1960 года, но не опубликована до ноября 1961 года. [3] Хотя получение произошло за целый год до того, как работа Мелзака [2] и Ламбека [4] была получена и опубликована (получена, соответственно, в мае и 15 июня 1961 года и опубликована бок о бок в сентябре 1961 года). То, что (i) оба были канадцами и были опубликованы в Canadian Mathematical Bulletin , (ii) ни один из них не мог ссылаться на работу Минского, поскольку она еще не была опубликована в рецензируемом журнале, но (iii) Мелзак ссылается на Вана, а Ламбек ссылается на Мелзака, приводит к гипотезе, что их работа была выполнена одновременно и независимо.
Почти то же самое произошло с Шепердсоном и Стерджисом. [21] Их статья была получена в декабре 1961 года — всего через несколько месяцев после того, как была получена работа Мелзака и Ламбека. Опять же, у них было мало (максимум 1 месяц) или вообще не было никакой выгоды от рецензирования работы Мински. Они были осторожны, отмечая в сносках, что статьи Ершова, [22] Капенгста [10] и Петера [9] «недавно появились» [21] : 219 Они были опубликованы намного раньше, но появились на немецком языке в немецких журналах, поэтому возникают вопросы доступности.
Окончательная статья Шепердсона и Стерджиса появилась в рецензируемом журнале только в 1963 году. [7] И как они отмечают в своем Приложении А, «системы» Капенгста (1959), [10], Ершова (1958), [22] и Петера (1958) [9] настолько похожи на результаты, полученные позже, что их невозможно отличить от следующих:
Действительно, Шеферсон и Стерджис приходят к выводу:
По дате публикации первыми были работы Капенгста (1959), [10] Ершова (1958), [22] Петера (1958). [9]
Фоновые тексты: Следующая библиография исходных статей включает ряд текстов, которые можно использовать в качестве фона. Математику, которая привела к потоку статей об абстрактных машинах в 1950-х и 1960-х годах, можно найти в van Heijenoort (1967) [23] — сборнике оригинальных статей, охватывающих 50 лет от Фреге (1879) [24] до Гёделя (1931). [25] Davis (ред.) The Undecidable (1965) [26] несет факел вперед, начиная с Гёделя (1931) [25] через постскриптум Гёделя (1964); [27] : 71 оригинальные статьи Алана Тьюринга (1936 [28] –1937) и Эмиля Поста (1936) [6] включены в The Undecidable . Математика Чёрча, Россера и Клини, которая появляется как перепечатки оригинальных статей в The Undecidable , развита далее в Kleene (1952), [29] обязательный текст для тех, кто стремится к более глубокому пониманию математики, лежащей в основе машин. И Kleene (1952) [29] , и Davis (1958) [30] упоминаются в ряде статей.
Для хорошего рассмотрения счетчиковой машины см. Минский (1967) Глава 11 «Модели, подобные цифровым компьютерам» — он называет счетчиковую машину «программным компьютером». [13] Недавний обзор можно найти у ван Эмде Боаса (1990). [31] Недавнее рассмотрение модели Минского (1961) [3] /Ламбека (1961) [4] можно найти у Булоса–Берджеса–Джеффри (2002); [32] они реинкарнируют «модель абака» Ламбека, чтобы продемонстрировать эквивалентность машин Тьюринга и частично рекурсивных функций, и они предоставляют введение на уровне выпускника как в абстрактные модели машин (контр- и Тьюринг-), так и в математику теории рекурсии. Начиная с первого издания Булоса–Берджеса (1970) [33] эта модель появилась практически с той же обработкой.
Статьи : Статьи начинаются с Вана (1957) [12] и его радикального упрощения машины Тьюринга. Тьюринг (1936), [28] Клини (1952), [29] Дэвис (1958), [30] и, в частности, Пост (1936) [6] цитируются в Ване (1957); [12] в свою очередь, на Вана ссылаются Мелзак (1961), [2] Минский (1961), [3] и Шепердсон–Стерджис (1961–1963) [21] [7], поскольку они независимо сводят ленты Тьюринга к «счетчикам». Мелзак (1961) [2] предоставляет свою модель машины счетчика «камешек в лунках» с косвенностью, но не развивает ее дальше. Работа Элгота–Робинсона (1964) [17] определяет RASP — компьютероподобные машины с произвольным доступом и хранимой программой — и, по-видимому, является первой, исследующей неспособность машины с ограниченным счетчиком вычислять мю-рекурсивные функции. Эта неспособность — за исключением драконовского использования чисел Гёделя в манере Мински (1961) [3] — приводит к их определению «индексированных» инструкций (т. е. косвенной адресации) для их модели RASP. Элгот–Робинсон (1964) [17] и, в большей степени, Хартманис (1971) [20] исследуют RASP с самомодифицирующимися программами. Хартманис (1971) [20] определяет набор инструкций с косвенностью, ссылаясь на лекции Кука (1970). [34] Для использования в исследованиях вычислительной сложности Кук и его аспирант Рекхов (1973) [18] дают определение RAM (их модель и мнемоническое соглашение похожи на модель Мелзака, но не дают ему ссылки в статье). Указательные машины являются ответвлением Кнута (1968, [35] 1973) и независимо Шёнхаге (1980). [36]
В большинстве статей содержится математика, выходящая за рамки уровня бакалавриата, в частности примитивные рекурсивные функции и мю-рекурсивные функции, изящно представленные в работе Клини (1952) [29] и менее подробно, но тем не менее полезно, в работе Булоса–Берджесса–Джеффри (2002). [32]
Все тексты и статьи, за исключением четырех отмеченных звездочкой, были засвидетельствованы. Эти четыре написаны на немецком языке и появляются в качестве ссылок в работах Шепердсона–Стерджиса (1963) [7] и Элгота–Робинсона (1964); [17] Шепердсон–Стерджис (1963) [7] предлагают краткое обсуждение своих результатов в Приложении А Шепердсона–Стерджиса. Терминология по крайней мере одной статьи (Кафенгст (1959) [10] , по-видимому, восходит к анализу архитектуры компьютера Берка–Голдстайна–фон Неймана (1946–1947) [19] .
