Некоторые конкретные типы машин указателей называются связывающим автоматом, KU-машиной, SMM, атомистической машиной LISP, машиной указателей деревьев и т. д. [2]
Указательные машины не имеют арифметических инструкций. Вычисление происходит только путем чтения входных символов, изменения и выполнения различных тестов на его структуре хранения — шаблоне узлов и указателей, и вывода символов на основе тестов. В этом смысле модель похожа на машину Тьюринга .
Типы «стрелочных машин»
И Гуревич, и Бен-Амрам перечисляют ряд очень похожих «атомистических» моделей «абстрактных машин»; [3] [2] Бен-Амрам считает, что «атомистические модели» следует отличать от «высокоуровневых» моделей. Ниже будут представлены следующие атомистические модели:
Машины для модификации хранилища Schönhage (SMM), [4]
Машины Колмогорова–Успенского (КУМ или КУ-Машины). [5]
Бен-Амрам также представляет следующие разновидности, которые в данной статье не рассматриваются:
Атомистическая машина чистого LISP (APLM)
Атомистическая полнофункциональная машина LISP (AFLM),
Общие атомистические стрелочные машины,
Язык Джона I (два типа).
Модель машины для модификации хранилища (SMM) Шёнхаге
Следующая презентация следует за ван Эмде Боасом. [6]
Машина состоит из фиксированного алфавита входных символов, фиксированной программы и изменяемом направленном графе со стрелками, помеченными символами алфавита. Граф является хранилищем машины . Каждый узел графа имеет ровно одну исходящую стрелку, помеченную каждым символом, хотя некоторые из них могут возвращаться в исходный узел. Один фиксированный узел графа идентифицируется как начальный или «активный» узел.
Каждое слово символов в алфавите затем может быть преобразовано в путь через машину; например, 10011 будет преобразовано в взятие ребра 1 из начального узла, затем ребра 0 из результирующего узла, затем ребра 0, затем ребра 1, затем ребра 1. Таким образом, слово идентифицирует узел, конечный узел пути, но эта идентификация будет меняться по мере изменения графа во время вычислений.
Машина может получать инструкции, которые изменяют макет графика. Основные инструкции:
(1) инструкция new w , которая создает новый узел в конце пути w , со всеми его ребрами, направленными к предпоследнему узлу в w . (2) инструкция set w to 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 совпадает с типом «связывающего автомата», кратко описанным в первом томе «Искусства программирования» . [4]
Модель машины Колмогорова–Успенского (КУ-машина)
KUM отличается от SMM тем, что допускает только обратимые указатели: для каждого указателя из узла x на узел y должен присутствовать обратный указатель из y на x, помеченный тем же символом. Другими словами, граф хранения ненаправленный. Поскольку исходящие указатели должны быть помечены различными символами алфавита, графы KUM и SMM имеют исходящую степень O(1). Однако обратимость указателей KUM также ограничивает входящую степень до O(1). Это решает некоторые проблемы физического (в отличие от чисто информационного) реализма.
Между моделями имеются и другие, незначительные различия, такие как форма программы — таблица состояний вместо списка инструкций.
Соображения относительно модели указателя-машины
Использование модели в теории сложности : ван Эмде Боас (1990) выражает обеспокоенность тем, что эта форма абстрактной модели:
«интересная теоретическая модель, но... ее привлекательность как фундаментальной модели для теории сложности сомнительна. Ее мера времени основана на равномерном времени в контексте, где эта мера, как известно, недооценивает истинную временную сложность. То же самое наблюдение справедливо для меры пространства для машины» (ван Эмде Боас (1990) стр. 35)
Гуревич также выражает обеспокоенность:
«С прагматической точки зрения модель Шёнхаге обеспечивает хорошую меру временной сложности на современном уровне техники (хотя я бы предпочел что-то вроде компьютеров с произвольным доступом Angluin и Valiant)». [7]
Шёнхаге демонстрирует эквивалентность в реальном времени двух типов машин с произвольным доступом с помощью SMM. [4]
Алгоритмы в модели SMM : Шёнхаге демонстрирует, что SMM может выполнять целочисленное умножение за линейное время. [4]
Потенциальные возможности использования модели : Гуревич задается вопросом, будет ли параллельная машина KU «чем-то напоминать человеческий мозг» [8]
Параллельные вычисления : Все упомянутые выше модели являются последовательными. Параллельная (атомистическая) модель указателя была предложена Куком и Даймондом; [9] также использовалась высокоуровневая (неатомистическая) модель параллельной указателя [10]
Пост-машина Тьюринга — минималистская одноленточная, двунаправленная, 1 символ {пробел, метка} машина, подобная Тьюрингу, но с последовательным выполнением инструкций по умолчанию способом, аналогичным базовым машинам со счетчиками из 3 инструкций.
Дальнейшее чтение
Большинство ссылок и библиографию можно найти в статье Register machine . Нижеследующее относится к этой статье:
Амир Бен-Амрам (1995), Что такое «машина указателя»?, Новости SIGACT (ACM Special Interest Group on Automata and Computability Theory)», том 26, 1995. Где Бен-Амрам описывает типы и подтипы: (тип 1a) Абстрактные машины: атомистические модели, включая машины Колмогорова-Успенского (KUM), машины модификации памяти Шёнхаге (SMM), «автомат связывания» Кнута, APLM и AFLM (атомистическая машина Pure-LISP) и (атомистическая машина Full-LISP), общие атомистические машины указателя, язык I Джонса; (тип 1b) Абстрактные машины: высокоуровневые модели, (тип 2) алгоритмы указателя.
Юрий Гуревич (2000), Sequential Abstract State Machines Capture Sequential Algorithms , ACM Transactions on Computational Logic, т. 1, № 1, (июль 2000 г.), страницы 77–111. В одном предложении Гуревич сравнивает «машины модификации памяти» Шёнхаге [1980] с «машинами указателей» Кнута. Для получения дополнительной информации о похожих моделях, таких как «машины произвольного доступа», Гуревич ссылается:
Джон Э. Сэвидж (1998), Модели вычислений: исследование мощности вычислений. Эддисон Уэсли Лонгман.
Юрий Гуревич (1988), О машинах Колмогорова и смежных вопросах, рубрика «Логика в информатике», Бюллетень Европейской ассоциации теоретической информатики, Номер 35, июнь 1988, 71-82. Ввел единое описание машин Шёнхаге и Колмогорова-Успенского, используемое здесь.
Арнольд Шёнхаге (1980), Машины модификации памяти , Общество промышленной и прикладной математики, SIAM J. Comput. Vol. 9, No. 3, август 1980 г. В этой статье Шёнхаге показывает эквивалентность своей МММ с «преемницей RAM» (машиной с произвольным доступом) и т. д. Он ссылается на более раннюю статью, в которой он представляет МММ:
Ян ван Леувен , редактор. Справочник по теоретической информатике. Том A: Алгоритмы и сложность , MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (том A).
Трактовка SMM ван Эмде Боаса представлена на стр. 32-35. Эта трактовка проясняет Schönhage 1980 — она близко следует, но немного расширяет трактовку Schönhage. Обе ссылки могут быть необходимы для эффективного понимания.
Ссылки
^ Клото, Брайан; Ранджан, Деш (2006). «Некоторые результаты разделения между классами алгоритмов указателей».
^ ab Амир Бен-Амрам (1995). Что такое «указательная машина»?, SIGACT News (ACM Special Interest Group on Automata and Computability Theory), том 26, 1995.
↑ Юрий Гуревич (2000), Последовательные абстрактные конечные автоматы захватывают последовательные алгоритмы , ACM Transactions on Computational Logic, т. 1, № 1, (июль 2000 г.), страницы 77–111.
^ abcd Арнольд Шёнхаге (1980), Машины для модификации хранилища , SIAM Journal on Computing Vol. 9, № 3, август 1980 г.
↑ Андрей Колмогоров и В. Успенский , Об определении алгоритма, Успехи математических наук 13 (1958), 3-28. Английский перевод в American Mathematical Society Translations, Серия II, Том 29 (1963), стр. 217-245.
^ Питер ван Эмде Боас , Модели машин и симуляции , стр. 3–66 в: Ян ван Леувен , ред. Справочник по теоретической информатике. Том A: Алгоритмы и сложность , MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (том A).
^ Гуревич (1988) стр. 6 со ссылкой на Angluin D. и Valiant LG, «Быстрые вероятностные алгоритмы для гамильтоновых цепей и сопоставлений», Журнал компьютерных и системных наук 18 (1979) 155-193.
↑ Юрий Гуревич (1988), О машинах Колмогорова и связанных с ними вопросах, колонка «Логика в информатике», Бюллетень Европейской ассоциации теоретической информатики, номер 35, июнь 1988 г., стр. 71–82.
^ Кук, Стивен А.; Даймонд, Патрик В. (март 1993 г.). «Параллельные машины указателей». Computational Complexity . 3 : 19–30. doi :10.1007/BF01200405.
^ Гудрич, МТ; Косараджу, СР (1996). «Сортировка на параллельной указательной машине с приложениями для оценки выражений множеств». Журнал ACM . 43 (2): 331–361. doi :10.1145/226643.226670.
