Счетчик машины - Counter machine

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

Основные характеристики

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

• CLR (r): регистр CLeaR р. (Набор р до нуля.)
• INC (r): Увеличить содержимое регистра р.
• DEC (r): Очистить содержимое регистра р.
• CPY (r_j, р_k): Скопируйте содержимое регистра р_j зарегистрироваться р_k оставив содержимое р_j неповрежденный.
• JZ (r, z): регистр IF р содержит Zero THEN Перейти к инструкции z ИНАЧЕ продолжайте последовательно.
• JE (r_j, р_k, z): ЕСЛИ содержимое регистра р_j Равно содержимому регистра р_k ТОГДА Перейти к инструкции z ИНАЧЕ продолжайте последовательно.

Вдобавок машина обычно имеет инструкцию HALT, которая останавливает машину (обычно после вычисления результата).

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

• набор 1: {INC (r), DEC (r), JZ (r, z)}, (Минский (1961, 1967), Ламбек (1961))
• набор 2: {CLR (r), INC (r), JE (r_j, р_k, z)}, (Ершов (1958), Питер (1958) в интерпретации Шепердсона-Стерджиса (1964); Мински (1967); Шёнхаге (1980))
• набор 3: {INC (r), CPY (r_j, р_k), JE (r_j, р_k, z)}, (Элгот-Робинсон (1964), Мински (1967))

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

Альтернативные названия, альтернативные модели

В счетчик машина Модели имеют несколько разных названий, которые могут помочь отличить их по особенностям. Далее инструкция «JZDEC (r)» представляет собой составную инструкцию, которая проверяет, пуст ли регистр r; если да, то переходите к инструкции I_z, иначе, если нет, то DECreate содержимое r:

• Машина Шепердсона-Стерджиса, потому что эти авторы формально изложили свою модель в легкодоступной экспозиции (1963). Использует набор инструкций (1), дополненный дополнительными удобными инструкциями (JNZ - это «Перейти, если не ноль, используется вместо JZ):

  {INC (r), DEC (r), CLR (r), CPY (r)_j, р_k ), JNZ (r, z), J (z)}

• Машина Минского, потому что Марвин Мински (1961) формализовали модель. Обычно используется набор инструкций (1), но выполнение инструкций не является последовательным по умолчанию, поэтому появляется дополнительный параметр 'z' для указания следующей инструкции после INC и в качестве альтернативы в JZDEC:

  {INC (r, z), JZDEC (r, z_правда, z_ложный) }

• Программная машина, Программный компьютер, имена Мински (1967) дали модели, потому что, как компьютер его инструкции выполняются последовательно, если условный переход не был успешным. Использует (обычно) набор инструкций (1), но может быть дополнен аналогично модели Шеферсона-Стерджиса. JZDEC часто разделяют:

  {INC (r), DEC (r), JZ (r, z_правда )}

• Абак машина, имя, которое Ламбек (1961) дал своему упрощению модели Мелзака (1961), и то, что Булос-Берджесс-Джеффри (2002) называет. Использует набор команд (1), но с дополнительным параметром z, чтобы указать следующую команду в манере модели Мински (1961);

  {INC (r, z), JZDEC (r, z_правда, z_ложный ) }

• Ламбек машина, альтернативное название Булос-Берджесс-Джеффри (2002) дал машине счеты. Использует набор инструкций (1-уменьшенный) с дополнительным параметром для указания следующей инструкции:

  {INC (r, z), JZDEC (r, z_правда, z_ложный ) }

• Преемник машины, потому что он использует «операцию преемника» и очень похож на аксиомы Пеано. Используется как база для преемник RAM модель. Использует набор инструкций (2), например, Шёнхаге в качестве основы для его моделей RAM0 и RAM1, которые привели к его указатель машины Модель SMM, также кратко обсуждаемая в van Emde Boas (1990):

  {CLR (r), INC (r), JE (r_j, р_k, z)}

