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.
In his 1936 paper "Finite Combinatory Processes—Formulation 1", Emil Post described a model of which he conjectured is "logically equivalent to recursiveness".
[2] Post's model employs a "symbol space" consisting of a "two-way infinite sequence of spaces or boxes", each box capable of being in either of two possible conditions, namely "marked" (as by a single vertical stroke) and "unmarked" (empty).
Minsky (1967), p. 200) as the source of the "program formulation" of binary-tape Turing machines using numbered instructions from the set Any binary-tape Turing machine is readily converted to an equivalent "Wang program" using the above instructions.
[2] The instructions are assumed to be executed sequentially (Davis 1974, p. 71): The following model appears as an essay What is a computation?
Of course, in an actual program, the letter i in a step of either the fifth or sixth kind must be replaced with a definite (positive whole) number."
Either the head or the tape moves, but their definitions of RIGHT and LEFT always specify the same outcome in either case (Turing used the same convention).
This model reduces to the binary { 0, 1 } versions presented above, as shown here: 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.
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.
For example, the 2-state busy beaver's "A" Turing-state, written as two lines of 5-tuples, is: The table represents just a single Turing "instruction", but we see that it consists of two lines of 5-tuples, one for the case "tape symbol under head = 1", the other for the case "tape symbol under head = 0".
This is a significant departure from the "Turing" version and is in the same format as what is called a "computer program": Alternately, we might write the table as a string.