A Post machine or Post–Turing machine 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).
1936: Post model In his 1936 paper "Finite Combinatory Processes—Formulation 1", Emil Post described a model of which he conjectured is "logically equivalent to recursiveness". Post's model of a computation differs from the Turing-machine model in a further "atomization" of the acts a human "computer" would perform during a computation. 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). Initially, finitely-many of the boxes are marked, the rest being unmarked. A "worker" is then to move among the boxes, being in and operating in only one box at a time, according to a fixed finite "set of directions" (instructions), which are numbered in order (1,2,3,...,n). Beginning at a box "singled out as the starting point", the worker is to follow the set of instructions one at a time, beginning with instruction 1. There are five different primitive operations that the worker can perform:
(a) Marking the box it is in, if it is empty (b) Erasing the mark in the box it is in, if it is marked (c) Moving to the box on its right (d) Moving to the box on its left (e) Determining whether the box it is in, is or is not marked. Then, the i th "direction" (instruction) given to the worker is to be one of the following forms:
(The above indented text and italics are as in the original.) Post remarks that this formulation is "in its initial stages" of development, and mentions several possibilities for "greater flexibility" in its final "definitive form", including
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
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 go to instruction i if scanning 1 then go to 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 model appears as an essay What is a computation? in Steen pages 241–267. For some reason Davis has renamed his model a "Turing–Post machine" (with one back-sliding on page 256.) In the following model, Davis assigns the numbers "1" to Post's "mark/slash" and "0" to the blank square. To quote Davis: "We are now ready to introduce the Turing–Post Programming Language. In this language there are seven kinds of instructions:
"PRINT 1 "PRINT 0 "GO RIGHT "GO LEFT "GO TO STEP i IF 1 IS SCANNED "GO TO STEP i IF 0 IS SCANNED "STOP "A Turing–Post program is then a list of instructions, each of which is of one of these seven kinds. 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." (Davis in Steen, p. 247).
1994 (2nd edition): Davis–Sigal–Weyuker's Post–Turing program model "Although the formulation of Turing we have presented is closer in spirit to that originally given by Emil Post, it was Turing's analysis of the computation that has made this formulation seem so appropriate. This language has played a fundamental role in theoretical computer science." (Davis et al. (1994) p. 129) This model allows for the printing of multiple symbols. The model allows for B (blank) instead of S0. The tape is infinite in both directions. 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).
… excerpt ends here. Continue reading the full article.
