Post–Turing machine
From Wikipedia the free encyclopedia
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)

A Post–Turing machine^{[1]} is a "program formulation" of a type of Turing machine, comprising a variant of Emil Post's Turingequivalent 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 bidirectional 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[edit]
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 Turingmachine model in a further "atomization" of the acts a human "computer" would perform during a computation.^{[2]}
Post's model employs a "symbol space" consisting of a "twoway 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, finitelymany 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:
 Perform operation O_{i} [O_{i} = (a), (b), (c) or (d)] and then follow direction j_{i}
 Perform operation (e) and according as the answer is yes or no correspondingly follow direction j_{i}′ or j_{i}″
 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
 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 finitelymany "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 5tuples to 4tuples[edit]
As briefly mentioned in the article Turing machine, Post, in his paper of 1947 (Recursive Unsolvability of a Problem of Thue) atomized the Turing 5tuples to 4tuples:
 "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):
 q_{i} S_{j} L q_{l},
 q_{i} S_{j} R q_{l},
 q_{i} S_{j} S_{k} q_{l}
At this time he was still retaining the Turing statemachine 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[edit]
For an even further reduction – to only four instructions – of the Wang model presented here see Wang Bmachine.
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 binarytape 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 binarytape Turing machine is readily converted to an equivalent "Wang program" using the above instructions.
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):
1978: second Davis model[edit]
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 backsliding 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[edit]
"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 S_{0}. 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).
 PRINT σ ;Replace scanned symbol with σ
 IF σ GOTO L ;IF scanned symbol is σ THEN go to "the first" instruction labelled L
 RIGHT ;Scan square immediately right of the square currently scanned
 LEFT ;Scan square immediately left of the square currently scanned
This model reduces to the binary { 0, 1 } versions presented above, as shown here:
 PRINT 0 = ERASE ;Replace scanned symbol with 0 = B = BLANK
 PRINT 1 ;Replace scanned symbol with 1
 IF 0 GOTO L ;IF scanned symbol is 0 THEN go to "the first" instruction labelled L
 IF 1 GOTO L ;IF scanned symbol is 1 THEN go to "the first" instruction labelled L
 RIGHT ;Scan square immediately right of the square currently scanned
 LEFT ;Scan square immediately left of the square currently scanned
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 2symbol Turing 5tuples to a sequence of 2symbol 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 Bmachine (italics in original, cf. Minsky (1961) p. 439).
(Minsky's reduction to what he calls "a subroutine" 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 5tuples to Post–Turing instructions may not result in an "efficient" Post–Turing program, but it will be faithful to the original Turingprogram.
In the following example, each Turing 5tuple of the 2state busy beaver converts into
 an initial conditional "jump" (goto, branch), followed by
 2 tapeaction instructions for the "0" case – Print or Erase or None, followed by Left or Right or None, followed by
 an unconditional "jump" for the "0" case to its next instruction
 2 tapeaction instructions for the "1" case – Print or Erase or None, followed by Left or Right or None, followed by
 an unconditional "jump" for the "1" case to its next instruction
for a total of 1 + 2 + 1 + 2 + 1 = 7 instructions per Turingstate.
For example, the 2state busy beaver's "A" Turingstate, written as two lines of 5tuples, is:
Initial mconfiguration (Turing state)  Tape symbol  Print operation  Tape motion  Final mconfiguration (Turing state) 

A  0  P  R  B 
A  1  P  L  B 
The table represents just a single Turing "instruction", but we see that it consists of two lines of 5tuples, one for the case "tape symbol under head = 1", the other for the case "tape symbol under head = 0". Turing observed (Undecidable, p. 119) that the lefttwo columns – "mconfiguration" and "symbol" – represent the machine's current "configuration" – its state including both Tape and Table at that instant – and the last three columns are its subsequent "behavior". As the machine cannot be in two "states" at once, the machine must "branch" to either one configuration or the other:
Initial mconfiguration and symbol S  Print operation  Tape motion  Final mconfiguration 

S=0 →  P →  R →  B 
→ A <  
S=1 →  P →  L →  B 
After the "configuration branch" (J1 xxx) or (J0 xxx) the machine follows one of the two subsequent "behaviors". We list these two behaviors on one line, and number (or label) them sequentially (uniquely). Beneath each jump (branch, go to) we place its jumpto "number" (address, location):
Initial mconfiguration & symbol S  Print operation  Tape motion  Final mconfiguration case S=0  Print operation  Tape motion  Final mconfiguration case S=1  

If S=0 then:  P  R  B  
→ A <  
If S=1 then:  P  L  B  
instruction #  1  2  3  4  5  6  7 
Post–Turing instruction  J1  P  R  J  P  L  J 
jumpto instruction #  5  B  B 
Per the Post–Turing machine conventions each of the Print, Erase, Left, and Right instructions consist of two actions:
 Tape action: {P, E, L, R}, then
 Table action: go to next instruction in sequence
And per the Post–Turing machine conventions the conditional "jumps" J0xxx, J1xxx consist of two actions:
 Tape action: look at symbol on tape under the head
 Table action: If symbol is 0 (1) and J0 (J1) then go to xxx else go to next instruction in sequence
And per the Post–Turing machine conventions the unconditional "jump" Jxxx consists of a single action, or if we want to regularize the 2action sequence:
 Tape action: look at symbol on tape under the head
 Table action: If symbol is 0 then go to xxx else if symbol is 1 then go to xxx.
Which, and how many, jumps are necessary? The unconditional jump Jxxx is simply J0 followed immediately by J1 (or vice versa). Wang (1957) also demonstrates that only one conditional jump is required, i.e. either J0xxx or J1xxx. However, with this restriction, the machine becomes difficult to write instructions for. Often only two are used, i.e.
 { J0xxx, J1xxx }
 { J1xxx, Jxxx }
 { J0xxx, Jxxx },
but the use of all three { J0xxx, J1xxx, Jxxx } does eliminate extra instructions. In the 2state Busy Beaver example that we use only { J1xxx, Jxxx }.
2state busy beaver[edit]
The mission of the busy beaver is to print as many ones as possible before halting. The "Print" instruction writes a 1, the "Erase" instruction (not used in this example) writes a 0 (i.e. it is the same as P0). The tape moves "Left" or "Right" (i.e. the "head" is stationary).
State table for a 2state Turingmachine busy beaver:
Tape symbol  Current state A  Current state B  

Write symbol  Move tape  Next state  Write symbol  Move tape  Next state  
0  1  R  B  1  L  A 
1  1  L  B  1  N  H 
Instructions for the Post–Turing version of a 2state busy beaver: observe that all the instructions are on the same line and in sequence. This is a significant departure from the "Turing" version and is in the same format as what is called a "computer program":
Instruction #  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 

Instruction  J1  P  R  J  P  L  J  J1  P  L  J  P  N  J  H 
Jumpto #  5  8  8  12  1  15  
Turingstate label  A  B  H 
Alternately, we might write the table as a string. The use of "parameter separators" ":" and instructionseparators "," are entirely our choice and do not appear in the model. There are no conventions (but see Booth (1967) p. 374, and Boolos and Jeffrey (1974, 1999) p. 23), for some useful ideas of how to combine state diagram conventions with the instructions – i.e. to use arrows to indicate the destination of the jumps). In the example immediately below, the instructions are sequential starting from "1", and the parameters/"operands" are considered part of their instructions/"opcodes":
 J1:5, P, R, J:8, P, L, J:8, J1:12, P, L, J1:1, P, N, J:15, H
