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

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

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

Основные функции

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

• CLR(r): Очистить регистр r . (Установите r равным нулю.)
• INC (r): INCrement содержимого регистра 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 — «Перейти, если не ноль», используется вместо JZ):

  { INC ( р ), DEC ( р ), CLR ( р ), CPY ( р _j , р _k ), JNZ ( р, 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 _правда )}

• Машина 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 указательной машины , также кратко обсуждаемой у ван Эмде Боаса (1990):

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

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

  { INC (r), CPY ( р _s , р _d ), JE ( р _j , р _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 , безусловный переход, HALT }

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

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

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

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

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

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

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

Инструкция	Влияние на регистр «j»	Влияние на ICR регистра счетчика команд	Краткое содержание
ИНК ( j )	[дж] +1 → j	[ИК] +1 → ИК	Увеличить содержимое регистра j; следующая инструкция
ДЕКАБРЬ ( j )	[дж] -1 → j	[ИК] +1 → ИК	Уменьшить содержимое регистра j; следующая инструкция
JZ ( дж , з )		ЕСЛИ [j] = 0 ТО I z → IC ИНАЧЕ [IC] +1 → IC	Если содержимое регистра j=0, то инструкция z, иначе следующая инструкция.
ОСТАНОВКА

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

Первоначально регистр №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 градусов: номера команд (адреса) расположены вверху, мнемоника инструкций — под адресами, а параметры команд — под мнемониками (по одному на ячейку):

															1	2	3	4	5	6	7	8	9	10	← Номер инструкции (адрес)
															Джей Зи	Декабрь	ИНК	ИНК	Джей Зи	Джей Зи	Декабрь	ИНК	Джей Зи	ЧАС	← Инструкция
															2	2	3	1	0	1	1	2	0		← Регистрационный номер
															6				1	10			6		← Переход к номеру инструкции
шаг		IC	Инст №	рег №	J-адрес		reg0	reg1	reg2	reg3	reg4		IC
начинать							0	0	2	0	0		1												переместите [#2] в №1 и №3:
1		1	Джей Зи	2	6		0	0	2	0	0		1→2		Джей Зи										Переход не выполнен: регистр №2 содержит 2
2		2	Декабрь	2	0		0	0	2→1	0	0		2→3			Декабрь									Уменьшить регистр №2 с 2 до 1.
3		3	ИНК	3	0		0	0	1	0→1	0		3→4				ИНК								Увеличить регистр №3 с 0 до 1.
4		4	ИНК	1	0		0	0→1	1	1	0		4→5					ИНК							Увеличить регистр №1 с 0 до 1.
5		5	Джей Зи	0	1		0	1	1	1	0		5→1						Джей Зи						U-Jump: регистр №0 пуст.
6		1	Джей Зи	2	6		0	1	1	1	0		1→2		Джей Зи										Переход не выполнен: регистр №2 содержит 1
7		2	Декабрь	2	0		0	1	1→0	1	0		2→3			Декабрь									Уменьшить регистр №2 с 1 до 0.
8		3	ИНК	3	0		0	1	0	1→2	0		3→4				ИНК								Увеличить регистр №3 с 1 до 2.
9		4	ИНК	1	0		0	1→2	0	2	0		4→5					ИНК							Увеличить регистр №1 с 1 до 2.
10		5	Джей Зи	0	1		0	2	0	2	0		5→1						Джей Зи						U-Jump: регистр №0 пуст.
11		1	Джей Зи	2	6		0	2	0	2	0		1→6		Джей Зи										Перейти!: регистр №2 пуст
																									переместите [1] на 2:
12		6	Джей Зи	1	10		0	2	0	2	0		6→7							Джей Зи					Переход не выполнен: регистр №1 содержит 2
13		7	Декабрь	1	0		0	2→1	0	2	0		7→8								Декабрь				Уменьшить регистр №1 с 2 до 1.
14		8	ИНК	2	0		0	1	0→1	2	0		8→9									ИНК			Увеличить регистр №2 с 0 до 1.
15		9	Джей Зи	0	6		0	1	1	2	0		9→6										Джей Зи		U-Jump: регистр №0 пуст.
16		6	Джей Зи	1	10		0	1	1	2	0		6→7							Джей Зи					Переход не выполнен: регистр №1 содержит 1
17		7	Декабрь	1	0		0	1→0	1	2	0		7→8								Декабрь				Уменьшить регистр №1 с 1 до 0.
18		8	ИНК	2	0		0	0	1→2	2	0		8→9									ИНК			Увеличить регистр №2 с 1 до 2.
19		9	Джей Зи	0	6		0	0	2	2	0		9→6										Джей Зи		U-Jump: регистр №0 пуст.
20		6	Джей Зи	1	10		0	0	2	2	0		6→10							Джей Зи					Перейти!: регистр №1 пуст
21		10	ЧАС	0	0		0	0	2	2	0		10→10											ЧАС	ОСТАНОВКА

Частично рекурсивные функции: построение «удобных инструкций» с помощью рекурсии

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

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

• Начальный набор команд: { 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 ), используя приведенное выше:

{ 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. Функция идентификации
4. Функция композиции
5. Примитивная рекурсия (индукция)
6. оператор μ (оператор неограниченного поиска)

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

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

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

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

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

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

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

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

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

• • ПРИРАЩЕНИЕ (r); [г] +1 → р
  • ДЕКРЕМЕНТ (r); [г] -1 → р
  • ЧИСТО (r); 0 → р
  • КОПИРОВАТЬ (от r _до r _d ); [р _с ] → р _д
  • ПЕРЕХОД-БЕЗУСЛОВНЫЙ к инструкции 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 ) } до того, как он доказал, что «универсальную программную машину» можно построить только с двумя регистрами (стр. 255 и далее).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

• Джордж Булос , Джон П. Берджесс , Ричард Джеффри (2002), Вычислимость и логика: четвертое издание , Издательство Кембриджского университета, Кембридж, Англия. Оригинальный текст Булоса-Джеффри был тщательно переработан Берджессом: он более продвинут, чем вводный учебник. Модель «счетной машины» подробно описана в главе 5 «Вычислимость счетов» ; это одна из трех моделей, которые широко рассматриваются и сравниваются: машина Тьюринга (все еще в исходной четырехкортежной форме Булоса) и две другие рекурсивные модели.
• Артур Беркс , Герман Голдстайн , Джон фон Нейман (1946), Предварительное обсуждение логического проектирования электронного вычислительного прибора , перепечатано на стр. 92 и далее в книге Гордона Белла и Аллена Ньюэлла (1971), Компьютерные структуры: материалы для чтения и примеры , Книга МакГроу-Хилла Компания, Нью-Йорк. 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 (3): 265–283, doi : 10.1007/bf01694011 , MR   0235932 , S2CID   13006433 . Разрабатывает теоремы временной и пространственной иерархии для счетных машин, аналогичные иерархиям для машин Тьюринга.
• Дж. Хартманис (1971), «Вычислительная сложность машин с хранимыми программами произвольного доступа», Mathematical Systems Theory 5, 3 (1971), стр. 232–245.
• Хопкрофт, Джон; Джеффри Уллман (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Чтение мессы: Аддисон-Уэсли. ISBN  0-201-02988-Х . Сложная книга, посвященная вопросам машинной интерпретации «языков», NP-полноты и т. д.
• Стивен Клини (1952), «Введение в метаматематику» , Издательство Северной Голландии, Амстердам, Нидерланды. ISBN   0-7204-2103-9 .
• Дональд Кнут (1968), Искусство компьютерного программирования , второе издание, 1973 г., Аддисон-Уэсли, Ридинг, Массачусетс. См. страницы 462–463, где он определяет «новый вид абстрактной машины или «автомата», который имеет дело со связанными структурами».
• Иоахим Ламбек (1961, получено 15 июня 1961 г.), Как запрограммировать бесконечные счеты , Mathematical Bulletin, vol. 4, нет. 3. Сентябрь 1961 г., страницы 295–302. В своем Приложении II Ламбек предлагает «формальное определение «программы». Он ссылается на Melzak (1961) и Kleene (1952) « Введение в метаматематику» .
• З.А. Мельзак (1961, получено 15 мая 1961 г.), Неофициальный арифметический подход к вычислимости и вычислениям , Canadian Mathematical Bulletin , vol. 4, нет. 3. Сентябрь 1961 г., страницы 279–293. Мельзак не приводит никаких упоминаний, но признает «пользу бесед с докторами Р. Хэммингом, Д. Макилроем и В. Высоцем из телефонных лабораторий Bell и с доктором Х. Вангом из Оксфордского университета».
• Марвин Мински (1961). «Рекурсивная неразрешимость проблемы Поста о «теге» и других тем теории машин Тьюринга». Анналы математики . 74 (3): 437–455. дои : 10.2307/1970290 . JSTOR   1970290 .
• Марвин Мински (1967). Вычисления: конечные и бесконечные машины (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc. В частности, см. главу 11: Модели, подобные цифровым компьютерам , и главу 14: Очень простые основы вычислительности . В первой главе он дает определение «программным машинам», а в следующей главе обсуждает «универсальные программные машины с двумя регистрами» и «... с одним регистром» и т. д.
• Джон К. Шепердсон и Х. Э. Стерджис (1961) получили в декабре 1961 года «Вычислимость рекурсивных функций» , журнал Ассоциации вычислительной техники (JACM) 10:217-255, 1963. Чрезвычайно ценный справочный документ. В Приложении А авторы цитируют еще 4 со ссылкой на «Минимальность инструкций, используемых в 4.1: Сравнение с аналогичными системами».
  • Капенгст, Хайнц, Абстрактная вычислительная машина с программным управлением» , Журнал математической логики и основ математики: 5 (1959), 366–379.
  • Ershov, A. P. On operator algorithms , (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
  • Петер, Рожа Графовые схемы и рекурсивные функции , Dialectica 12 (1958), 373.
  • Гермес, Ганс Универсальность вычислительных машин с программным управлением . Матем.-Физ. Отчеты за семестр (Геттинген) 4 (1954), 42–53.
• А. Шёнхаге (1980), Машины для модификации памяти , Общество промышленной и прикладной математики, SIAM J. Comput. Том. 9, № 3, август 1980 г. При этом Шёнхаге показывает эквивалентность своего СММ «преемнику RAM» (машине произвольного доступа) и т. д.
• Рич Шреппель , май 1972 г., «Машина с двумя счетчиками не может вычислить 2». ^Н «, Массачусетский технологический институт, Лаборатория искусственного интеллекта, Памятка по искусственному интеллекту № 257. Автор ссылается на Мински, 1967 год, и отмечает, что « Фрэнсис Яо независимо доказала невычислимость, используя аналогичный метод в апреле 1971 года».
• Питер ван Эмде Боас , Модели машин и моделирование, стр. 3–66, появляются в:

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

Отношение ван Эмде Боаса к СММ представлено на стр. 32–35. Эта трактовка проясняет Шёнхаге 1980 — она близко следует, но немного расширяет трактовку Шёнхаге. Обе ссылки могут быть необходимы для эффективного понимания.

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

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

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