replacing the infinity of boxes by a finite extensible symbol space, "extending the primitive operations to allow for the necessary extension of the given finite symbol space as the process proceeds", using an alphabet of more than two symbols, "having more than one way to mark a box", introducing finitely-many "physical objects to serve as pointers, which the worker can identify and move from box to box". 1947: Post's formal reduction of the Turing 5-tuples to 4-tuples As briefly mentioned in the article Turing machine, Post, in his paper of 1947 (Recursive Unsolvability of a Problem of Thue) atomized the Turing 5-tuples to 4-tuples: "Our quadruplets are quintuplets in the Turing development. That is, where our standard instruction orders either a printing (overprinting) or motion, left or right, Turing's standard instruction always order a printing and a motion, right, left, or none" (footnote 12, Undecidable, p. 300) Like Turing, he defined erasure as printing a symbol "S0". And so his model admitted quadruplets of only three types (cf. Undecidable, p. 294): qi Sj L ql, qi Sj R ql, qi Sj Sk ql At this time he was still retaining the Turing state-machine convention – he had not formalized the notion of an assumed sequential execution of steps until a specific test of a symbol "branched" the execution elsewhere. 1954, 1957: Wang model For an even further reduction – to only four instructions – of the Wang model presented here see Wang B-machine. Wang (1957, but presented to the ACM in 1954) is often cited (cf. Minsky (1967), p. 200) as the source of the "program formulation" of binary-tape Turing machines using numbered instructions from the set write 0 write 1 move left move right if scanning 0 then goto instruction i if scanning 1 then goto instruction j Any binary-tape Turing machine is readily converted to an equivalent "Wang program" using the above instructions. 1974: first Davis model 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". The instructions are assumed to be executed sequentially (Davis 1974, p. 71): 1978: second Davis model The following