Счетчик машина

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

Счетные машины с тремя счетчиками могут вычислять любую частично рекурсивную функцию одной переменной. Счетные машины с двумя счетчиками являются полными по Тьюрингу : они могут имитировать любую соответствующим образом закодированную машину Тьюринга, но есть некоторые простые функции, которые они не могут вычислить. Счетные машины только с одним счетчиком могут распознавать надлежащее надмножество регулярных языков и подмножество детерминированных контекстно-свободных языков . ^[1]

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

• CLR (r): ОЧИСТИТЬ регистр r . (Установить r в ноль.)
• INC (r): Увеличить содержимое регистра r .
• DEC (r): Уменьшает содержимое регистра r .
• CPY (r _j , r _k ): Копирует содержимое регистра r _j в регистр r _k, оставляя содержимое r _j нетронутым.
• JZ (r, z): ЕСЛИ регистр r содержит ноль, ТО перейти к инструкции z, ИНАЧЕ продолжить последовательность.
• JE (r _j , r _k , z): ЕСЛИ содержимое регистра r _j равно содержимому регистра r _k ТО Перейти к инструкции z ИНАЧЕ продолжить последовательность.

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

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

• набор 1: { INC (r), DEC (r), JZ (r, z) }, (Минский (1961, 1967), Ламбек (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 , иначе, если нет, то выполнить декрементацию содержимого r:

• Машина Шепердсона–Стерджиса , поскольку эти авторы формально изложили свою модель в легкодоступном изложении (1963). Использует набор инструкций (1), дополненный дополнительными удобными инструкциями (JNZ — «Jump if Not Zero», используется вместо 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) дал своему упрощению модели Melzak (1961), и то, что Булос–Берджесс–Джеффри (1974) называют ею. Использует набор инструкций (1), но с дополнительным параметром z для указания следующей инструкции в стиле модели Minsky (1961);

  { INC ( r, z ), JZDEC (r, z _true , z _false ) }

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

  { INC ( r, z ), JZDEC ( r, z _true , z _false ) }

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

  { CLR ( р ), INC ( р ), JE ( р _j , р _k , z ) }

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

  { INC (r), CPY (r _s , r _d ), JE (r _j , r _k , z ) }

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

Счетная машина состоит из:

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

{ Инкремент (r), Уменьшение (r), Очистка (r); Копировать (r _j ,r _k ), условный переход, если содержимое r = 0, условный переход, если r _j =r _k , безусловный переход, ОСТАНОВКА }

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

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

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

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

После этого r _s будет содержать свой исходный счетчик (в отличие от MOVE, который очищает исходный регистр, т.е. обнуляет его).

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

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

Программа останавливается с содержимым регистра №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 было бы возможно, легко. И на самом деле, ниже приводится краткое изложение того, как могут возникнуть примитивные рекурсивные функции, такие как ADD, MULtiply и EXPonent. ^[2]

• Начальный набор инструкций: { DEC, INC, JZ, H }
• Определим безусловный «Прыжок 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 ), используя вышеизложенное:

{ ДОБАВИТЬ, КП, КЛР, J, УБ, ВКЛ, JZ, H }

• Определим «MULtiply ( r _j , r _k , r _i )» (MUL) (возможно, сохраняя содержимое r _j , r _k ) в терминах вышеизложенного:

{ МУЛ, ДОБАВИТЬ, КП, КЛР, J, УБ, ВКЛ, JZ, H }

• Определим «ЭКСПОНЕНТАЛЬ ( r _j , r _k , r _i )» (EXP) (возможно, сохраняя содержимое r _j , r _k ) в терминах вышеизложенного,

{ ЭКСП, УМНОЖ, ДОБАВИТЬ, КОПИРОВАТЬ, КЛР, J, УБВ, ИНК, JZ, H }

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

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

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

Авторы показывают, что это легко сделать в любом из доступных базовых наборов (1, 2 или 3) (пример можно найти в операторе μ ). Это означает, что любая рекурсивная функция mu может быть реализована как счетчиковая машина ^[3], несмотря на конечный набор инструкций и размер программы конструкции счетчиковой машины. Однако требуемая конструкция может быть контринтуитивной, даже для функций, которые относительно легко определить в более сложных регистровых машинах, таких как машина с произвольным доступом . Это связано с тем, что оператор μ может выполнять итерации неограниченное количество раз, но любая заданная счетчиковая машина не может адресовать неограниченное количество различных регистров из-за конечного размера ее списка инструкций.

Например, вышеприведенная иерархия примитивных рекурсивных операторов может быть расширена за пределы возведения в степень в операции со стрелками более высокого порядка в обозначении стрелки вверх Кнута . Для любого фиксированного функция является примитивно рекурсивной и может быть реализована как счетчик-машина простым способом. Но функция не является примитивно рекурсивной. Может возникнуть соблазн реализовать оператор стрелки вверх с помощью конструкции, аналогичной инструкциям преемника, сложения, умножения и возведения в степень выше, путем реализации стека вызовов , чтобы функцию можно было применять рекурсивно к меньшим значениям . Эта идея похожа на то, как можно реализовать функцию на практике во многих языках программирования. Однако счетчик-машина не может использовать неограниченное количество регистров в своих вычислениях, что было бы необходимо для реализации стека вызовов, который может расти произвольно большим. Операция «стрелка вверх» по-прежнему может быть реализована как счетная машина, поскольку она является мю-рекурсивной, однако функция будет реализована путем кодирования неограниченного объема информации внутри конечного числа регистров, например, с использованием нумерации Гёделя .${\displaystyle к}$${\displaystyle Q(x,y)=x\uparrow ^{k}y}$${\displaystyle R(n,x,y)=x\uparrow ^{n}y}$${\displaystyle R}$${\displaystyle n}$

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

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

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

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

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

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

• • ПРИРАЩЕНИЕ (r); [r] +1 → r
  • ДЕКРЕМЕНТ ( r ); [r] -1 → r
  • ОЧИСТИТЬ (r); 0 → r
  • КОПИРОВАТЬ ( r _s to r _d ); [r _s ] → r _d
  • ПЕРЕХОД-БЕЗУСЛОВНЫЙ к инструкции I _z
  • ПЕРЕЙТИ ЕСЛИ [r] =0 к инструкции I _z

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

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

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

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

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

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

Этот результат, вместе со списком других функций от N , которые не вычисляются двухсчетчиковой машиной — при инициализации с N в одном счетчике и 0 в другом — таких как N ² , sqrt( N ), log ₂ ( 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 ^answer ». (стр. 3)
• «Теорема: Не существует машины с двумя счетчиками, которая вычисляет 2 ^N [если один счетчик инициализирован как N ]» (стр. 11)

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

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

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

Сложение производилось с помощью счетчика с прибавлением, а вычитание — с помощью счетчика с вычитанием, при этом использовалась аналогичная схема для обработки заемных средств.

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

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

• Булос, Джордж ; Берджесс, Джон П.; Джеффри , Ричард (2007) [1974]. Вычислимость и логика (5-е изд.). Кембридж, Англия: Cambridge University Press . doi :10.1017/CBO9780511804076. ISBN 9780521877527.Оригинальный текст Булоса–Джеффри был значительно переработан Берджессом: он стал более продвинутым, чем вводный учебник. Модель «машины Абак» подробно описана в Главе 5 «Вычислимость Абак» ; это одна из трех моделей, которые были подробно рассмотрены и сравнены — машина Тьюринга (все еще в исходной форме 4-кортежа Булоса) и рекурсия — две другие.

• Беркс, Артур ; Голдстайн, Герман ; Фон Нейман, Джон (1946). Предварительное обсуждение логической конструкции электронного вычислительного прибора ., перепечатано в Bell, Gordon ; Newell, Allen, ред. (1971) [1946]. Компьютерные структуры: материалы для чтения и примеры . Нью-Йорк: McGraw-Hill Book Company. ISBN 0-07-004357-4.

• Кук, Стивен А.; Рекхоу, Роберт А. (1973). «Машины с произвольным доступом с ограничением по времени» (PDF) . Журнал компьютерных системных наук . 7 : 354–375 .

• Дэвис, Мартин (1958). Вычислимость и неразрешимость . Нью-Йорк: McGraw-Hill Book Company, Inc.

• Элгот, Кэлвин; Робинсон, Абрахам (1964). «Машины с произвольным доступом и хранимыми программами, подход к языкам программирования». Журнал Ассоциации вычислительной техники . 11 (4): 365–399 .

• Фишер, Патрик К .; Мейер, Альберт Р .; Розенберг, Арнольд Л. (1968), «Счетные машины и счетные языки», Математическая теория систем , 2 (3): 265–283 , doi :10.1007/bf01694011, MR  0235932, S2CID  13006433Разрабатывает теоремы об иерархии времени и пространства для счетных машин, аналогичные иерархиям для машин Тьюринга.

• Хартманис, Юрис (1971). «Вычислительная сложность машин с произвольным доступом и хранимыми программами». Теория математических систем . 5 (3): 232– 245.

• Хопкрофт, Джон ; Ульман, Джеффри (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Массовое чтение: Addison-Wesley. ISBN 0-201-02988-X.Сложная книга, посвященная вопросам машинной интерпретации «языков», NP-полноты и т. д.

• Хопкрофт, Джон ; Мотвани, Раджив ; Ульман, Джеффри (2003) [1979]. Введение в теорию автоматов, языки и вычисления (2-е изд.). Массовая литература: Addison-Wesley. стр. 352. ISBN 0-201-44124-1.

• Клини, Стивен (1952). Введение в метаматематику . Амстердам, Нидерланды: North-Holland Publishing Company. ISBN 0-7204-2103-9.

• Кнут, Дональд (1973) [1968]. Искусство программирования (2-е изд.). Рединг, Массачусетс: Addison-Wesley.См. страницы 462-463, где он определяет «новый вид абстрактной машины или «автомата», который имеет дело со связанными структурами».

• Ламбек, Иоахим (1961). «Как запрограммировать бесконечный абак». Математический вестник . 4 (3): 295–302 .В Приложении II Ламбек предлагает «формальное определение понятия «программа». Он ссылается на работу Мелзака (1961) и Клини (1952) « Введение в метаматематику» .

• Мелзак, З.А. (1961). «Неформальный арифметический подход к вычислимости и вычислениям». Канадский математический бюллетень . 4 (3): 279–293 .Мелзак не приводит никаких ссылок, но признает «полезность бесед с докторами Р. Хэммингом, Д. Макилроем и В. Высотсом из Bell Telephone Laborators, а также с доктором Х. Ваном из Оксфордского университета».

• Минский, Марвин (1961). «Рекурсивная неразрешимость проблемы Поста «Тэга» и другие темы в теории машин Тьюринга». Annals of Mathematics . 74 (3): 437– 455. doi :10.2307/1970290. JSTOR  1970290.

• Минский, Марвин (1967). Вычисления: Конечные и бесконечные машины (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc.В частности, см. главу 11: Модели, подобные цифровым компьютерам и главу 14: Очень простые основы вычислимости . В первой главе он определяет «Программные машины», а в последней главе обсуждает «Универсальные программные машины с двумя регистрами» и «...с одним регистром» и т. д.

• Шепердсон, Дж. К.; Стерджис, Х. Э. (1963). «Вычислимость рекурсивных функций». Журнал Ассоциации вычислительной техники (JACM) . 10 (2): 217– 255. doi : 10.1145/321160.321170 .Ценная справочная статья. В своем Приложении А авторы цитируют 4 других со ссылкой на «Минимальность инструкций, используемых в 4.1: Сравнение с аналогичными системами».

• • Капенгст, Хайнц (1959). «Eine Abstrakte programmgesteuerte Rechenmaschine». Zeitschrift für mathematische Logik und Grundlagen der Mathematik . 5 : 366–379 .

• • Ершов, А.П. (1958). «Об операторных алгоритмах». Доклады Академии наук СССР . 122 (6): 967–970 .Перевод на английский язык, Automat. Express 1 (1959), 20-23.

• • Петер, Рожа (1958). «Графические схемы и рекурсивные функции». Диалектика (на немецком языке). 12 ( 3–4 ): 373–393 . doi : 10.1111/j.1746-8361.1958.tb01470.x .

• • Гермес, Ганс (1954). «Die Universalität programmgesteuerter Rechenmaschinen». Матем.-Физ. Семестрберихте . 4 . Геттинген: 42–53 .

• Шёнхаге, А. (1980). «Машины модификации памяти». SIAM J. Comput . 9 (3). Общество промышленной и прикладной математики: 366–379 .При этом Шёнхаге показывает эквивалентность своего SMM с «преемником RAM» (машиной произвольного доступа) и т. д.

• Шрёппель, Рич (1972). «Машина с двумя счетчиками не может вычислить 2N» (PDF) . Массачусетский технологический институт, Лаборатория искусственного интеллекта, Меморандум об искусственном интеллекте № 257.Автор ссылается на работу Мински 1967 года и отмечает, что « Фрэнсис Яо независимо доказала невычислимость, используя аналогичный метод в апреле 1971 года.

• Van Emde Boas, Peter (1990). «Модели машин и симуляции». В Van Leeuwen, Jan (ред.). Справочник по теоретической информатике. Том A: Алгоритмы и сложность (1-е изд.). MIT Press/Elsevier. стр.  3–66 . ISBN 9780444880710.Трактовка SMM Ван Эмде Боаса представлена ​​на стр. 32-35. Эта трактовка проясняет Schōnhage 1980 — она близко следует, но немного расширяет трактовку Schōnhage. Обе ссылки могут быть необходимы для эффективного понимания.

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

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