WikiDer > Автомат очереди
А машина очереди или автомат очереди это конечный автомат с возможностью хранить и извлекать данные из бесконечной памяти очередь. Это модель вычислений, эквивалентная Машина Тьюринга, и поэтому он может обрабатывать тот же класс формальные языки.
Теория
Автомат очередей можно определить как набор из шести
- куда
- конечный набор состояния;
- конечный набор вводить алфавит;
- конечный алфавит очереди;
- это начальный символ очереди;
- это начальное состояние;
- это функция перехода.
Машина конфигурация упорядоченная пара его состояния и содержимого очереди , куда обозначает Клини закрытие из . Начальная конфигурация входной строки определяется как , а переход от одной конфигурации к другой определяется как:
куда символ из алфавита очереди, - последовательность символов очереди (), и . Обратите внимание на свойство очереди в отношении «первым пришел - первым обслужен».
Машина принимает строку если после конечного числа переходов начальная конфигурация эволюционирует, чтобы исчерпать строку (достигнув нулевой строки ), или же [1]
Полнота по Тьюрингу
Мы можем доказать, что машина с очередями эквивалентна машине Тьюринга, показав, что машина с очередями может моделировать машину Тьюринга и наоборот.
Машину Тьюринга можно смоделировать с помощью машины очереди, которая постоянно хранит копию содержимого машины Тьюринга в своей очереди, с двумя специальными маркерами: одним для положения головы ТМ и одним для конца ленты; его переходы имитируют переходы TM, проходя через всю очередь, выскакивая каждый из ее символов и повторно ставя либо вытянутый символ, либо, около позиции заголовка, эквивалент эффекта перехода TM.
Машину очереди можно смоделировать с помощью машины Тьюринга, но проще - с помощью многоленточная машина Тьюринга, который, как известно, эквивалентен обычной машине с одной лентой. имитирующая машина очереди считывает ввод на одной ленте и сохраняет очередь на второй, с толчками и импульсами, определяемыми простыми переходами к начальному и конечному символам ленты.[2] Формальным доказательством этого часто является упражнение на курсах теоретической информатики.
Приложения
Машины очереди предлагают простую модель, на которой можно основывать компьютерные архитектуры,[3][4] языки программирования, или же алгоритмы.[5][6]
Смотрите также
- Вычислимость
- Эквиваленты машины Тьюринга
- Детерминированный конечный автомат
- Выталкивающий автомат
- Система тегов
- Manufactoria, браузерная флеш-игра, в которой игроку предлагается реализовать различные алгоритмы с использованием модели машины очереди.
Рекомендации
- ^ Козен, Декстер К. (1997) [1951]. Дэвид Грис, Фред Б. Шнайдер (ред.). Автоматы и вычислимость (твердый переплет). Тексты для бакалавров по информатике (1-е изд.). Нью-Йорк: Springer-Verlag. стр.368–370. ISBN 978-0-387-94907-9.
- ^ Русь, Теодор. «Варианты машин Тьюринга» (PDF). Конспект лекций по теории вычислений. Университет Айовы, Айова-Сити, Айова, 52242-1419. Архивировано из оригинал (PDF) на 21.09.2008. Получено 2007-11-06.
- ^ Feller, M .; Доктор медицины Эрчеговац (1981). Машины очереди: организация для параллельных вычислений. Конспект лекций по информатике. 111. С. 37–47. Дои:10.1007 / BFb0105108. ISBN 978-3-540-10827-6.
- ^ Schmit, H .; Левин, Б .; Илвисакер, Б. (2002). «Машины очереди: Аппаратная компиляция в аппаратном обеспечении». Ход работы. 10-й ежегодный симпозиум IEEE по программируемым пользовательским вычислительным машинам. С. 152–160. CiteSeerX 10.1.1.6.7718. Дои:10.1109 / FPGA.2002.1106670. ISBN 978-0-7695-1801-5.
- ^ Мур, Кристофер (1999-09-20). «Очереди, стопки и трансцендентальность при переходе к хаосу». Семинар проекта "Алгоритмы". INRIA. Получено 2007-11-06.
- ^ фон Тум, Манфред (2007). «Машина очереди для вычисления выражений». Латробский университет. Архивировано из оригинал на 2007-08-07. Получено 2007-11-06.