Зарегистрировать машину

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

Обзор

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

встречается как минимум четыре подкласса В литературе . В порядке возрастания сложности это:

• Счетная машина – наиболее примитивная и упрощенная теоретическая модель компьютерного оборудования. Отсутствие косвенной адресации. Инструкции находятся в конечном автомате в духе Гарвардской архитектуры .
• Указательная машина - смесь моделей счетчика и RAM. Менее распространена и более абстрактна, чем любая модель. Инструкции находятся в конечном автомате в духе Гарвардской архитектуры.
• Машина произвольного доступа (ОЗУ) – машина-счетчик с косвенной адресацией и, как правило, с расширенным набором команд. Инструкции находятся в конечном автомате в духе Гарвардской архитектуры.
• Модель машины с произвольным доступом и хранимой программой (RASP) — ОЗУ с инструкциями в регистрах, аналогично универсальной машине Тьюринга ; его создание является примером архитектуры фон Неймана . Но в отличие от компьютера, модель идеализирована с фактически бесконечными регистрами (и, если они используются, фактически бесконечными специальными регистрами, такими как аккумуляторы ). Однако по сравнению с современным компьютером набор команд все еще меньше по количеству и сложности.

Любая правильно определенная модель регистровой машины является эквивалентом Тьюринга . Скорость вычислений во многом зависит от особенностей модели.

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

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

Регистрационная машина состоит из:

1. Неограниченное количество помеченных, дискретных, неограниченных регистров, неограниченных по размеру (емкости) : конечный (или бесконечный в некоторых моделях) набор регистров. $r_{0}\ldots r_{n}$ каждый из них считается бесконечным и содержит одно неотрицательное целое число (0, 1, 2, ...). Регистры могут выполнять свои собственные арифметические действия или могут быть один или несколько специальных регистров, выполняющих арифметические действия, например «аккумулятор» и/или «адресный регистр». См. также Машина с произвольным доступом .
2. Счетчики или отметки : дискретные, неразличимые объекты или знаки только одного вида, подходящие для модели. В наиболее сокращенной модели счетной машины за каждую арифметическую операцию только один объект/метка либо добавляется, либо удаляется из ее местоположения/ленты. В некоторых моделях счетчиков (например, Melzak, Минский ) и в большинстве моделей RAM и RASP более одного объекта/метки можно добавить или удалить за одну операцию с «сложением» и обычно «вычитанием»; иногда с «умножением» и/или «делением». Некоторые модели имеют операции управления, такие как «копирование» (или альтернативно: «перемещение», «загрузка», «сохранение»), которые перемещают «группы» объектов/меток из регистра в регистр за одно действие.
3. Ограниченный набор инструкций : инструкции имеют тенденцию делиться на два класса: арифметические и управляющие. Инструкции извлекаются из двух классов для формирования «наборов инструкций», так что набор инструкций должен позволять модели быть эквивалентной по Тьюрингу (он должен быть в состоянии вычислить любую частично рекурсивную функцию ).
   1. Арифметика : арифметические инструкции могут работать со всеми регистрами или с определенным регистром, например аккумулятором. Обычно они выбираются из следующих наборов, хотя существуют исключения: Счетчик: { Инкремент (r), Декремент (r), Сброс в ноль (r) } Уменьшенная RAM, RASP: { Инкремент (r), Декремент ( r), сброс до нуля (r), постоянная нагрузки k, Add ( $r_{1},r_{2}$), Правильное вычитание ( $r_{1},r_{2}$), Увеличение аккумулятора, Уменьшение аккумулятора, Очистка аккумулятора, Добавление содержимого регистра r в аккумулятор, Правильное вычитание содержимого регистра r из аккумулятора } Расширенное ОЗУ, RASP: включает все сокращенные инструкции, а также: { Умножение , деление, различные логические побитовые операции (сдвиг влево, проверка битов и т. д.) }
   2. Управление : Модели счетчиков: Опционально включают { Копирование ( $r_{1},r_{2}$) }. Модели RAM и RASP: большинство из них включают { Copy ( $r_{1},r_{2}$) } или { Загрузить аккумулятор из r, Сохранить аккумулятор в r, Загрузить аккумулятор немедленной константой }. Все модели: включают по крайней мере один условный «переход» (ветвь, переход) после проверки регистра, например { Jump-if-zero, Jump-if-not-zero (т. е. Jump-if-positive), Jump. -если-равно, Перейти-если-не-равно }. Все модели дополнительно включают: { безусловный переход к программе (goto) }.
   3. Регистровый метод адресации :
      • Счетная машина: нет косвенной адресации, в сильно атомизированных моделях возможны немедленные операнды.
      • RAM и RASP: доступна косвенная адресация, типичны непосредственные операнды
   4. Ввод-вывод : опционально во всех моделях.
