Указатель машины - Pointer machine

В теоретическая информатика а указатель машины является "атомистическим" абстрактная вычислительная машина модель, родственная машина с произвольным доступом. А указатель алгоритм является алгоритм ограничивается моделью машины указателя.[1]

В зависимости от типа указательная машина может называться связывающим автоматом, KU-машиной, SMM, атомистической LISP-машиной, древовидной машиной и т. Д. (См. Ben-Amram 1995). В литературе существует по крайней мере три основных разновидности - модель Колмогорова-Успенского (KUM, KU-машина), связывающий автомат Кнута и модель машины модификации памяти Шенхаге (SMM). SMM кажется наиболее распространенным.

Со своей "ленты только для чтения" (или ее эквивалента) указатель получает Вход- ограниченные последовательности символов («слова»), состоящие как минимум из двух символов, например {0, 1} - и пишет выход последовательности символов на выходной ленте, предназначенной только для записи (или эквивалентной). Для преобразования последовательности символов (входного слова) в последовательность символов на выходе машина оснащена «программой» - конечным автоматом (память и список инструкций). Через свой конечный автомат программа читает входные символы, работает на его структура хранения- набор «узлов» (регистров), соединенных «ребрами» (указатели, помеченные символами, например, {0, 1}), и пишет символы на выходной ленте.

Указательные машины не могут выполнять арифметические операции. Вычисления продолжаются только путем чтения входных символов, изменения и выполнения различных тестов в его структуре хранения - паттерна узлов и указателей и вывода символов на основе тестов. «Информация» находится в хранилище структура.

Типы "стрелочных машин"

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

  • Машины для модификации складских помещений (SMM) Schönhage,
  • Машины Колмогорова – Успенского (КУМ или КУ-машины),
  • «Связывающий автомат» Кнута

Но Бен-Амрам добавляет еще:

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

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

Использование модели в теории сложности: van Emde Boas (1990) выражает озабоченность по поводу того, что эта форма абстрактной модели:

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

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

«С прагматической точки зрения, модель Шенхаге обеспечивает хорошую меру временной сложности на текущем уровне техники (хотя я бы предпочел что-то вроде компьютеров с произвольным доступом Angluin и Valiant)» (Гуревич (1988) стр. 6 с ссылка на Angluin D. и Valiant LG, "Быстрые вероятностные алгоритмы для гамильтоновых схем и согласований", Журнал компьютерных и системных наук 18 (1979) 155-193.)

Тот факт, что в § 3 и § 4 (стр. 494–497) сам Шёнхаге (1980) демонстрирует эквивалентность двух своих машина с произвольным доступом модели "RAM0" и "RAM1" заставляют усомниться в необходимости SMM для изучения сложности.

Возможные варианты использования модели: Однако Шенхаге (1980) демонстрирует в своем § 6, Целочисленное умножение за линейное время. И Гуревич задается вопросом, похожа ли «параллельная машина КУ» «чем-то на человеческий мозг» (Гуревич (1988) с. 5).

Модель машины модификации хранилища (SMM) Schönhage

SMM-модель Шёнхаге кажется наиболее распространенной и принятой. Это совсем не похоже на зарегистрировать машину модель и другие общие вычислительные модели, например ленточный Машина Тьюринга или помеченные отверстия и неразличимые камешки счетчик машина.[2]

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

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

Машина может получать инструкции, которые изменяют структуру графика. Основные инструкции - это новый ш инструкция, которая создает новый узел, который является «результатом» следования за строкой ш, а набор ш к v инструкция, которая (повторно) направляет ребро на другой узел. Здесь ш и v представлять слова. v это бывший слово - т.е. ранее созданная строка символов - так, чтобы перенаправленное ребро указывало «назад» на старый узел, который является «результатом» этой строки.

Этапы создания нового «узла» в машине с 2 символами {0,1}: при встрече с новым словом (здесь: «11») машина отвечает за (i) создание нового узла 3 и указание на него соответствующего 1-ребра, затем (ii) создание двух новых указателей (0- «ребро» и 1- «ребро»), оба из которых указывают на предыдущий узел (здесь: узел 2).

(1) новый ш: создает новый узел. ш представляет новый слово который создает новый узел. Машина читает слово ш, следуя по пути, обозначенному символами ш пока машина не дойдет до последнего, «дополнительного» символа в слове. Вместо этого дополнительный символ заставляет последнее состояние создать новый узел и «перевернуть» соответствующую ему стрелку (помеченную этим символом) со старой позиции, чтобы указать на новый узел. Новый узел, в свою очередь, направляет все свои края обратно в старое последнее состояние, где они просто «отдыхают», пока не будут перенаправлены другим новый или же набор. В некотором смысле новые узлы «спят», ожидая назначения. В случае начального или центрального узла мы аналогичным образом начнем с того, что оба его края будут указывать на себя.

  • Пример: Пусть «w» будет 10110 [1], где последний символ находится в скобках, чтобы обозначить его особый статус. Мы берем 1 край узла, достигнутого 10110 (в конце пути с пятью, следовательно, с шестью узлами), и указываем его на новый седьмой узел. Затем два ребра этого нового узла указывают «назад» на 6-й узел пути.