Notes[edit]
 ^ Rajendra Kumar, Theory of Automata, Tata McGrawHill Education, 2010, p. 343.
 ^ ^{a} ^{b} In his chapter XIII Computable Functions, Kleene adopts the Post model; Kleene's model uses a blank and one symbol "tally mark ¤" (Kleene p. 358), a "treatment closer in some respects to Post 1936. Post 1936 considered computation with a 2way infinite tape and only 1 symbol" (Kleene p. 361). Kleene observes that Post's treatment provided a further reduction to "atomic acts" (Kleene p. 357) of "the Turing act" (Kleene p. 379). As described by Kleene "The Turing act" is the combined 3 (timesequential) actions specified on a line in a Turing table: (i) printsymbol/erase/donothing followed by (ii) movetapeleft/movetaperight/donothing followed by (iii) testtapegotonextinstruction: e.g. "s1Rq1" means "Print symbol "¤", then move tape right, then if tape symbol is "¤" then go to state q1". (See Kleene's example p. 358.) Kleene observes that Post atomized these 3actions further into two types of 2actions. The first type is a "print/erase" action, the second is a "move tape left/right action": (1.i) printsymbol/erase/donothing followed by (1.ii) testtapegotonextinstruction, OR (2.ii) movetapeleft/movetaperight/donothing followed by (2.ii) testtapegotonextinstruction. But Kleene observes that while
 "Indeed it could be argued that the Turing machine act is already compound, and consists psychologically in a printing and change in the state of mind, followed by a motion and another state of mind [, and] Post 1947 does thus separate the Turing act into two; we have not here, primarily because it saves space in the machine tables not to do so."(Kleene p. 379)
References[edit]
 Stephen C. Kleene, Introduction to MetaMathematics, NorthHolland Publishing Company, New York, 10th edition 1991, first published 1952. Chapter XIII is an excellent description of Turing machines; Kleene uses a Postlike model in his description and admits the Turing model could be further atomized, see footnote 1.
 Martin Davis, editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven Press, New York, 1965. Papers include those by Gödel, 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 farsimpler 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.
 Martin Davis, Ron Sigal, Elaine J. Weyuker, (1994) Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science – 2nd edition, Academic Press: Harcourt, Brace & Company, San Diego, 1994 ISBN 0122063821 (First edition, 1983).
 Fred Hennie, Introduction to Computability, Addison–Wesley, 1977.
 Marvin Minsky, (1961), Recursive Unsolvability of Post's problem of 'Tag' and other Topics in Theory of Turing Machines, Annals of Mathematics, Vol. 74, No. 3, November, 1961.
 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 overcomplicated 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.
 Hao Wang (1957): "A variant to Turing's theory of computing machines", Journal of the Association for Computing Machinery (JACM) 4, 63–92.