4. Государственный регистр : специальный регистр инструкций (IR), отличный от упомянутых ранее регистров, хранит текущую команду, которая должна быть выполнена, вместе с ее адресом в таблице команд. Этот регистр вместе со связанной с ним таблицей находится внутри конечного автомата. ИК недоступен во всех моделях. В случае RAM и RASP для определения «адреса» регистра модель может выбрать либо (i) адрес, указанный в таблице и временно сохраненный в IR для прямой адресации, либо (ii) содержимое регистра. указанный инструкцией в ИР для косвенной адресации. Важно отметить, что IR не является «счетчиком программ» (ПК) RASP (или обычного компьютера). PC — это просто еще один регистр, аналогичный аккумулятору, но специально зарезервированный для хранения номера текущей инструкции RASP на основе регистров. Таким образом, RASP имеет два регистра «инструкций/программ»: (i) IR (регистр инструкций конечного автомата) и (ii) PC ​​(счетчик программ) для программы, хранящейся в регистрах. Кроме того, помимо ПК, RASP может также выделить еще один регистр для «Регистра программ и команд» (называемого различными именами, такими как «PIR», «IR», «PR» и т. д.).
5. Список помеченных инструкций, обычно в последовательном порядке : конечный список инструкций. $I_{1}\ldots I_{m}$. В случае машины со счетчиком, машины с произвольным доступом (ОЗУ) и машины с указателем хранилище команд находится в «ТАБЛИЦЕ» конечного автомата; таким образом, эти модели являются примерами Гарвардской архитектуры. В случае RASP хранилище программ находится в регистрах; таким образом, это пример архитектуры фон Неймана. См. также «Машина с произвольным доступом» и «Машина с произвольным доступом» .
   Обычно, как и в компьютерных программах , инструкции располагаются в последовательном порядке; если прыжок не окажется успешным, последовательность по умолчанию продолжается в числовом порядке. Исключением являются счеты. модели счетчиковых машин — каждая инструкция имеет хотя бы один идентификатор «следующей» инструкции «z», а условная ветвь — два.
   • Также обратите внимание, что модель счетов объединяет две инструкции: JZ, а затем DEC: например, { INC ( r, z ), JZDEC ( r, z _true , z _false ) }.
     см . в разделе «Формализм Маккарти» Дополнительную информацию об условном выражении «IF r=0 THEN z _true ELSE z _false ».

развитие модели

В начале 1950-х годов появились две тенденции: первая заключалась в том, чтобы охарактеризовать компьютер как машину Тьюринга, вторая заключалась в том, чтобы определить компьютероподобные модели — модели с последовательными последовательностями команд и условными переходами — с мощью машины Тьюринга, т.е. - так называемая эквивалентность Тьюринга. Необходимость этой работы возникла в контексте двух «трудных» проблем: неразрешимой проблемы слова, поставленной Эмилем Постом. — его проблема «метки» — и очень «сложная» проблема из проблем Гильберта — 10-й вопрос о диофантовых уравнениях . Исследователи искали модели, эквивалентные Тьюрингу, которые были бы менее «логическими» по своей природе и более «арифметическими».

Первый шаг к характеристике компьютеров был сделан с Гансом Гермесом (1954), Петер Рожа (1958), и Хайнц Капенгст (1959), второй шаг с Хао Вангом (1954, 1957 ) и, как отмечалось выше, поддержанный Здзиславом Александром Мельзаком (1961), Иоахим Ламбек (1961) и Марвин Мински (1961, 1967 ).

