Post machine

In theoretical computer science and recursion theory, a Post machine is a deterministic finite automaton with a queue. There is no separate input tape.

At the start of the computation, the input string x is loaded on the queue. The input string is followed by a special symbol Zo. At the start of the computation, the contents of the queue are xZo. The first symbol of x is at the front of the queue and Zo is at the end of the queue. A transition of a Post machine depends on the symbol at the front of the queue and on the state. Each transition will delete the symbol at the front of the queue. A transition has two components: the next state and the string to be added at the end of the queue. This string can be the empty string.