Указательная машина

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

Некоторые конкретные типы указательных машин называются связующим автоматом, КУ-машиной, SMM, атомистической LISP-машиной, древовидной указательной машиной и т. д.

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

Виды «указательных машин»

И Гуревич, и Бен-Амрам перечисляют ряд очень похожих «атомистических» моделей «абстрактных машин»; Бен-Амрам считает, что «атомистические модели» следует отличать от моделей «высокого уровня». Ниже будут представлены следующие атомистические модели:

• Машины для модификации хранилища Schönhage (SMM),
• Kolmogorov–Uspenskii machines (KUM or KU-Machines).

Бен-Амрам также представляет следующие сорта, которые далее не обсуждаются в этой статье:

• Атомистическая машина чистого LISP (APLM)
• Атомистическая машина с полным LISP (AFLM),
• Общие атомистические указатели,
• Язык Джонса I (два типа).

Модель машины для модификации хранилища (SMM) Шёнхаге

Следующая презентация посвящена ван Эмде Боасу.

Машина состоит из фиксированного алфавита входных символов, фиксированной программы и изменяемого ориентированного графа , стрелки которого помечены символами алфавита. машины Граф — это память . Каждый узел графа имеет ровно одну исходящую стрелку, помеченную каждым символом, хотя некоторые из них могут возвращаться в исходный узел. Один фиксированный узел графа идентифицируется как начальный или «активный» узел.

Каждое слово символов алфавита затем можно перевести в путь через машину; например, 10011 будет означать взятие ребра 1 из начального узла, затем ребра 0 из результирующего узла, затем ребра 0, затем ребра 1, затем ребра 1. Таким образом, слово идентифицирует узел, конечный узел пути, но эта идентификация будет меняться по мере изменения графика во время вычислений.

Машина может получать инструкции, изменяющие структуру графика. Основные инструкции таковы:

(1) новая инструкция w , которая создает новый узел в конце пути w , причем все его ребра направлены к предпоследнему узлу в w . (2) установить инструкцию w в v , которая (пере) направляет ребро в другой узел. Здесь w и v представляют слова . Команда приводит к изменению назначения последнего ребра на пути w .

Некоторые шаги выполнения 2-символьной машины {0,1} с инструкциями: (1) новое ε; (2) новый 1; (3) новый 11. Инструкция №1 инициализирует граф хранения как единственный узел, узел 1, в графе хранения.

(3) Если v = w, то инструкция z : условная инструкция, которая сравнивает два пути, представленные словами w и v, чтобы определить, заканчиваются ли они в одном и том же узле; если да, то перейдите к инструкции z, иначе продолжайте. Эта инструкция служит той же цели, что и команда if в любом императивном языке программирования.

Эволюция графа памяти в 2-символьной машине {0,1} с инструкциями: (1) новое ε; (2) новый 1; (3) новый 11; (4) новые 10; (5) установите 111 на 10. В этот момент, если бы машина выполнила if 10=111 then xxx, то тест был бы успешным и машина действительно перешла бы на xxx.

(4) инструкции чтения и записи для ввода/вывода, доступ к входной ленте только для чтения и выходной ленте только для записи, обе из которых содержат символы алфавита.

Кнут отметил, что модель SMM совпадает с типом «связывающего автомата», кратко описанным в первом томе книги « Искусство компьютерного программирования» .

Kolmogorov–Uspenskii machine (KU-machine) model

KUM отличается от SMM тем, что допускает только обратимые указатели: для каждого указателя от узла x к узлу y должен присутствовать обратный указатель от y к x, помеченный тем же символом. Другими словами, граф хранения неориентированный. Поскольку исходящие указатели должны быть помечены разными символами алфавита, графы KUM и SMM имеют исходящую степень O(1). Однако обратимость указателей KUM также ограничивает входную степень до O(1). Это решает некоторые проблемы физического (в отличие от чисто информационного) реализма.

Есть и другие, незначительные различия между моделями, например, форма программы — таблица состояний вместо списка инструкций.

Соображения относительно модели указателя

Использование модели в теории сложности : Ван Эмде Боас (1990) выражает обеспокоенность тем, что эта форма абстрактной модели:

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

