# Queue automaton

A queue machine or queue automaton is a finite state machine with the ability to store and retrieve data from an infinite-memory queue. It is a model of computation equivalent to a Turing machine, and therefore it can process the same class of formal languages.

## Theory

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 -Sigma }$ is the initial queue symbol;
• ${displaystyle ,sin Q}$ is the start state;
• ${displaystyle ,delta :Qtimes Gamma rightarrow Qtimes Gamma ^{*}}$ is the transition function.

A machine configuration is an ordered pair of its state and queue contents ${displaystyle ,(q,gamma )in Qtimes 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,Aalpha )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 ,xin Sigma ^{*}}$ if after a finite number of transitions the starting configuration evolves to exhaust the string (reaching a null string ${displaystyle ,epsilon }$), or ${displaystyle ,(s,x)rightarrow _{M}^{*}(q,epsilon ).}$[1]

### Turing completeness

We can prove that a queue machine is equivalent to a Turing machine by showing that a queue machine can simulate a Turing machine and vice versa.

A Turing machine can be simulated by a queue machine that keeps a copy of the Turing machine's contents in its queue at all times, with two special markers: one for the TM's head position, and one for the end of the tape; its transitions simulate those of the TM by running through the whole queue, popping off each of its symbols and re-enqueing either the popped symbol, or, near the head position, the equivalent of the TM transition's effect.

A queue machine can be simulated by a Turing machine, but more easily by a multi-tape Turing machine, which is known to be equivalent to a normal single-tape machine. The simulating queue machine reads input on one tape and stores the queue on the second, with pushes and pops defined by simple transitions to the beginning and end symbols of the tape.[2] A formal proof of this is often an exercise in theoretical computer science courses.

## Applications

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

## References

1. ^ Kozen, Dexter C. (1997) [1951]. David Gries, Fred B. Schneider, ed. Automata and Computability (hardcover). Undergraduate Texts in Computer Science (1 ed.). New York: Springer-Verlag. pp. 368–370. ISBN 0-387-94907-0.
2. ^ Rus, Teodor. "Variants of Turing Machines" (PDF). Lecture Notes Covering Theory of Computation. University of Iowa, Iowa City, IA, 52242-1419. Archived from the original (PDF) on 2008-09-21. Retrieved 2007-11-06.
3. ^ Feller, M.; M.D. Ercegovac (1981). "Queue machines: An organization for parallel computation". Lecture Notes in Computer Science. 111: 37. doi:10.1007/BFb0105108. Retrieved 2007-11-06.
4. ^ Schmit, Herman; Benjamin Levine; Benjamin Ylvisaker (2002). "Queue Machines: Hardware Compilation in Hardware". 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'02): 152. doi:10.1109/FPGA.2002.1106670. Retrieved 2007-11-06.
5. ^ Moore, Christopher (1999-09-20). "Queues, Stacks, and Transcendentality at the Transition to Chaos". Algorithms Project's Seminar. INRIA. Retrieved 2007-11-06.
6. ^ von Thum, Manfred (2007). "A queue machine for evaluating expressions". LaTrobe University. Archived from the original on 2007-08-07. Retrieved 2007-11-06.

# Queue Automaton

Definitions by https://www.wiktionary.org/

Sorry Isnare.com is offline for a short while. Please check back after 5 minutes.