Автомат очереди - Queue automaton

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

Теория

Автомат очередей можно определить как набор из шести

${ Displaystyle M = (Q, Sigma, Gamma, $, s, delta)}$ куда

• ${ displaystyle , Q}$ конечный набор состояния;
• ${ Displaystyle , Sigma subset Gamma}$ конечный набор вводить алфавит;
• ${ displaystyle , Gamma}$ конечный алфавит очереди;
• ${ Displaystyle , $ in Gamma - Sigma}$ это начальный символ очереди;
• ${ displaystyle , s in Q}$ это начальное состояние;
• ${ displaystyle , delta: Q times Gamma rightarrow Q times Gamma ^ {*}}$ это функция перехода.

Машина конфигурация упорядоченная пара его состояния и содержимого очереди ${ Displaystyle , (д, гамма) в Q раз Гамма ^ {*}}$, куда ${ Displaystyle , Gamma ^ {*}}$ обозначает Клини закрытие из ${ displaystyle , Gamma}$. Начальная конфигурация входной строки ${ Displaystyle , х}$ определяется как ${ Displaystyle , (s, х $)}$, а переход ${ displaystyle rightarrow _ {M} ^ {1}}$ от одной конфигурации к другой определяется как:

${ Displaystyle , (п, А альфа) rightarrow _ {M} ^ {1} (д, альфа гамма)}$

куда ${ displaystyle A}$ символ из алфавита очереди, ${ displaystyle alpha}$ - последовательность символов очереди (${ displaystyle alpha in Gamma ^ {*}}$), и ${ Displaystyle (д, гамма) = дельта (р, А)}$. Обратите внимание на свойство очереди в отношении «первым пришел - первым обслужен».

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

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

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

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

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

Приложения

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

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

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

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