Гуревич также выражает обеспокоенность:

«С прагматической точки зрения, модель Шенхаге обеспечивает хорошую оценку временной сложности на современном уровне техники (хотя я бы предпочел что-то вроде компьютеров с произвольным доступом Angluin и Valiant)».

Шёнхаге демонстрирует в реальном времени эквивалентность двух типов машин с произвольным доступом и SMM.

Алгоритмы в модели SMM : Шёнхаге демонстрирует, что SMM может выполнять целочисленное умножение за линейное время.

Потенциальное использование модели : Гуревич задается вопросом, «напоминает ли параллельная машина КУ чем-то человеческий мозг»

Параллельные вычисления . Все упомянутые выше модели являются последовательными. Модель параллельной (атомистической) машины с указателем была предложена Куком и Даймондом; также использовалась высокоуровневая (неатомистическая) модель машины с параллельным указателем.

См. также

Регистровая машина — универсальная абстрактной машины вычислительная модель на основе регистров.

• Счетная машина - самая примитивная машина, наборы инструкций базовых моделей используются во всем классе регистровых машин.
• Машина с произвольным доступом — ОЗУ: машина-счетчик с добавленной возможностью косвенной адресации.
• Машина с хранимой программой произвольного доступа — RASP: машина на основе счетчика или ОЗУ с «программой инструкций», которую можно найти в самих регистрах, наподобие универсальной машины Тьюринга, то есть архитектуры фон Неймана .

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

• Машина Пост-Тьюринга — минималистская машина с одной лентой, в двух направлениях, с 1 символом {пусто, метка}. Машина, подобная Тьюрингу, но с последовательным выполнением инструкций по умолчанию, аналогично базовым машинам со счетчиком с тремя командами.

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

Большинство ссылок и библиографию можно найти в статье « Регистрация машины» . К этой статье относятся следующие особенности:

• Амир Бен-Амрам (1995), Что такое «указательная машина»? , SIGACT News (Специальная группа по интересам ACM по автоматам и теории вычислимости)», том 26, 1995. В котором Бен-Амрам описывает типы и подтипы: (тип 1a) Абстрактные машины: атомистические модели, включая машины Колмогорова-Успенского (KUM), машины Шенхаге Машины модификации хранилища (SMM), «Связывающий автомат» Кнута, APLM и AFLM (Атомистическая машина Pure-LISP) и (Атомистическая машина Full-LISP), Общие атомистические указатели, язык Джонса I (тип 1b). Абстрактные машины: модели высокого уровня, (тип 2) Алгоритмы указателей.
• Юрий Гуревич (2000), Последовательные абстрактные конечные автоматы захватывают последовательные алгоритмы , Транзакции ACM в вычислительной логике, том. 1, нет. 1 (июль 2000 г.), страницы 77–111. В одном предложении Гуревич сравнивает «машины модификации памяти» Шёнхаге [1980] с «указательными машинами» Кнута. Подробнее о подобных моделях, таких как «машины произвольного доступа», ссылается Гуревич:
  • Джон Э. Сэвидж (1998), Модели вычислений: исследование возможностей вычислений . Эддисон Уэсли Лонгман.
• Юрий Гуревич (1988), «О машинах Колмогорова и связанных с ними проблемах », колонка «Логика в информатике», Бюллетень Европейской ассоциации теоретической информатики, номер 35, июнь 1988 г., 71-82. Введено единое описание используемых здесь машин Шенхаге и Колмогорова-Успенского.
• Арнольд Шёнхаге (1980), Машины для модификации памяти , Общество промышленной и прикладной математики, SIAM J. Comput. Том. 9, № 3, август 1980 г. В котором Шёнхаге показывает эквивалентность своего SMM с «наследником RAM» (машиной произвольного доступа) и т. д. Он ссылается на более раннюю статью, в которой представляет SMM:
  • Арнольд Шёнхаге (1970), Универсальное хранилище Тьюринга , теория автоматов и формальные языки, Дёрр, Хотц, ред. Библиография Институт, Мангейм, 1970, стр. 69–383.
• Питер ван Эмде Боас , Модели машин и моделирование, стр. 3–66, появляются в:

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

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