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
:
where
*
is a finite set of ''states'';
*
is the finite set of the ''input alphabet'';
*
is the finite ''queue alphabet'';
*
is the ''initial queue symbol'';
*
is the ''start state'';
*
is the ''transition function''.
A machine ''configuration'' is an ordered pair of its state and queue contents
, where
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
. The starting configuration on an input string
is defined as
, and the transition
from one configuration to the next is defined as:
:
where
is a symbol from the queue alphabet,
is a sequence of queue symbols (
), and
. Note the "first-in-first-out" property of the queue in the relation.
The machine accepts a string
if after a finite number of transitions the starting configuration evolves to exhaust the string (reaching the null string
), or otherwise stated, if
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