Post–Turing machine
A Post–Turing machine[1] is a "program formulation" of a type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation. Post's model and Turing's model, though very similar to one another, were developed independently. Turing's paper was received for publication in May 1936, followed by Post's in October. A Post–Turing machine uses a binary alphabet, an infinite sequence of binary storage locations, and a primitive programming language with instructions for bi-directional movement among the storage locations and alteration of their contents one at a time. The names "Post–Turing program" and "Post–Turing machine" were used by Martin Davis in 1973–1974 (Davis 1973, p. 69ff). Later in 1980, Davis used the name "Turing–Post program" (Davis, in Steen p. 241).
1974: first Davis model[edit]
Martin Davis was an undergraduate student of Emil Post. Along with Stephen Kleene he completed his Ph.D. under Alonzo Church (Davis (2000) 1st and 2nd footnotes p. 188).
The following model he presented in a series of lectures to the Courant Institute at NYU in 1973–1974. This is the model to which Davis formally applied the name "Post–Turing machine" with its "Post–Turing language".[2] The instructions are assumed to be executed sequentially (Davis 1974, p. 71):
Examples of the Post–Turing machine[edit]
Atomizing Turing quintuples into a sequence of Post–Turing instructions[edit]
The following "reduction" (decomposition, atomizing) method – from 2-symbol Turing 5-tuples to a sequence of 2-symbol Post–Turing instructions – can be found in Minsky (1961). He states that this reduction to "a program ... a sequence of Instructions" is in the spirit of Hao Wang's B-machine (italics in original, cf. Minsky (1961) p. 439).
(Minsky's reduction to what he calls "a sub-routine" results in 5 rather than 7 Post–Turing instructions. He did not atomize Wi0: "Write symbol Si0; go to new state Mi0", and Wi1: "Write symbol Si1; go to new state Mi1". The following method further atomizes Wi0 and Wi1; in all other respects the methods are identical.)
This reduction of Turing 5-tuples to Post–Turing instructions may not result in an "efficient" Post–Turing program, but it will be faithful to the original Turing-program.
In the following example, each Turing 5-tuple of the 2-state busy beaver converts into