Post machine
|
|
In theoretical computer science and recursion theory, a Post machine, named after Emil Leon Post, 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.
References
- V.A.Uspensky, "A Post Machine" (in Russian), Moscow, "Nauka", 1979.
External links
- C++ Simulator of a Nondeterministic and Deterministic Multitape Post Machine (http://semillon.wpi.edu/~aofa/AofA/msg00021.html) (free software).