Последние пять имен приведены именно в таком порядке Юрием Матиясевичем . Он продолжает:

«Регистровые машины [некоторые авторы используют термин «регистровая машина» как синоним «счетной машины»] особенно подходят для построения диофантовых уравнений. Как и машины Тьюринга, они имеют очень примитивные инструкции и, кроме того, имеют дело с числами».

Ламбек, Мельзак, Мински, Шепердсон и Стерджис независимо друг от друга одновременно открыли одну и ту же идею. См. примечание о приоритете ниже.

История начинается с модели Ванга.

Ванга (1954, 1957): машина Пост

Работа Ванга последовала за работой Эмиля Поста (1936). статью и привел Ванга к определению его B-машины Ванга — двухсимвольной вычислительной модели машины Пост-Тьюринга всего с четырьмя атомарными инструкциями:

{ ВЛЕВО, ВПРАВО, ПЕЧАТЬ, JUMP_if_marked_to_instruction_z }

К этим четырём оба Ванга (1954, 1957 ), а затем Сай Ли (1961) добавил еще одну инструкцию из набора Post { ERASE }, а затем безусловный переход Post { JUMP_to_ Instruction_z } (или, чтобы упростить задачу, условный переход JUMP_IF_blank_to_instruction_z или и то, и другое. Ли назвал это моделью «W-машины»:

{ ВЛЕВО, ВПРАВО, ПЕЧАТЬ, СТЕРЕТЬ, JUMP_if_marked, [может быть JUMP или JUMP_IF_blank] }

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

Работы Ванга имели большое влияние. Мы находим ссылку на него у Мински (1961). и (1967), Мельзак (1961), Шепердсон и Стерджис (1963). Действительно, Шепердсон и Стерджис (1963) отмечают, что:

«...мы попытались сделать еще один шаг вперед в «сближении» между практическими и теоретическими аспектами вычислений, предложенном Вангом»

Мартин Дэвис в конечном итоге развил эту модель в (2-символьную) машину Пост-Тьюринга.

Трудности с моделью Ванга/Поста-Тьюринга :

Но была проблема: модель Ванга (шесть инструкций машины Пост-Тьюринга с 7 командами) по-прежнему представляла собой одноленточное устройство типа Тьюринга, каким бы хорошим ни ее последовательный поток команд программы был . Оба Мельзака (1961) и Шепердсон и Стерджис (1963) заметил следующее (в контексте некоторых доказательств и расследований):

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

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

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

ленту» на множество

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

Необходимо позаботиться о написании инструкций так, чтобы перед уменьшением происходила проверка на ноль и переход, иначе машина «упадет с конца» или «ударится о конец», создавая экземпляр частичной функции .

Минский (1961) и Шепердсон-Стерджис (1963) докажите, что лишь несколько лент — всего лишь одна — по-прежнему позволяют машине быть эквивалентной по Тьюрингу, если данные на ленте представлены в виде числа Гёделя (или какого-либо другого однозначно кодируемого Кодируемо-декодируемого числа); это число будет меняться по мере продолжения вычислений. В версии с одной лентой с кодированием числа Гёделя счетчик должен иметь возможность (i) умножать число Гёделя на константу (числа «2» или «3») и (ii) делить на константу (числа «2» или «3») и прыгайте, если остаток равен нулю. Минский (1967) показывает, что необходимость в этом причудливом наборе команд может быть уменьшена до { INC (r), JZDEC (r, z) } и удобных инструкций { CLR (r), J (r) }, если доступны две ленты. Однако простая гёделизация по-прежнему необходима. Аналогичный результат появляется у Элгота-Робинсона (1964). относительно их модели RASP.

Модель Мельзака (1961) отличается: комки гальки входят в отверстия и выходят

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

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

Наследием модели Мельзака является упрощение Ламбека и повторное появление его мнемонических соглашений у Кука и Рекхоу, 1973.

модель Мельзака в модель Мински (1961): INC и DEC-with-

Ламбек (1961) взял троичную модель Мельзака и раздробил ее до двух унарных инструкций — X+, X-, если возможно, еще переход — точно тех же двух, что Мински (1961). придумал.

Однако, как и Минский (1961) В модели Ламбека инструкции выполняются последовательно по умолчанию — и X+, и X- несут идентификатор следующей инструкции, а X- также несет инструкцию перехода, если нулевая проверка прошла успешно.

проблема RASP без

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

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

Элгот-Робинсон исследуют возможность разрешить своей модели RASP «самомодифицировать» свои программные инструкции. Идея была старой, предложенной Берксом-Голдстайном-фон Нейманом (1946–1947). и иногда его называют «вычисляемым переходом». Мельзак (1961) конкретно упоминает «вычисленный переход» по имени, но вместо этого предоставляет своей модели косвенную адресацию.

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

Но это не решает проблему (если только не прибегнуть к числам Гёделя ). Что необходимо, так это метод получения адреса программной инструкции, которая находится (далеко) «за пределами/выше» верхней границы регистра команд конечного автомата и TABLE.

Пример: счетная машина, оснащенная только четырьмя неограниченными регистрами, может, например, умножать любые два числа ( m, n ) вместе, чтобы получить p — и, таким образом, быть примитивно-рекурсивной функцией — независимо от того, насколько велики числа m и n; причем для этого потребуется менее 20 инструкций! например { 1: CLR ( p ), 2: JZ ( m, Done ), 3 external_loop: JZ ( n, Done ), 4: CPY ( m, temp ), 5: внутренний_цикл: JZ ( m, external_loop ), 6: DEC (m), 7: INC (p), 8: J (inner_loop), 9: external_loop: DEC (n), 10 J (external_loop), HALT }

Однако, имея всего 4 регистра, эта машина недостаточно велика для создания RASP, который может выполнять алгоритм умножения как программу . Независимо от того, насколько большим мы построим наш конечный автомат, всегда найдется программа ( включая ее параметры), которая будет больше. Таким образом, машина с ограниченной программой, которая не использует трюки с неограниченным кодированием, такие как числа Гёделя, по определению не может быть универсальной .

Минский (1967) намекает на эту проблему в своем исследовании счетчиковой машины (он называет их «программными компьютерными моделями»), оснащенной инструкциями { CLR (r), INC (r) и RPT («a» умножает инструкции от m до n) } . Он не говорит нам, как решить проблему, но замечает, что:

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

Но Элгот и Робинсон решают проблему: Они дополняют свой P ₀ RASP индексированным набором инструкций — несколько более сложной (но более гибкой) формой косвенной адресации. модель P'0 _Их обращается к регистрам путем добавления содержимого «базового» регистра (указанного в инструкции) к «индексу», явно указанному в инструкции (или наоборот, меняя местами «базовый» и «индекс»). Таким образом, индексирующие инструкции P'0 _имеют на один параметр больше, чем неиндексирующие _{инструкции P0} :

Пример: INC (r _база , индекс); эффективный адрес будет [r _base ] + индекс, где натуральное число «индекс» получается из самой инструкции конечного автомата.

Хартманис (1971)

К 1971 году Хартманис упростил индексацию до косвенной для использования в своей модели RASP.

Косвенная адресация: регистр-указатель предоставляет конечному автомату адрес целевого регистра, необходимый для выполнения инструкции. Другими словами: содержимое регистра-указателя — это адрес «целевого» регистра, который будет использоваться инструкцией. Если регистр-указатель неограничен, ОЗУ и подходящий RASP, построенный на его шасси, будут эквивалентны по Тьюрингу. Целевой регистр может служить либо регистром источника, либо регистром назначения, как указано в инструкции.

Обратите внимание, что конечный автомат не должен явно указывать адрес этого целевого регистра. Он просто говорит остальной части машины: получите мне содержимое регистра, на который указывает мой регистр-указатель, а затем выполните с ним xyz. Он должен явно указать по имени, через свою команду, этот регистр-указатель (например, «N», или «72», или «PC» и т. д.), но ему не обязательно знать, какое число на самом деле содержит регистр-указатель ( возможно, 279 431).

ОЗУ

Кук и Рекхау (1973) цитируйте Хартманиса (1971) и упростить свою модель до того, что они называют машиной с произвольным доступом (ОЗУ — т. е. машиной с косвенностью и гарвардской архитектурой). В каком-то смысле мы вернулись к Мельзаку (1961). но с гораздо более простой моделью, чем модель Мелзака.

Приоритет

Мински работал в Лаборатории Линкольна Массачусетского технологического института и опубликовал там свою работу; его статья была получена для публикации в « Анналах математики» 15 августа 1960 года, но опубликована только в ноябре 1961 года. Хотя поступление произошло на целый год раньше работы Мельзака. и Ламбек был получен и опубликован (получены соответственно в мае и 15 июня 1961 г. и опубликованы одновременно в сентябре 1961 г.). Что (i) оба были канадцами и опубликованы в Canadian Mathematical Bulletin , (ii) ни один из них не имел ссылки на работу Мински, поскольку она еще не была опубликована в рецензируемом журнале, но (iii) Мельзак ссылается на Ванга, а Ламбек ссылается на него. Мельзака, заставляет предположить, что их работа происходила одновременно и независимо.

Почти то же самое произошло с Шепердсоном и Стерджисом. Их статья была получена в декабре 1961 года — всего через несколько месяцев после того, как была получена работа Мельзака и Ламбека. Опять же, у них было мало (максимум 1 месяц) или вообще не было никакой пользы от рассмотрения работы Мински. Они внимательно отметили в сносках, что статьи Ершова, Кейп-жеребец и Питер «недавно появился» Они были опубликованы гораздо раньше, но появились в немецких журналах на немецком языке, поэтому возникают проблемы с доступностью.

Последняя статья Шепердсона и Стерджиса не публиковалась в рецензируемом журнале до 1963 года. И как они отмечают в Приложении А, «системы» Капенгста (1959), Ершов (1958), Питер (1958) все настолько похожи на результаты, которые были получены позже, что их невозможно отличить от следующего:

производить 0 т.е. 0 → n

увеличить число, т.е. n+1 → n

«т.е. выполнения операций, которые генерируют натуральные числа»

скопируйте число, т.е. n → m

«изменить ход вычислений», сравнивая два числа или уменьшая их до 0.

Действительно, Шеферсон и Стерджис заключают

«Различные минимальные системы очень похожи»

По дате публикации работа Капенгста (1959 г.): Ершов (1958), Петер (1958) были первыми.

См. также

• Счетчик машина
  • Модель противомашины
• Указательная машина
• Машина произвольного доступа
• Машина с произвольным доступом к хранимой программе
• Машина Тьюринга
  • Универсальная машина Тьюринга
  • Галерея машин Тьюринга
  • Примеры машины Тьюринга
• Ван Б-машина
• Машина Пост-Тьюринга - описание и примеры
• Алгоритм
  • Характеристики алгоритма
• Проблема с остановкой
• Занятой бобер
• Штабелируемая машина
• Бумажный компьютер WDR

Библиография

Справочные тексты: Следующая библиография исходных документов включает ряд текстов, которые можно использовать в качестве справочных. Математику, которая привела к шквалу статей об абстрактных машинах в 1950-х и 1960-х годах, можно найти у ван Хейеноорта (1967). - собрание оригинальных документов Фреге за 50 лет (1879 г.) Гёделю (1931). Дэвис (редактор) Неразрешимое (1965) несет факел вперед, начиная с Гёделя (1931). через постскриптум Гёделя (1964); оригинальные статьи Алана Тьюринга (1936 г.) –1937) и Эмиль Пост (1936) включены в «Неразрешимое» . Математика Чёрча, Россера и Клини, представленная в виде переизданий оригинальных статей в «Неразрешимом», развивается дальше в Клини (1952): обязательный текст для всех, кто стремится к более глубокому пониманию математики, лежащей в основе машин. Обе Клини (1952) и Дэвис (1958) на них ссылаются в ряде статей.