(2)Набор ш к v: перенаправляет (перемещает) край (стрелку) с пути, представленного словом ш к бывшему узлу, который представляет слово v. И снова перенаправляется последняя стрелка на пути.

  • Пример: Установите 1011011 на 1011, после приведенной выше инструкции изменит стрелку 1 нового узла в 101101, чтобы указать на пятый узел в пути, достигнутом в 1011. Таким образом, путь 1011011 теперь будет иметь тот же результат, что и 1011.

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

Шаги по созданию новых «узлов» в 2-символьной {0,1} машине. Когда слова - строки символов 0 и 1 - входят в машину, машина создает график. Как показано здесь, после 5-го шага два слова - «111» и «10» - оба указывают на узел 4. В это время, если бы машина выполняла если 10=111 тогда xxx, то тест будет успешным, и машина действительно перейдет на xxx.

Модель «связывающего автомата» Кнута

По словам Шенхаге, Кнут отметил, что модель SMM совпадает со специальным типом «связывающих автоматов», кратко объясненных в первом томе книги. Искусство программирования (ср. [4, с. 462–463])

Модель машины Колмогорова – Успенского (КУ-машины)

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

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

Смотрите также

Зарегистрировать машину - на основе общих регистров абстрактная машина вычислительная модель

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

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

Рекомендации

  1. ^ Клото, Брайан; Ранджан, Деш (2006). «Некоторые результаты разделения между классами алгоритмов указателей».
  2. ^ Это трактовка ван Эмде Боаса 1990 года, а не Шенхаге, в которой отсутствуют примеры.

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

  • Амир Бен-Амрам (1995), Что такое «указательная машина»?, SIGACTN: SIGACT News (Специальная группа ACM по автоматам и теории вычислимости), том 26, 1995 г. также: DIKU, Департамент компьютерных наук, Копенгагенский университет, [email protected]. Бен-Амрам описывает типы и подтипы: (тип 1a) абстрактные машины: атомистические модели, включая машины Колмогорова-Успенского (KUM), машины модификации хранилища (SMM) Шёнхаге, «связывающий автомат» Кнута, APLM и AFLM (атомистическая машина Pure-LISP) и (Atomistic Full-LISP machine), Общие атомистические указательные машины, язык Jone I; (тип 1b) абстрактные машины: модели высокого уровня, (тип 2) алгоритмы указателя.
  • Андрей Колмогоров и В. Успенский, Об определении алгоритма, Успехи матем. АН 13 (1958), 3-28. Английский перевод в American Mathematical Society Translations, Series II, Volume 29 (1963), pp. 217–245.
  • Юрий Гуревич (2000), Последовательные абстрактные конечные автоматы захватывают последовательные алгоритмы, Транзакции ACM по вычислительной логике, т. 1, вып. 1, (июль 2000 г.), страницы 77–111. Одним предложением Гуревич сравнивает «машины модификации памяти» Шенхаге [1980] с «стрелочными машинами» Кнута. Подробнее о подобных моделях, таких как «машины с произвольным доступом», Гуревич ссылается:
  • Юрий Гуревич (1988), О колмогоровских машинах и смежных вопросах, колонка «Логика в информатике», Бюллетень Европейской ассоциации теоретической информатики, номер 35, июнь 1988 г., 71-82. Введено единое описание используемых здесь машин Шёнхаге и Колмогорова-Успенского.
  • Арнольд Шёнхаге (1980), Машины для модификации хранения, Общество промышленной и прикладной математики, SIAM J. Comput. Vol. 9, No. 3, август 1980 г. В котором Шёнхаге показывает эквивалентность своего SMM с «преемником RAM» (машина произвольного доступа) и т. Д. Он ссылается на более ранний документ, в котором он представляет SMM:
    • Арнольд Шёнхаге (1970), Universelle Turing Speicherung, Automatentheorie und Formale Sprachen, Dörr, Hotz, eds. Библиогр. Институт, Мангейм, 1970, стр. 69–383.
  • Питер ван Эмде Боас, Модели машин и симуляции стр. 3–66, появляющиеся в:
Ян ван Леувен, изд. Справочник по теоретической информатике. Том A: Алгоритмы и сложность, MIT PRESS / Elsevier, 1990. ISBN  0-444-88071-2 (том А). QA 76.H279 1990.
Трактовка СММ ван Эмде Боасом приводится на стр. 32-35. Это лечение проясняет Schönhage 1980 - оно близко следует, но немного расширяет лечение Schönhage. Обе ссылки могут потребоваться для эффективного понимания.