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).
Emil Leon Post (February 11, 1897 - April 21, 1954) was a Polish-American mathematician and logician.
In his Columbia University doctoral thesis, he proved, among other things, that the propositional calculus of Principia Mathematica was complete: all tautologies are theorems, given the Principia axioms and a rule of uniform substitution.
His Post correspondence problem contributed to the decision problems of recursion theory, as a new model of computation.
Feeds |
Contact