HOME

TheInfoList



OR:

A queue machine, queue automaton, or pullup automaton (PUA) is a
finite-state machine A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
with the ability to store and retrieve data from an infinite-memory queue. Its design is similar to a
pushdown automaton In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack. Pushdown automata are used in theories about what can be computed by machines. They are more capab ...
but differs by replacing the stack with this queue. A queue machine is a model of computation equivalent to a
Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
, and therefore it can process the same class of
formal language In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet". The alphabet of a formal language consists of symbols that concatenate into strings (also c ...
s.


Theory

A queue machine can be defined as a six-tuple :M = (Q, \Sigma, \Gamma, \$, s, \delta) where * \,Q is a finite set of ''states''; * \,\Sigma \subset \Gamma is the finite set of the ''input alphabet''; * \,\Gamma is the finite ''queue alphabet''; * \,\$ \in \Gamma \setminus \Sigma is the ''initial queue symbol''; * \,s \in Q is the ''start state''; * \,\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 \,(q,\gamma)\in Q\times\Gamma^*, where \,\Gamma^* denotes the
Kleene closure In mathematical logic and theoretical computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation on a set to generate a set of all finite-length strings that are composed of zero or more repetitions of members ...
of \,\Gamma. The starting configuration on an input string \,x is defined as \,(s,x\$), and the transition \rightarrow_M^1 from one configuration to the next is defined as: :\,(p,A\alpha) \rightarrow_M^1 (q,\alpha\gamma) where A is a symbol from the queue alphabet, \alpha is a sequence of queue symbols (\alpha \in \Gamma^*), and (q, \gamma) = \delta(p, A). Note the "first-in-first-out" property of the queue in the relation. The machine accepts a string \,x\in\Sigma^* if after a finite number of transitions the starting configuration evolves to exhaust the string (reaching the null string \,\epsilon), or otherwise stated, if \,(s,x\$)\rightarrow_M^*(q,\epsilon).


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 Turing machine's head position, and one for the end of the tape; its transitions simulate those of the Turing machine 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 Turing machine 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. 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 In computer science and computer engineering, computer architecture is a description of the structure of a computer system made from component parts. It can sometimes be a high-level description that ignores details of the implementation. At a mo ...
,
programming languages A programming language is a system of notation for writing computer programs. Programming languages are described in terms of their syntax (form) and semantics (meaning), usually defined by a formal language. Languages usually provide features ...
, or
algorithms In mathematics and computer science, an algorithm () is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for per ...
.


See also

*
Computability Computability is the ability to solve a problem by an effective procedure. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is c ...
*
Turing machine equivalents A Turing machine is a hypothetical computing device, first conceived by Alan Turing in 1936. Turing machines manipulate symbols on a potentially infinite strip of tape according to a finite table of rules, and they provide the theoretical underp ...
*
Deterministic finite automaton In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state auto ...
*
Tag system In the theory of computation, a tag system is a deterministic model of computation published by Emil Leon Post in 1943 as a simple form of a Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine ( ...

Manufactoria
a browser flash game tasking the player with implementation of various algorithms using a queue machine model.


References

{{DEFAULTSORT:Queue Machine Automata (computation) Models of computation