• Модель Элгот-Робинсона, использованные для определения их модели RASP (1964). Эта модель требует в начале одного пустого регистра (например, [r0] = 0). (Они дополнили ту же модель косвенной адресацией, используя дополнительный регистр, который будет использоваться в качестве «индексного» регистра.)

  {INC (r), CPY (r_s, р_d ), JE (r_j, р_k, z)}

• Другие счетные машины: Minsky (1967) демонстрирует, как построить три базовые модели (программа / Minsky / Lambek-abacus, преемник и Элгот-Робинсон) из расширенного набора доступных инструкций, описанных в первом абзаце этой статьи. Модель Мелзака (1961) сильно отличается от вышеупомянутой, потому что она включает «сложение» и «вычитание», а не «приращение» и «уменьшение». Доказательства Мински (1961, 1967) того, что одного регистра будет достаточно для эквивалентности Тьюринга, требуют двух инструкций {MULtiply k и DIV k} для кодирования и декодирования Число Гёделя в регистре, представляющем вычисление. Мински показывает, что если доступны два или более регистра, то более простые INC, DEC и т. Д. Подходят (но Число Гёделя все еще требуется для демонстрации Эквивалентность Тьюринга; также продемонстрировано в Elgot-Robinson 1964).

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

Счетчик состоит из:

1. Помеченные неограниченные целочисленные регистры: конечный (или бесконечный в некоторых моделях) набор регистров р₀ ... р_п каждое из которых может содержать любое одно неотрицательное целое число (0, 1, 2, ... - т.е. неограниченное). Регистры выполняют свою собственную арифметику; может быть или не быть один или несколько специальных регистров, например «аккумулятор» (см. Машина с произвольным доступом подробнее об этом).
2. А государственный реестр который сохраняет / идентифицирует текущую инструкцию, которая должна быть выполнена. Этот регистр ограничен и отделен от регистров выше; таким образом, модель счетчика является примером Гарвардская архитектура
3. Список помеченных последовательных инструкций: Конечный список инструкций я₀ ... я_м. Магазин программ (инструкция конечный автомат ) не находится в том же физическом «пространстве», что и регистры. Обычно, но не всегда, как компьютерные программы инструкции перечислены в последовательном порядке; если прыжок не был успешным, последовательность по умолчанию продолжается в числовом порядке. Все инструкции в списке взяты из (очень) небольшого набора, но этот набор не включает косвенное обращение. Исторически большинство моделей черпали свои инструкции из этого набора:

{Увеличение (г), Уменьшение (г), Очистить (г); Копировать (r_j,р_k), условный переход, если содержимое r = 0, условный переход, если r_j= г_k, безусловный прыжок, HALT}

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

Альтернативные наборы инструкций обсуждаются в приложении. Регистрационные модели машин.

Пример: КОПИРОВАТЬ счет из регистра №2 в №3

В этом примере показано, как создать еще три полезных инструкции: Чисто, безусловный прыжок, и копировать.

• CLR (j): очистить содержимое регистра р_j до нуля.
• J (z): Безоговорочный переход к инструкции я_z.
• CPY (s, d): копирование содержимого исходного регистра р_s в регистр назначения р_d. Потом р_s будет содержать исходный счетчик (в отличие от MOVE, который очищает исходный регистр, то есть очищает его до нуля).

Базовый набор (1) используется, как определено здесь:

Первоначальные условия

Первоначально регистр №2 содержит «2». Регистры №0, №1 и №3 пусты (содержат «0»). Регистр № 0 остается неизменным во время вычислений, потому что он используется для безусловного перехода. Регистр №1 - это блокнот. Программа начинается с инструкции 1.

Окончательные условия

Программа HALT завершает работу с содержимым регистра # 2 на своем исходном счетчике и содержимым регистра # 3, равным исходному содержимому регистра # 2, т.е.

[2] = [3].

Описание программы на высоком уровне

