Счетчик машина является абстрактная машина используется в формальной логики и теоретической информатики для модельных расчетов . Это самый примитивный из четырех типов регистровых машин . Счетчик состоит из одного или нескольких неограниченных регистров., каждый из которых может содержать одно неотрицательное целое число и список (обычно последовательных) арифметических и управляющих инструкций, которым должна следовать машина. Счетчик обычно используется в процессе разработки параллельных алгоритмов в соответствии с принципом взаимного исключения. При использовании таким образом счетчик используется для моделирования дискретных временных шагов вычислительной системы по отношению к доступам к памяти. Путем моделирования вычислений по отношению к доступам к памяти для каждого соответствующего вычислительного шага могут быть разработаны параллельные алгоритмы, чтобы избежать блокировки, одновременной операции записи двумя (или более) потоками по одному и тому же адресу памяти.
Основные характеристики
Для данной модели счетчика набор инструкций крошечный - от одной до шести или семи инструкций. Большинство моделей содержат несколько арифметических операций и хотя бы одну условную операцию (если условие истинно, то переход). Три базовые модели , каждая из которых использует три инструкции, взяты из следующей коллекции. (Аббревиатуры произвольные.)
- CLR (r): регистр CLeaR r . (Установите r на ноль.)
- INC (r): Увеличивает содержимое регистра r .
- DEC (r): очистить содержимое регистра r .
- CPY (r j , r k ): скопируйте содержимое регистра r j в регистр r k, оставив содержимое r j нетронутым.
- JZ (r, z): ЕСЛИ регистр r содержит ноль THEN Перейти к инструкции z ELSE, продолжить по порядку.
- JE (r j , r k , z): ЕСЛИ содержимое регистра r j равно содержимому регистра r k THEN Перейти к инструкции z ELSE продолжить по порядку.
Вдобавок у машины обычно есть инструкция HALT, которая останавливает машину (обычно после вычисления результата).
Используя приведенные выше инструкции, различные авторы обсуждали определенные счетные машины:
- набор 1: {INC (r), DEC (r), JZ (r, z)}, (Minsky (1961, 1967), Lambek (1961))
- набор 2: {CLR (r), INC (r), JE (r j , r k , z)}, (Ершов (1958), Питер (1958) в интерпретации Шепердсона-Стерджиса (1964); Мински (1967) ; Шёнхаге (1980))
- набор 3: {INC (r), CPY (r j , r k ), JE (r j , r k , z)}, (Элгот-Робинсон (1964), Мински (1967))
Три базовых модели счетных машин имеют одинаковую вычислительную мощность, поскольку инструкции одной модели могут быть получены из инструкций другой. Все они эквивалентны вычислительной мощности машин Тьюринга . Из-за своего унарного стиля обработки счетные машины обычно экспоненциально медленнее, чем сопоставимые машины Тьюринга.
Альтернативные названия, альтернативные модели
Модели счетных машин имеют ряд различных названий, которые могут помочь отличить их по особенностям. Далее инструкция «JZDEC (r)» представляет собой составную инструкцию, которая проверяет, пуст ли регистр r; если да, то переходите к инструкции I z , иначе, если нет, то DECrement содержимое r:
- Машина Шепердсона – Стерджиса , потому что эти авторы формально изложили свою модель в легкодоступной экспозиции (1963). Использует набор инструкций (1), дополненный дополнительными удобными инструкциями (JNZ - это «Перейти, если не ноль, используется вместо JZ):
- {INC (r), DEC (r), CLR (r), CPY (r j , r k ), JNZ (r, z), J (z)}
- Машина Мински , потому что Марвин Мински (1961) формализовал модель. Обычно используется набор инструкций (1), но выполнение инструкций не является последовательным по умолчанию, поэтому появляется дополнительный параметр 'z' для указания следующей инструкции после INC и в качестве альтернативы в JZDEC:
- {INC (r, z), JZDEC (r, z true , z false )}
- Программная машина , программный компьютер - имена, которые Мински (1967) дал модели, потому что, как и компьютер, его инструкции выполняются последовательно, если условный переход не был успешным. Использует (обычно) набор инструкций (1), но может быть расширен аналогично модели Шеферсона-Стерджиса. JZDEC часто разделяют:
- {INC (r), DEC (r), JZ (r, z true )}
- Машина Abacus - название, которое Ламбек (1961) дал своему упрощению модели Мелзака (1961), и то, что Булос-Берджесс-Джеффри (2002) называет. Использует набор инструкций (1), но с дополнительным параметром z для указания следующей инструкции в манере модели Мински (1961);
- {INC (r, z), JZDEC (r, z true , z false )}
- Машина Ламбека, альтернативное название, которое Булос-Берджесс-Джеффри (2002) дал машине для счётов. Использует набор инструкций (1-уменьшенный) с дополнительным параметром для указания следующей инструкции:
- {INC (r, z), JZDEC (r, z true , z false )}
- Машина-преемник , потому что она использует «операцию преемника» и очень похожа на аксиомы Пеано. Используется в качестве основы для последующей модели RAM . Использует набор команд (2), например, Шёнхаге, в качестве основы для своих моделей RAM0 и RAM1, которые приводят к его модели SMM указательной машины , также кратко обсуждаемой в van Emde Boas (1990):
- {CLR (r), INC (r), JE (r j , r k , z)}
- Модель Элгот-Робинсона , использованная для определения их модели RASP (1964). Эта модель требует в начале одного пустого регистра (например, [r0] = 0). (Они дополнили ту же модель косвенной адресацией, используя дополнительный регистр, который будет использоваться в качестве «индексного» регистра.)
- {INC (r), CPY (r s , r d ), JE (r j , r k , z)}
- Другие счетные машины : Minsky (1967) демонстрирует, как построить три базовые модели (программа / Minsky / Lambek-abacus, преемник и Элгот-Робинсон) из расширенного набора доступных инструкций, описанных в первом абзаце этой статьи. Модель Мелзака (1961) сильно отличается от вышеупомянутой, потому что она включает в себя «сложение» и «вычитание», а не «приращение» и «уменьшение». Доказательства Мински (1961, 1967), что одного регистра будет достаточно для эквивалентности по Тьюрингу, требуют двух инструкций {MULtiply k и DIV k} для кодирования и декодирования числа Гёделя в регистре, представляющем вычисление. Мински показывает, что если доступны два или более регистра, то более простые INC, DEC и т. Д. Являются адекватными (но число Гёделя по-прежнему требуется для демонстрации эквивалентности по Тьюрингу ; также продемонстрировано в Elgot-Robinson 1964).
Формальное определение
Счетчик состоит из:
- Помеченные неограниченные целочисленные регистры : конечный (или бесконечный в некоторых моделях) набор регистров r 0 ... r n, каждый из которых может содержать любое единственное неотрицательное целое число (0, 1, 2, ... - т.е. неограниченное ). Регистры выполняют свою собственную арифметику; может быть или не быть один или несколько специальных регистров, например, «аккумулятор» ( подробнее об этом см. Машина с произвольным доступом ).
- Государственный реестр , который хранит / идентифицирует текущая команда должна быть выполнена. Этот регистр ограничен и отделен от регистров выше; таким образом, модель счетчика является примером архитектуры Гарварда.
- Список помеченных последовательных инструкций : Конечный список инструкций I 0 ... I m . Хранилище программ (инструкции конечного автомата ) не находится в том же физическом «пространстве», что и регистры. Обычно, но не всегда, как в компьютерных программах, инструкции перечислены в последовательном порядке; если прыжок не был успешным, последовательность по умолчанию продолжается в числовом порядке. Все инструкции в списке взяты из (очень) небольшого набора, но этот набор не включает косвенное обращение. Исторически сложилось так, что большинство моделей черпали свои инструкции из этого набора:
- {Увеличение (г), Уменьшение (г), Очистить (г); Копировать (r j , r k ), условный переход, если содержимое r = 0, условный переход, если r j = r k , безусловный переход, HALT}
- Некоторые модели либо дополнительно разделили некоторые из вышеперечисленных на инструкции без параметров, либо объединили их в одну инструкцию, такую как «Decrement», которой предшествует условный переход при нулевом значении «JZ (r, z)». Распыление инструкций или включение вспомогательных инструкций не приводит к изменению концептуальной мощи, поскольку любую программу в одном варианте можно напрямую транслировать в другой.
- Альтернативные наборы команд обсуждаются в дополнительных моделях регистровых машин .
Пример: КОПИРОВАТЬ счетчик из регистра №2 в №3.
В этом примере показано, как создать еще три полезных инструкции: очистить , безусловный переход и скопировать .
- CLR (j): очистить содержимое регистра r j до нуля.
- J (z): Безоговорочный переход к инструкции I z .
- CPY (s, d): скопируйте содержимое регистра источника r s в регистр назначения r d . (См. Компьютер с одним набором инструкций # Архитектура, запускаемая транспортом )
После этого r s будет содержать исходный счетчик (в отличие от MOVE, который очищает исходный регистр, т. Е. Очищает его до нуля).
Базовый набор (1) используется, как определено здесь:
Инструкция | Влияние на регистр "j" | Влияние на регистр счетчика команд ICR | Резюме |
---|---|---|---|
INC (j) | [j] +1 → j | [IC] +1 → IC | Увеличить содержимое регистра j; следующая инструкция |
DEC (j) | [j] -1 → j | [IC] +1 → IC | Уменьшить содержимое регистра j; следующая инструкция |
JZ (j, z) | ЕСЛИ [j] = 0, ТО I z → IC ELSE [IC] +1 → IC | Если содержимое регистра j = 0, то инструкция z иначе следующая инструкция | |
HALT |
Первоначальные условия
Первоначально регистр №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) p. 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}
- Определите «CoPY (r j , r k )» при сохранении содержимого r j в терминах выше:
- {CPY, CLR, J, DEC, INC, JZ, H}
- Выше приведен набор инструкций Шепердсона-Стерджиса (1963).
- Определите «ADD (r j , r k , r i )» (возможно, с сохранением содержимого r j и r k ), используя приведенное выше:
- {ADD, CPY, CLR, J, DEC, INC, JZ, H}
- Определите "MULtiply (r j , r k , r i )" (MUL) (возможно, с сохранением содержимого r j , r k ) в терминах вышеизложенного:
- {MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H}
- Определите "EXPonential (r j , r k , r i )" (EXP) (возможно, с сохранением содержимого r j , r k ) в терминах вышеизложенного,
- {EXP, MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H}
В общем, мы можем построить любую частичную или полную примитивную рекурсивную функцию , какую захотим, используя те же методы. Действительно, Мински (1967), Шепердсон-Стерджис (1963) и Булос-Берджесс-Джеффри (2002) демонстрируют, как сформировать пять примитивных «операторов» рекурсивных функций (1-5 ниже) из базового набора (1).
Но как насчет полной эквивалентности Тьюринга ? Нам нужно добавить шестой оператор - оператор μ - чтобы получить полную эквивалентность, способную создавать полную и частичную рекурсивные функции :
- Нулевая функция (или постоянная функция)
- Функция преемника
- Функция идентичности
- Функция композиции
- Примитивная рекурсия (индукция)
- Оператор μ ( оператор неограниченного поиска)
Авторы показывают, что это легко сделать в рамках любого из доступных базовых наборов (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 to r d ); [r 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 true , z false )}.
Шаг 1. Машину Тьюринга можно смоделировать двумя стеками.
Машина Тьюринга состоит из конечного автомата и бесконечной ленты, изначально заполненной нулями, на которую машина может записывать единицы и нули. В любой момент головка чтения / записи машины указывает на одну ячейку на ленте. На этом этапе ленту можно концептуально разрезать пополам. Каждую половину ленты можно рассматривать как стопку , где верхняя часть - это ячейка, ближайшая к головке чтения / записи, а нижняя часть находится на некотором расстоянии от головки, со всеми нулями на ленте за нижним краем. Соответственно, машину Тьюринга можно смоделировать с помощью конечного автомата плюс два стека. Перемещение головы влево или вправо равносильно тому, чтобы вытащить немного из одной стопки и надвинуть ее на другую. Запись эквивалентна изменению бита перед его нажатием.
Шаг 2: Стек можно смоделировать двумя счетчиками.
Стек, содержащий нули и единицы, может быть смоделирован двумя счетчиками, когда биты в стеке рассматриваются как представляющие двоичное число (самый верхний бит в стеке является младшим значащим битом). Помещение нуля в стек эквивалентно удвоению числа. Нажатие единицы эквивалентно удвоению и добавлению 1. Выталкивание эквивалентно делению на 2, где остаток - это бит, который был вытянут. Два счетчика могут моделировать этот стек, в котором один из счетчиков содержит число, двоичное представление которого представляет биты в стеке, а другой счетчик используется как блокнот. Чтобы удвоить число в первом счетчике, конечный автомат может инициализировать второй счетчик до нуля, затем несколько раз уменьшить первый счетчик один раз и увеличить второй счетчик дважды. Это продолжается до тех пор, пока первый счетчик не достигнет нуля. В этот момент второй счетчик будет содержать удвоенное число. Деление вдвое выполняется путем уменьшения одного счетчика дважды и увеличения другого один раз и повторения этого действия до тех пор, пока первый счетчик не достигнет нуля. Остаток может быть определен по тому, достиг ли он нуля после четного или нечетного количества шагов, где четность количества шагов кодируется в состоянии конечного автомата.
Шаг 3: Четыре счетчика можно смоделировать двумя счетчиками.
Как и прежде, один из счетчиков используется как блокнот. Другой содержит целое число , разложение на простые множители которого равно 2 a 3 b 5 c 7 d . Показатели a , b , c и d можно представить как четыре виртуальных счетчика, которые упаковываются (с помощью нумерации Гёделя ) в один реальный счетчик. Если реальный счетчик установлен на ноль, а затем увеличивается на единицу, что эквивалентно установке всех виртуальных счетчиков на ноль. Если реальный счетчик удваивается, это эквивалентно увеличению a , а если оно уменьшается вдвое, это эквивалентно уменьшению a . Аналогичным образом его можно умножить или разделить на 3, что эквивалентно увеличению или уменьшению b . Точно так же c и d можно увеличивать или уменьшать. Чтобы проверить, равен ли виртуальный счетчик, такой как c , нулю, просто разделите реальный счетчик на 5, посмотрите, каков остаток, затем умножьте на 5 и сложите остаток. Таким образом, реальный счетчик остается неизменным. Остаток был бы ненулевым тогда и только тогда, когда c был равен нулю.
В результате автомат с двумя счетчиками может моделировать четыре счетчика, которые, в свою очередь, моделируют два стека, моделирующих машину Тьюринга. Следовательно, автомат плюс два счетчика по крайней мере так же мощен, как машина Тьюринга. Машина Тьюринга может легко моделировать конечный автомат с двумя счетчиками, поэтому две машины имеют эквивалентную мощность.
Предостережение: * Если * его счетчики инициализированы на N и 0, то 2CM не может рассчитать 2 N
Этот результат вместе со списком других функций N , которые не могут быть вычислены машиной с двумя счетчиками - при инициализации N в одном счетчике и 0 в другом - например, N 2 , sqrt ( N ), log 2 ( N ) и т. д., появляется в статье Шрёппеля (1972). Результат неудивителен, потому что модель машины с двумя счетчиками была доказана (Мински) как универсальная только тогда, когда аргумент N соответствующим образом закодирован (посредством геделизации) для моделирования машины Тьюринга, начальная лента которой содержит N, закодированное в унарном порядке; кроме того, аналогичным образом будет закодирован выходной сигнал машины с двумя счетчиками. Это явление типично для очень маленьких вычислительных баз, универсальность которых доказывается только моделированием (например, множество тарпитов Тьюринга , самые маленькие из известных универсальных машин Тьюринга и т. Д.).
Доказательству предшествуют несколько интересных теорем:
- «Теорема: машина с тремя счетчиками может моделировать машину Тьюринга» (стр. 2, также см. Мински 1967: 170-174)
- "Теорема: 3CM [машина с тремя счетчиками] может вычислить любую частично рекурсивную функцию одной переменной. Она начинается с аргумента [например, N ] в счетчике и (если он останавливается) оставляет ответ [например, F ( N )] в счетчике ". (стр. 3)
- «Теорема: счетную машину можно смоделировать с помощью 2CM [машины с двумя счетчиками], при условии, что для входа и выхода будет принята нечеткая кодировка» [стр. 3; "непонятная кодировка": 2 W 3 X 5 Y 7 Z, где смоделированные счетчики - W, X, Y, Z]
- «Теорема: любую счетную машину можно смоделировать с помощью 2CM, при условии, что для ввода и вывода допускается неясная кодировка». (стр. 3)
- «Следствие: проблема остановки для 2CM неразрешима.
- «Следствие: 2CM может вычислить любую частично рекурсивную функцию одного аргумента, при условии, что вход закодирован как 2 N, а выход (если машина останавливается) закодирован как 2 ответа ». (стр. 3)
- «Теорема: не существует машины с двумя счетчиками, которая вычисляет 2 N [если один счетчик инициализируется значением N ]». (стр.11)
Что касается второй теоремы о том, что «3CM может вычислить любую частично рекурсивную функцию», автор ставит перед читателем «сложную задачу: умножить два числа, используя только три счетчика» (стр. 2). Основное доказательство включает представление о том, что машины с двумя счетчиками не могут вычислять арифметические последовательности с нелинейными темпами роста (стр. 15), то есть «функция 2 X растет быстрее, чем любая арифметическая прогрессия». (стр.11).
Практический пример расчета счетом
В калькуляторе Friden EC-130 как таковой логики сумматора не было. Его логика была в высшей степени последовательной, арифметические действия выполнялись путем счета. Внутренне десятичные цифры были основаны на основании 1 - например, шестерка была представлена шестью последовательными импульсами в пределах временного интервала, выделенного для этой цифры. Каждый временной интервал содержит одну цифру, сначала наименее значащую. Carries устанавливает триггер, в результате которого к цифре в следующем временном интервале добавляется один счетчик.
Добавление производилось счетчиком вверх, а вычитание - счетчиком вниз по аналогичной схеме для работы с займами.
Схема временных интервалов определяла шесть регистров по 13 десятичных цифр, каждый со знаковым битом. Умножение и деление производились в основном путем повторного сложения и вычитания. Версия с квадратным корнем, EC-132, эффективно вычитала последовательные нечетные целые числа, причем каждое уменьшение требовало двух последовательных вычитаний. После первого, уменьшаемое увеличивалось на единицу перед вторым вычитанием.
Смотрите также
Рекомендации
- Джордж Булос , Джон П. Берджесс , Ричард Джеффри (2002), Вычислимость и логика: четвертое издание , Cambridge University Press, Кембридж, Англия. Первоначальный текст Булоса-Джеффри был тщательно отредактирован Берджессом: он был более продвинутым, чем вводный учебник. Модель "Abacus machine" подробно описана в главе 5 " Вычислимость Abacus" ; это одна из трех моделей, которые тщательно изучаются и сравниваются - машина Тьюринга (все еще в исходной четырехкортежной форме Boolos) и две другие рекурсивные модели.
- Артур Беркс , Герман Голдстайн , Джон фон Нейман (1946), Предварительное обсуждение логической конструкции электронного вычислительного инструмента , перепечатано с. 92ff в Гордоне Белле и Аллене Ньюэлле (1971), Компьютерные структуры: чтения и примеры , mcGraw-Hill Book Компания, Нью-Йорк. ISBN 0-07-004357-4 .
- Стивен А. Кук и Роберт А. Рекхоу (1972), Машины с произвольным доступом с ограничением по времени , Journal of Computer Systems Science 7 (1973), 354–375.
- Мартин Дэвис (1958), « Вычислимость и неразрешимость» , McGraw-Hill Book Company, Inc., Нью-Йорк.
- Кальвин Элгот и Абрахам Робинсон (1964), Машины с хранимыми программами с произвольным доступом, подход к языкам программирования , Журнал Ассоциации вычислительной техники, Vol. 11, № 4 (октябрь 1964 г.), стр. 365–399.
- Фишер, Патрик К .; Мейер, АР ; Розенберг, Арнольд Л. (1968), "Счетчик машины и языки счетчик", Математическая теория систем , 2 : 265-283, DOI : 10.1007 / bf01694011 , MR 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)« Введение в метаматематику » .
- ZA Melzak (1961, получено 15 мая 1961 г.), Неформальный арифметический подход к вычислимости и вычислениям , Canadian Mathematical Bulletin, vol. 4, вып. 3. Сентябрь 1961 г., стр. 279–293. Мелзак не дает никаких ссылок, но признает «пользу разговоров с докторами Р. Хэммингом, Д. Макилроем и В. Виссотсом из телефонных лабораторий Bell и с доктором Х. Вангом из Оксфордского университета».
- Марвин Мински (1961 г., получен 15 августа 1960 г.). "Рекурсивная неразрешимость проблемы Поста" тега "и других тем теории машин Тьюринга". Анналы математики . Анналы математики. 74 (3): 437–455. DOI : 10.2307 / 1970290 . JSTOR 1970290 . Проверить значения даты в:
|date=
( помощь ) - Марвин Мински (1967). Вычисление: конечные и бесконечные машины (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc.В частности, см. Главу 11: Модели, подобные цифровым компьютерам, и главу 14: Очень простые основы вычислимости . В предыдущей главе он дает определение «Программные машины», а в более поздней главе он обсуждает «Универсальные программные машины с двумя регистрами» и «... с одним регистром» и т. Д.
- Джон С. Шепердсон и Х. Э. Стерджис (1961) получили в декабре 1961 г. « Вычислимость рекурсивных функций» , Journal of the Association of Computing Machinery (JACM) 10: 217-255, 1963. Чрезвычайно ценный справочный документ. В своем Приложении А авторы цитируют еще 4 со ссылкой на «Минимум инструкций, используемых в 4.1: Сравнение с аналогичными системами».
- Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine ' , Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik: 5 (1959), 366-379.
- Ершов А.П. Об операторных алгоритмах // Докл. Акад. НАУК, 122 (1958), 967–970. Английский перевод, Автомат. Экспресс 1 (1959), 20-23.
- Петер, Rózsa Graphschemata und rekursive Funktionen , Dialectica 12 (1958), 373.
- Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semesterberichte (Göttingen) 4 (1954), 42–53.
- A. Schnhage (1980), Машины для модификации памяти , Общество промышленной и прикладной математики, SIAM J. Comput. Vol. 9, No. 3, август 1980 г. В котором Шенхаге показывает эквивалентность своего SMM «преемнику RAM» (машина произвольного доступа) и т. Д.
- Рич Шроппель , май 1972 г., «Машина с двумя счетчиками не может вычислить 2 N », Массачусетский технологический институт, лаборатория искусственного интеллекта, памятка по искусственному интеллекту № 257. Автор ссылается на Мински 1967 и отмечает, что « Фрэнсис Яо независимо доказала невычислимость, используя аналогичный метод в апреле 1971 года».
- Питер ван Эмде Боас , Machine Models and Simulations, стр. 3–66, появляется в:
- Ян ван Леувен , изд. "Справочник по теоретической информатике. Том A: Алгоритмы и сложность" , MIT PRESS / Elsevier, 1990. ISBN 0-444-88071-2 (том A). QA 76.H279 1990.
- Трактовка СММ ван Эмде Боасом приводится на стр. 32-35. Это лечение проясняет Schnhage 1980 - оно близко следует, но немного расширяет лечение Schnhage. Обе ссылки могут потребоваться для эффективного понимания.
- Хао Ван (1957), вариант теории вычислительных машин Тьюринга, JACM (Журнал Ассоциации вычислительной техники) 4; 63–92. Представлено на заседании Ассоциации 23–25 июня 1954 г.
- [1]
Внешние ссылки
- Вайсштейн, Эрик В. «Регистрационная машина» . MathWorld .
- Игблан - Машины Регистра Минского
- ^ [1]