Queue automaton
A queue machine, queue automaton, or pullup automaton (PUA) 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

 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 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, programming languages, or algorithms. See also 
 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. References 

Automata (computation)
Models of computation