Программа COPY (# 2, # 3) состоит из двух частей. В первой части программа движется содержимое регистра источника # 2 как в блокноте # 1, так и в регистре назначения # 3; таким образом # 1 и # 3 будут копии друг друга и исходный счетчик в # 2, но # 2 очищается в процессе уменьшения его до нуля. Безусловные переходы J (z) выполняются тестами регистра # 0, который всегда содержит число 0:

[#2] →#3; [#2] →#1; 0 →#2

Во второй части программа движется (возвращает, восстанавливает) содержимое блокнота №1 обратно в №2, очищая блокнот №1 в процессе:

[#1] →#2; 0 →#1

Программа

Программа, выделенная желтым цветом, отображается написанным слева направо в правом верхнем углу.

Ниже показан "запуск" программы. Время бежит вниз по странице. Инструкции желтого цвета, регистры синего цвета. Программа перевернута на 90 градусов, номера инструкций (адреса) расположены вверху, мнемоника инструкций под адресами, а параметры инструкции - под мнемоникой (по одному на ячейку):

Частично рекурсивные функции: построение "удобных инструкций" с использованием рекурсии

В приведенном выше примере показано, как первые базовые инструкции {INC, DEC, JZ} могут создавать еще три инструкции - безусловный переход J, CLR, CPY. В некотором смысле CPY использует как CLR, так и J плюс базовый набор. Если регистр № 3 изначально имел содержимое, сумма содержимого # 2 и # 3 попало бы в # 3. Таким образом, чтобы быть полностью точным, программа CPY должна предшествовать своим ходам с помощью CLR (1) и CLR (3).

Однако мы видим, что СДВ можно было бы легко осуществить. Фактически, ниже приводится краткое изложение того, как примитивные рекурсивные функции такие как ADD, MULtiply и EXPonent могут появиться (см. Boolos-Burgess-Jeffrey (2002), стр. 45-51).

• Начальный набор инструкций: {DEC, INC, JZ, H}
• Определите безусловный "Jump J (z)" в терминах JZ (r0, z), учитывая, что r0 содержит 0.

{J, DEC, INC, JZ, H}

• Определите "CLeaR (r)" в терминах вышеизложенного:

{CLR, J, DEC, INC, JZ, H}

• Определите «Копировать (r_j, р_k ) "при сохранении содержимого r_j с точки зрения вышеизложенного:

{CPY, CLR, J, DEC, INC, JZ, H}

Выше приведен набор инструкций Шепердсона-Стерджиса (1963).

• Определите «ДОБАВИТЬ (r_j, р_k, р_я ) ", (возможно, сохраняя содержимое r_j, а г_k ), используя указанное выше:

{ADD, CPY, CLR, J, DEC, INC, JZ, H}

• Определите "MULtiply (r_j, р_k, р_я ) "(MUL) (возможно, с сохранением содержимого r_j, р_k), с точки зрения вышеизложенного:

{MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H}

• Определите "EXPonential (r_j, р_k, р_я ) "(EXP) (возможно, с сохранением содержимого r_j, р_k ) в терминах вышеизложенного,

{EXP, MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H}

В общем, мы можем построить Любые частичное или полное примитивная рекурсивная функция что мы желаем, используя те же методы. Действительно, Мински (1967), Шепердсон-Стерджис (1963) и Булос-Берджесс-Джеффри (2002) демонстрируют, как сформировать пять примитивная рекурсивная функция «операторы» (1-5 ниже) из базового набора (1).

Но как насчет полного Эквивалентность Тьюринга ? Нам нужно добавить шестой оператор - μ оператор - получить полную эквивалентность, способную создать полную и частичную рекурсивные функции:

1. Нулевая функция (или постоянная функция)
2. Функция преемника
3. Функция идентичности
4. Функция композиции
5. Примитивная рекурсия (индукция)
6. μ оператор (оператор неограниченного поиска)

Авторы показывают, что это легко сделать в рамках любого из доступных базовых наборов (1, 2 или 3) (пример можно найти на μ оператор ). Однако следует предупредить читателя о том, что, хотя оператор μ легко создается базовым набором инструкций, это не означает, что произвольный частичная рекурсивная функция можно легко создать с помощью базовой модели - Эквивалентность Тьюринга и частичные рекурсивные функции подразумевают неограниченный Оператор μ, который может до бесконечности метаться к концам цепочки регистров в поисках своей цели. Проблема в том, что регистры должны вызываться явно по номеру / имени, например. INC (47,528) и DEC (39,347), и на этом ТАБЛИЦА инструкций конечного автомата будет исчерпана. Независимо от того, насколько «велик» конечный автомат, мы можем найти функцию, которая использует «большее» количество регистров.

Проблемы с моделью счетчика машины

Проблемы подробно рассмотрены в статье. Машина с произвольным доступом. Проблемы делятся на два основных класса и третий класс «неудобств»:

(1) Неограниченный возможности регистров по сравнению с ограниченной емкостью инструкций конечного автомата: Каким образом машина будет создавать константы, превышающие возможности ее конечного автомата?

(2) Неограниченный числа регистров по сравнению с ограниченным числом инструкций конечного автомата: Как машина будет обращаться к регистрам с адресными номерами за пределами досягаемости / возможностей ее конечного автомата?

(3) Полностью уменьшенные модели громоздки:

Шепердсон и Стерджис (1963) не извиняются за свой набор из шести инструкций. Они сделали свой выбор, основываясь на «простоте программирования ... а не на экономии» (стр. 219, сноска 1).

Инструкции Шепердсона и Стерджиса ([r] означает «содержимое регистра r»):

• • УВЕЛИЧЕНИЕ (r); [r] +1 → r
  • ЗАКАЗ (r); [г] -1 → г
  • ПРОЗРАЧНЫЙ (r); 0 → г
  • КОПИРОВАТЬ (r_s к г_d ); [р_s] → r_d
  • JUMP-UNCONDITIONAL к инструкции I_z
  • JUMP IF [r] = 0 к инструкции I_z

Минский (1967) расширил свой набор из двух инструкций {INC (z), JZDEC (r, I_z)} в {CLR (r), INC (r), JZDEC (r, I_z), J (I_z)} до его доказательства того, что «универсальная программная машина» может быть построена только с двумя регистрами (стр. 255ff).

Машины с двумя счетчиками эквивалентны Тьюрингу (с оговоркой)

Для каждого Машина Тьюринга, есть 2CM, который имитирует это, учитывая, что вход и выход 2CM правильно закодированы. Это доказано в книге Минского (Вычисление, 1967, с. 255-258), а альтернативное доказательство представлено ниже в три этапа. Во-первых, машину Тьюринга можно смоделировать с помощью конечного автомата (FSM), оснащенного двумя стеками. Затем две стопки можно смоделировать с помощью четырех счетчиков. Наконец, четыре счетчика можно моделировать двумя счетчиками. Машина с двумя счетчиками использует набор инструкций {INC (r, z), JZDEC (r, z_правда, z_ложный) }.

Шаг 1. Машину Тьюринга можно смоделировать двумя стеками.

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

Шаг 2: Стек можно смоделировать двумя счетчиками.

Стек, содержащий нули и единицы, может быть смоделирован двумя счетчиками, когда биты в стеке рассматриваются как представляющие двоичное число (самый верхний бит в стеке является младшим значащим битом). Помещение нуля в стек эквивалентно удвоению числа. Нажатие единицы эквивалентно удвоению и добавлению 1. Поппинг эквивалентно делению на 2, где остаток это бит, который выскочил. Два счетчика могут имитировать этот стек, в котором один из счетчиков содержит число, двоичное представление которого представляет биты в стеке, а другой счетчик используется как блокнот. Чтобы удвоить число в первом счетчике, FSM может инициализировать второй счетчик до нуля, затем несколько раз уменьшить первый счетчик один раз и увеличить второй счетчик дважды. Это продолжается до тех пор, пока первый счетчик не достигнет нуля. В этот момент второй счетчик будет содержать удвоенное число. Деление вдвое выполняется путем уменьшения одного счетчика дважды и увеличения другого один раз и повторения, пока первый счетчик не достигнет нуля. Остаток можно определить по тому, достиг ли он нуля после четного или нечетное число шагов, где четность количества шагов закодирована в состоянии автомата.

Шаг 3: Четыре счетчика можно смоделировать двумя счетчиками.

Как и прежде, один из счетчиков используется как блокнот. Другой держит целое число чья премьер факторизация 2^а3^б5^c7^d. Показатели а, б, c, и d можно представить себе как четыре виртуальных счетчика, которые упаковываются (через Гёделевская нумерация ) в единый реальный счетчик. Если реальный счетчик установлен на ноль, а затем увеличивается на один раз, что эквивалентно установке всех виртуальных счетчиков на ноль. Если реальный счетчик удваивается, это эквивалентно увеличению а, а если его уменьшить вдвое, это эквивалентно уменьшению а. По аналогичной процедуре его можно умножить или разделить на 3, что эквивалентно увеличению или уменьшению б. Так же, c и d можно увеличивать или уменьшать. Чтобы проверить, есть ли виртуальный счетчик, например c равен нулю, просто разделите реальный счетчик на 5, посмотрите, каков остаток, затем умножьте на 5 и прибавьте остаток. При этом реальный счетчик остается неизменным. Остаток будет отличным от нуля тогда и только тогда, когда c было ноль.

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

Предупреждение: * Если * его счетчики инициализируются на N и 0, то 2CM не может вычислить 2^N

Этот результат вместе со списком других функций N которые не рассчитываются машиной с двумя счетчиками - при инициализации с помощью N в одном счетчике и 0 в другом - такие как N², sqrt (N), журнал₂(N) и др., появляется в статье Шрёппеля (1972). Результат неудивителен, потому что модель машины с двумя счетчиками была доказана (Мински) как универсальная только тогда, когда аргумент N соответствующим образом кодируется (посредством геделизации) для моделирования машины Тьюринга, начальная лента которой содержит N закодировано в унарном формате; кроме того, аналогичным образом будет закодирован вывод машины с двумя счетчиками. Это явление типично для очень маленьких вычислительных баз, универсальность которых доказывается только моделированием (например, многие Брезент Тьюринга, самый маленький из известных универсальные машины Тьюринга, так далее.).

Доказательству предшествуют несколько интересных теорем:

• «Теорема: машина с тремя счетчиками может моделировать машину Тьюринга» (стр. 2, также см. Мински 1967: 170-174)
• «Теорема: 3CM [машина с тремя счетчиками] может вычислить любую частично рекурсивную функцию одной переменной. Она начинается с аргумента [т.е. N] в счетчике и (если он останавливается) оставляет ответ [т.е. F (N)] в счетчике »(стр. 3)
• «Теорема: счетчик можно смоделировать с помощью 2CM [машины с двумя счетчиками], при условии, что для входа и выхода будет принята нечеткая кодировка» [стр. 3; "непонятная кодировка": 2^W3^Икс5^Y7^Z где смоделированные счетчики: W, X, Y, Z]
• «Теорема: любую счетную машину можно смоделировать с помощью 2CM, при условии, что для ввода и вывода используется неясная кодировка». (стр. 3)
  • "Следствие: проблема остановки для 2CMs неразрешима.
  • Следствие: 2CM может вычислить любую частично рекурсивную функцию одного аргумента, при условии, что входные данные закодированы как 2^N а вывод (если машина останавливается) кодируется как 2^ответ. "(стр. 3)
• Теорема: не существует машины с двумя счетчиками, которая вычисляет 2^N [если один счетчик инициализирован N]. »(стр. 11)

Что касается второй теоремы о том, что «3CM может вычислить любую частично рекурсивную функцию», автор ставит перед читателем «сложную задачу: умножить два числа, используя только три счетчика» (стр. 2). Основное доказательство связано с представлением о том, что машины с двумя счетчиками не могут вычислять арифметические последовательности с нелинейными темпами роста (стр. 15), то есть «функция 2^Икс растет быстрее, чем любая арифметическая прогрессия »(стр. 11).

Практический пример расчета счетом

В калькуляторе Friden EC-130 как таковой логики сумматора не было. Его логика была в высшей степени последовательной, арифметические действия выполнялись путем счета. Внутренне десятичные цифры были основаны на системе счисления-1 - например, шестерка была представлена ​​шестью последовательными импульсами в пределах временного интервала, выделенного для этой цифры. Каждый временной интервал содержит одну цифру, сначала наименее значащую. Carries устанавливает триггер, в результате которого к цифре в следующем временном интервале добавляется один счетчик.

Добавление производилось счетчиком вверх, а вычитание - счетчиком вниз по аналогичной схеме для работы с займами.

Схема временных интервалов определяла шесть регистров по 13 десятичных цифр, каждый из которых имел знаковый бит. Умножение и деление выполнялись в основном путем повторного сложения и вычитания. Версия с квадратным корнем, EC-132, эффективно вычитала последовательные нечетные целые числа, причем каждое уменьшение требовало двух последовательных вычитаний. После первого, уменьшаемое увеличивалось на единицу перед вторым вычитанием.

Смотрите также

• Счетчик: эталонная модель
• Указатель машины
• Машина Пост-Тьюринга
• Машина с произвольным доступом
• Зарегистрировать машину
• Ван Б-машина

использованная литература

• Джордж Булос, Джон П. Берджесс, Ричард Джеффри (2002), Вычислимость и логика: четвертое изданиеИздательство Кембриджского университета, Кембридж, Англия. Первоначальный текст Булоса-Джеффри был тщательно отредактирован Берджессом: более продвинутый, чем вводный учебник. Модель "Abacus machine" подробно рассматривается в главе 5. Вычислимость Abacus; это одна из трех моделей, которые тщательно изучаются и сравниваются - машина Тьюринга (все еще в исходной четырехкортежной форме Boolos) и две другие рекурсивные модели.
• Артур Беркс, Герман Голдстайн, Джон фон Нейман (1946), Предварительное обсуждение логической конструкции электронного вычислительного прибора., перепечатано с. 92ff в Гордон Белл и Аллен Ньюэлл (1971), Компьютерные структуры: литература и примеры, mcGraw-Hill Book Company, Нью-Йорк. ISBN  0-07-004357-4 .
• Стивен А. Кук и Роберт А. Рекхоу (1972), Машины с ограниченным по времени произвольным доступом, Журнал компьютерных систем науки 7 (1973), 354–375.
• Мартин Дэвис (1958), Вычислимость и неразрешимость, McGraw-Hill Book Company, Inc., Нью-Йорк.
• Кэлвин Элгот и Авраам Робинсон (1964), Машины с хранимыми программами с произвольным доступом, подход к языкам программирования, Журнал Ассоциации вычислительной техники, Vol. 11, № 4 (октябрь 1964 г.), стр. 365–399.
• Фишер, Патрик С.; Мейер, А.; Розенберг, Арнольд Л. (1968), "Счетные машины и счетные языки", Математическая теория систем, 2: 265–283, Дои:10.1007 / bf01694011, Г-Н  0235932. Развивается временная иерархия и пространственная иерархия теоремы для счетных машин, аналогичные иерархиям для машин Тьюринга.
• Дж. Хартманис (1971), "Вычислительная сложность машин, хранимых с произвольным доступом", Математическая теория систем 5, 3 (1971) стр. 232–245.
• Хопкрофт, Джон; Джеффри Уллман (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Месса для чтения: Эддисон-Уэсли. ISBN  0-201-02988-X. Сложная книга, посвященная проблемам машинной интерпретации «языков», NP-полноты и т. Д.
• Стивен Клини (1952), Введение в метаматематику, North-Holland Publishing Company, Амстердам, Нидерланды. ISBN  0-7204-2103-9.
• Дональд Кнут (1968), Искусство программирования, Второе издание 1973 г., Addison-Wesley, Reading, Massachusetts. См. Страницы 462-463, где он определяет «новый вид абстрактной машины или« автомата », который имеет дело со связанными структурами».
• Иоахим Ламбек (1961 г., получено 15 июня 1961 г.), Как программировать бесконечные счеты, Математический вестник, т. 4, вып. 3. Сентябрь 1961 г., стр. 295–302. В своем Приложении II Ламбек предлагает «формальное определение« программы ». Он ссылается на Мелзака (1961) и Клини (1952). Введение в метаматематику.
• З. А. Мельзак (1961 г., получено 15 мая 1961 г.), Неформальный арифметический подход к вычислимости и вычислениям, Канадский математический бюллетень, т. 4, вып. 3. Сентябрь 1961 г., стр. 279–293. Мелзак не дает никаких ссылок, но признает «пользу разговоров с докторами Р. Хэммингом, Д. Макилроем и В. Виссотсом из телефонных лабораторий Bell и с доктором Х. Вангом из Оксфордского университета».
• Марвин Мински (1961 г., получено 15 августа 1960 г.). «Рекурсивная неразрешимость проблемы Поста о« теге »и других тем в теории машин Тьюринга». Анналы математики. Анналы математики. 74 (3): 437–455. Дои:10.2307/1970290. JSTOR  1970290. Проверить значения даты в: | дата = (Помогите)
• Марвин Мински (1967). Вычисления: конечные и бесконечные машины (1-е изд.). Englewood Cliffs, N.J .: Prentice-Hall, Inc. В частности, см. Главу 11: Модели, похожие на цифровые компьютеры и глава 14: Очень простые основы вычислимости. В предыдущей главе он дает определение «Программные машины», а в следующей главе он обсуждает «Универсальные программные машины с двумя регистрами» и «... с одним регистром» и т. Д.
• Джон С. Шепердсон и Х. Э. Стерджис (1961) получен в декабре 1961 г. Вычислимость рекурсивных функций, Journal of the Association of Computing Machinery (JACM) 10: 217-255, 1963. Чрезвычайно ценный справочный документ. В своем Приложении А авторы цитируют еще 4 со ссылкой на «Минимум инструкций, используемых в 4.1: Сравнение с аналогичными системами».
  • Капхенгст, Хайнц, Eine Abstrakte programmgesteuerte Rechenmaschine ', Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik:5 (1959), 366-379.
  • Ершов, А. Об операторных алгоритмах, (Русский) Док. Акад. АН СССР, 122 (1958), 967-970. Английский перевод, Автомат. Экспресс 1 (1959), 20-23.
  • Петер, Рожа Графические схемы и рекурсивные функции, Диалектика 12 (1958), 373.
  • Гермес, Ганс Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semesterberichte (Göttingen) 4 (1954), 42–53.
• А. Schnhage (1980), Машины для модификации хранения, Общество промышленной и прикладной математики, SIAM J. Comput. Vol. 9, No. 3, август 1980 г. В котором Шенхаге показывает эквивалентность своего SMM «преемнику RAM» (машина произвольного доступа) и т. Д.
• Рич Шрёппель, Май 1972 г., "Машина с двумя счетчиками не может вычислить 2"^N", Массачусетский технологический институт, Лаборатория А. И., Записка по искусственному интеллекту № 257. Автор ссылается на Мински 1967 и отмечает, что"Фрэнсис Яо независимо доказал невычислимость аналогичным методом в апреле 1971 г. "
• Питер ван Эмде Боас, Модели машин и симуляции стр. 3–66, появляющиеся в:

Ян ван Леувен, изд. Справочник по теоретической информатике. Том A: Алгоритмы и сложность, MIT PRESS / Elsevier, 1990. ISBN  0-444-88071-2 (том А). QA 76.H279 1990.

Трактовка СММ ван Эмде Боасом приводится на стр. 32-35. Это лечение проясняет Schnhage 1980 - оно близко следует, но немного расширяет лечение Schnhage. Обе ссылки могут потребоваться для эффективного понимания.

• Хао Ван (1957), Вариант теории вычислительных машин Тьюринга, JACM (Журнал Ассоциации вычислительной техники) 4; 63–92. Представлено на заседании Ассоциации 23–25 июня 1954 г.

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

• Вайсштейн, Эрик В. "Зарегистрировать машину". MathWorld.
• Игблан - Машины Регистра Минского