Queue automaton

A queue machine can be defined as a six-tuple

${\displaystyle M=(Q,\Sigma ,\Gamma ,\$,s,\delta )}$ where

• ${\displaystyle \,Q}$ is a finite set of states;
• ${\displaystyle \,\Sigma \subset \Gamma }$ is the finite set of the input alphabet;
• ${\displaystyle \,\Gamma }$ is the finite queue alphabet;
• ${\displaystyle \,\$\in \Gamma \setminus \Sigma }$ is the initial queue symbol;
• ${\displaystyle \,s\in Q}$ is the start state;
• ${\displaystyle \,\delta :Q\times \Gamma \rightarrow Q\times \Gamma ^{*}}$ is the transition function.

A machine configuration is an ordered pair of its state and queue contents ${\displaystyle \,(q,\gamma )\in Q\times \Gamma ^{*}}$, where ${\displaystyle \,\Gamma ^{*}}$ denotes the Kleene closure of ${\displaystyle \,\Gamma }$. The starting configuration on an input string ${\displaystyle \,x}$ is defined as ${\displaystyle \,(s,x\$)}$, and the transition ${\displaystyle \rightarrow _{M}^{1}}$ from one configuration to the next is defined as:

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

where ${\displaystyle A}$ is a symbol from the queue alphabet, ${\displaystyle \alpha }$ is a sequence of queue symbols (${\displaystyle \alpha \in \Gamma ^{*}}$), and ${\displaystyle (q,\gamma )=\delta (p,A)}$. Note the "first-in-first-out" property of the queue in the relation.

The machine accepts a string ${\displaystyle \,x\in \Sigma ^{*}}$ if after a finite number of transitions the starting configuration evolves to exhaust the string (reaching the null string ${\displaystyle \,\epsilon }$), or otherwise stated, if ${\displaystyle \,(s,x\$)\rightarrow _{M}^{*}(q,\epsilon ).}$[1]

Queue machines offer a simple model on which to base computer architectures,[3][4] programming languages, or algorithms.[5][6]

• Computability
• Turing machine equivalents
• Deterministic finite automaton
• Pushdown automaton
• Tag system
• Manufactoria, a browser flash game tasking the player with implementation of various algorithms using a queue machine model.