Подробное описание счетной машины см. Мински (1967), глава 11 «Модели, подобные цифровым компьютерам» - он называет счетную машину «программным компьютером». Недавний обзор можно найти у ван Эмде Боаса (1990). Недавнее обращение с Минским (1961) / Ламбек (1961) модель можно найти Булос-Берджесс-Джеффри (2002); они перевоплощают «модель счетов» Ламбека, чтобы продемонстрировать эквивалентность машин Тьюринга и частично рекурсивных функций, а также обеспечивают на уровне выпускников введение как в абстрактные модели машин (контр- и Тьюринг-), так и в математику теории рекурсии. Начиная с первого издания Булоса-Берджесса (1970). эта модель появилась практически с такой же обработкой.

Газеты : Газеты начинаются с Ванга (1957). и его резкое упрощение машины Тьюринга. Тьюринг (1936), Клини (1952), Дэвис (1958) и в частности Пост (1936) цитируются у Ванга (1957); в свою очередь, на Вана ссылается Мельзак (1961), Минский (1961) и Шепердсон-Стерджис (1961–1963) поскольку они самостоятельно сводят ленты Тьюринга к «счетчикам». Мельзак (1961) снабжает свою модель счетчика камней «камешки в отверстиях» косвенным подходом, но не развивает дальнейшее рассмотрение. Работа Элгота-Робинсона (1964). определили RASP — компьютероподобные машины с произвольным доступом и хранимыми программами — и, похоже, первыми исследовали неспособность машины с ограниченным счетчиком вычислить мю-рекурсивные функции. Эта неудача — за исключением драконовского использования чисел Гёделя в манере Мински (1961). - приводит к определению «индексированных» инструкций (т. е. косвенной адресации) для их модели RASP. Элгот-Робинсон (1964) и тем более Хартманис (1971) исследовать RASP с помощью самомодифицирующихся программ. Хартманис (1971) определяет набор команд с косвенным обращением, цитируя конспекты лекций Кука (1970). Для использования в исследованиях вычислительной сложности Кук и его аспирант Рекхау (1973). дайте определение RAM (их модель и мнемоническое соглашение аналогичны модели Мелзака, но в статье он не упоминается). Указательные машины являются ответвлением Кнута (1968, 1973) и независимо Шенхаге (1980).

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

