Gourt Home::Gourt :: Post-Turing machine
A Post-Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation described below. (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 of 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).
Post model
In his 1936 paper "Finite combinatory processes—formulation 1" (which can be found on page 289 of The Undecidable), Emil Post described a model of extreme simplicity which he conjectured is "logically equivalent to recursiveness", and which was later proved to be so. The quotes in the following are from this paper.
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.
The instructions may require the worker to perform the following "basic acts" or "operations":
- (a) Marking the box he is in (assumed empty),
- (b) Erasing the mark in the box he is in (assumed marked),
- (c) Moving to the box on his right,
- (d) Moving to the box on his left,
- (e) Determining whether the box he is in, is or is not marked.
Specifically, the i th "direction" (instruction) given to the worker is to be one of the following forms:
- (A) Perform operation Oi = (a), (b), (c) or (d) and then follow direction ji,
- (B) Perform operation (e) and according as the answer is yes or no correspondingly follow direction ji' or ji' ' ,
- (C) Stop.
(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
- (1) 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",
- (2) using an alphabet of more than two symbols, "having more than one way to mark a box",
- (3) introducing finitely-many "physical objects to serve as pointers, which the worker can identify and move from box to box".
Davis model # 1
Martin Davis was a undergraduate student of Emil Post's (cf Davis in Steen, p. 260) and, as a professor himself, carried on Post's traditions: Like Post he regarded computation as an act of "a human calculator". The following model can be found in What is a Computation?, an essay in Mathematics Today: Twelve Informal Essays (Davis in Steen, p. 241ff).
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
- Confusion arises if one does not realize that a "blank" tape is actually printed with all zeroes — there is no "blank".
- Splits Post's "GO TO" ("branch" or "jump") instruction into two, thus creating a larger (but easier-to-use) instruction set of seven rather than Post's six instructions.
- Does not mention that instructions PRINT 1, PRINT 0, GO RIGHT and GO LEFT imply that, after execution, the "computer" must go to the next step in numerical sequence.
Davis model #2
This is Davis's earlier model (Davis 1974, p. 69):
- "Write 1
- "Write B
- "To A if read 1
- "To A if read B
- "RIGHT
- "LEFT
Wang model
Wang (1957), with credit to Post, is often cited 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
where sequential execution is assumed, and Post's single "if ... then ... else" has been "atomised" into two "if ... then ..." statements. (Here '1' and '0' are used where Wang used "marked" and "unmarked", respectively, and the initial tape is assumed to contain only '0's except for finitely-many '1's.) In fact, Wang showed that — without loss of Turing-completeness — this set of instructions can be further reduced in various ways. For example, the first and fifth of the above instructions can be omitted, reducing the set of instructions to
- write 1
- move left
- move right
- if scanning 1 then goto instruction i
Wang noted that in his instruction sets, "... there is no separate instruction for halt (stop) ...", and that – unlike the Turing machine with a one-way infinite tape – "... we are following Post in the use of a 2-way infinite tape." (p. 65)
In any case, this is so close to Post that it seems quite appropriate to regard these as "Post-Turing" programs.
References
- Martin Davis, editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. Papers include those by Godel, Church, Rosser, Kleene, and Post.
- Martin Davis, "What is a computation", in Mathematics Today, Lynn Arthur Steen, Vintage Books (Random House), 1980. A wonderful little paper, perhaps the best ever written about Turing Machines. Davis reduces the Turing Machine to a far-simpler model based on Post's model of a computation. Includes a little biography of Emil Post.
- Martin Davis, Computability: with Notes by Barry Jacobs, Courant Institute of Mathematical Sciences, New York University, 1974.
- Roger Penrose, The Emperor's New Mind: Concerning computers, Minds and the Laws of Physics, Oxford University Press, Oxford England, 1990 (with corrections). Cf: Chapter 2, "Algorithms and Turing Machines". An overly-complicated presentation (see Davis's paper for a better model), but a thorough presentation of Turing machines and the halting problem, and Church's lambda calculus.
- Fred Hennie, Introduction to Computability, Addison-Wesley, 1977.
- Hao Wang (1957): "A variant to Turing's theory of computing machines", Journal of the Association for Computing Machinery (JACM) 4, 63-92.
Recursion theory | Computational models | Formal methods | Programming languages
"Post-Turing machine"