Автомат очереди

Машина очереди , автомат очереди или автомат подтягивания (PUA) ^{[ нужна ссылка ]} — это конечный автомат с возможностью хранения и извлечения данных из очереди с бесконечной памятью . Это модель вычислений, эквивалентная машине Тьюринга , и поэтому она может обрабатывать тот же класс формальных языков .

Теория [ править ]

Машину очереди можно определить как шестикортежную

M=(Q,\Sigma ,\Gamma ,\$,s,\delta )

где

$\,Q$ — конечное множество состояний ;
$\,\Sigma \subset \Gamma$ – конечное множество входного алфавита ;
$\,\Gamma$ – конечный алфавит очереди ;
$\,\$\in \Gamma \setminus \Sigma$ — начальный символ очереди ;
$\,s\in Q$ это начальное состояние ;
$\,\delta :Q\times \Gamma \rightarrow Q\times \Gamma ^{*}$ – это функция перехода .

машины Конфигурация — это упорядоченная пара ее состояния и содержимого очереди. $\,(q,\gamma )\in Q\times \Gamma ^{*}$ , где $\,\Gamma ^{*}$ обозначает Клини замыкание $\,\Gamma$ . Начальная конфигурация входной строки $\,x$ определяется как $\,(s,x\$)$ , и переход $\rightarrow _{M}^{1}$ от одной конфигурации к другой определяется как:

\,(p,A\alpha )\rightarrow _{M}^{1}(q,\alpha \gamma )

где $A$ — символ из алфавита очереди, $\alpha$ представляет собой последовательность символов очереди ( $\alpha \in \Gamma ^{*}$ ), и $(q,\gamma )=\delta (p,A)$ . Обратите внимание на свойство очереди в отношении «первым пришел — первым обслужен».

Машина принимает строку $\,x\in \Sigma ^{*}$ если после конечного числа переходов стартовая конфигурация развивается до исчерпания строки (достижения нулевой строки $\,\epsilon$ ), или указано иное, если $\,(s,x\$)\rightarrow _{M}^{*}(q,\epsilon ).$ ^[1]

Полнота по Тьюрингу [ править ]

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

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

Машину очереди можно смоделировать с помощью машины Тьюринга, но проще с помощью многоленточной машины Тьюринга , которая, как известно, эквивалентна обычной одноленточной машине.Машина, имитирующая очередь, считывает входные данные на одной ленте и сохраняет очередь на второй, при этом нажатия и извлечения определяются простыми переходами к начальным и конечным символам ленты. ^[2] Формальным доказательством этого часто являются упражнения на курсах теоретической информатики.

Приложения [ править ]

Машины очередей предлагают простую модель, на которой можно строить компьютерные архитектуры . ^[3]^[4] языки программирования или алгоритмы . ^[5]^[6]

См. также [ править ]

Вычислимость
Эквиваленты машины Тьюринга
Детерминированный конечный автомат
Нажимной автомат
Дневная система
Manufactoria — браузерная флеш-игра, в которой игроку предлагается реализовать различные алгоритмы с использованием модели машины очереди.

Ссылки [ править ]

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

[1] Козен, Декстер К. (1997) [1951]. Дэвид Грис, Фред Б. Шнайдер (ред.). Автоматы и вычислимость (твердый переплет). Тексты для бакалавриата по информатике (1-е изд.). Нью-Йорк: Springer-Verlag. стр. 368–370 . ISBN 978-0-387-94907-9 .

[2] Рус, Теодор. «Варианты машин Тьюринга» (PDF) . Конспекты лекций по теории вычислений . Университет Айовы , Айова-Сити, Айова, 52242-1419. Архивировано из оригинала (PDF) 21 сентября 2008 г. Проверено 6 ноября 2007 г.

[3] Феллер, М.; Доктор медицинских наук Эрцеговац (1981). «Машины очередей: организация параллельных вычислений». Конпар 81 . Конспекты лекций по информатике. Том. 111. стр. 37–47. дои : 10.1007/BFb0105108 . ISBN 978-3-540-10827-6 .

[4] Шмит, Х.; Левин, Б.; Юлвисакер, Б. (2002). «Машины очередей: аппаратная компиляция в аппаратном обеспечении». Слушания. 10-й ежегодный симпозиум IEEE по программируемым пользовательским вычислительным машинам . стр. 152–160. CiteSeerX 10.1.1.6.7718 . дои : 10.1109/FPGA.2002.1106670 . ISBN 978-0-7695-1801-5 . S2CID 8993845 .

[5] Мур, Кристофер (20 сентября 1999 г.). «Очереди, стопки и трансцендентальность при переходе к хаосу» . Семинар проекта «Алгоритмы» . ИНРИА . Проверено 6 ноября 2007 г.

[6] фон Тун, Манфред (2007). «Машина очередей для оценки выражений» . Университет Ла Троб . Архивировано из оригинала 7 августа 2007 г. Проверено 6 ноября 2007 г.

[1]

[2]

[3]

[4]

[5]

[6]