Все тексты и документы, за исключением четырех звезд, были засвидетельствованы. Эти четыре написаны на немецком языке и упоминаются в книге Шепердсона-Стерджиса (1963). и Элгот-Робинсон (1964); Шепердсон-Стерджис (1963) предложите краткое обсуждение своих результатов в Приложении А Шепердсона-Стерджиса. Терминология по крайней мере одной статьи (Кафенгст (1959) кажется, возвращает нас к Берку-Голдстайну-фон Нейману (1946–1947). анализ архитектуры компьютера.

Автор	Год	Ссылка	Машина Тьюринга	Счетчик машина	БАРАН	РАСП	Указательная машина	Косвенная адресация	Самомодифицирующаяся программа
Голдстайн и фон Нейман	1947
Клини	1952
Гермес	1954–1955			?
Ван	1957			намеки				намеки
Питер	1958			?
Дэвис	1958
Ершов	1959			?
Кейп-жеребец	1959			?
Мелкс	1961								намеки
Ламбек	1961
Минский	1961
Шепердсон и Стерджис	1963							намеки
Элгот и Робинсон	1964
Дэвис- Неразрешимо	1965
Ван Хейеноорт	1967
Минский	1967				намеки			намеки
Кнут	1968, 1973
Хартман	1971
Кук и Рекхау	1973
Шенхаге	1980
от Эмде Боас	1990
Булос и Берджесс; Булос, Берджесс и Джеффри	1970 –2002

Дальнейшее чтение

• Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media, Inc., стр. 97–102 . ISBN  1-57955-008-8 .

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

• Вайсштейн, Эрик В. «Регистрационная машина» . Математический мир .
• Игблан - Машины Минского Регистра