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. 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. Later in 1980, Davis used the name "Turing–Post program".

1936: Post model

In his 1936 paper "Finite Combinatory Processes—Formulation 1", 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 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" and "unmarked". 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", which are numbered in order. 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":
Specifically, the i th "direction" given to the worker is to be one of the following forms:
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

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 atomized the Turing 5-tuples to 4-tuples:
Like Turing he defined erasure as printing a symbol "S0". And so his model admitted quadruplets of only three types :
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 is often cited as the source of the "program formulation" of binary-tape Turing machines using numbered instructions from the set
where sequential execution is assumed, and Post's single "if... then... else" has been "atomised" into two "if... then..." statements.
Wang noted the following:
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's. Along with Stephen Kleene he completed his PhD under Alonzo Church.
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 :
Note that there is no "halt" or "stop".

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"
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:
"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 replaced with a definite number.".
"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."
This model allows for the printing of multiple symbols. The model allows for B 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.
Note that only one type of "jump" – a conditional GOTO – is specified; for an unconditional jump a string of GOTO's must test each symbol.
This model reduces to the binary versions presented above, as shown here:

Examples of the Post–Turing machine

Atomizing Turing quintuples into a sequence of Post–Turing instructions

The following "reduction" method – from 2-symbol Turing 5-tuples to a sequence of 2-symbol Post–Turing instructions – can be found in Minsky. He states that this reduction to "a program... a sequence of Instructions" is in the spirit of Hao Wang's B-machine.

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.
In the following example, each Turing 5-tuple of the 2-state busy beaver converts into
for a total of instructions per Turing-state.
For example, the 2-state busy beaver's "A" Turing-state, written as two lines of 5-tuples, is:
Initial m-configuration Tape symbolPrint operationTape motionFinal m-configuration
A0PRB
A1PLB

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". Turing observed that the left-two columns – "m-configuration" 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 m-configuration and symbol SPrint operationTape motionFinal m-configuration
S=0 -->P -->R -->B
--> A <
S=1 -->P -->L -->B

After the "configuration branch" or the machine follows one of the two subsequent "behaviors". We list these two behaviors on one line, and number them sequentially. Beneath each jump we place its jump-to "number" :
Initial m-configuration & symbol SPrint operationTape motionFinal m-configuration case S=0Print operationTape motionFinal m-configuration case S=1
If S=0 then:PRB
---> A <
If S=1 then:PLB
instruction #1234567
Post–Turing instructionJ1PRJPLJ
jump-to instruction #5BB

Per the Post–Turing machine conventions each of the Print, Erase, Left, and Right instructions consist of two actions:
And per the Post–Turing machine conventions the conditional "jumps" J0xxx, J1xxx consist of two actions:
And per the Post–Turing machine conventions the unconditional "jump" Jxxx consists of a single action, or if we want to regularize the 2-action sequence:
Which, and how many, jumps are necessary? The unconditional jump Jxxx is simply J0 followed immediately by J1. Wang 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.
but the use of all three does eliminate extra instructions. In the 2-state Busy Beaver example that we use only.

2-state busy beaver

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 writes a 0. The tape moves "Left" or "Right".
State table for a 2-state Turing-machine busy beaver:
Instructions for the Post–Turing version of a 2-state 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 #123456789101112131415
InstructionJ1PRJPLJJ1PLJPNJH
Jump-to #58812115
Turing-state labelABH

Alternately, we might write the table as a string. The use of "parameter separators" ":" and instruction-separators "," are entirely our choice and do not appear in the model. There are no conventions p. 374, and Boolos and Jeffrey, 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":
The state diagram of a two-state busy beaver converts to the equivalent Post–Turing machine with the substitution of 7 Post–Turing instructions per "Turing" state. The HALT instruction adds the 15th state:
A "run" of the 2-state busy beaver with all the intermediate steps of the Post–Turing machine shown:

Two state busy beaver followed by "tape cleanup"

The following is a two-state Turing busy beaver with additional instructions 15–20 to demonstrate the use of "Erase", J0, etc. These will erase the 1's written by the busy beaver:
Instruction #1234567891011121314151617181920
InstructionJ1PRJPLJJ1PLJPNJLJ0ERJ1H
Jump-to #588121152017
Turing-state labelAB*

Additional Post–Turing instructions 15 through 20 erase the symbols created by the busy beaver. These "atomic" instructions are more "efficient" than their Turing-state equivalents. To accomplish the same task a Post–Turing machine will require fewer Post–Turing states than a Turing-machine, because a jump can occur to any Post–Turing instruction within the Turing-state, a grouping of move-instructions such as L, L, L, P are possible, etc.:
Instruction #1617181920
InstructionJ0ERJ1H
Jump-to #2017

Example: Multiply 3 &times; 4 with a Post–Turing machine

This example is a reference to show how a "multiply" computation would proceed on a single-tape, 2-symbol Post–Turing machine model.
This particular "multiply" algorithm is recursive through two loops. The head moves. It starts to the far left of the string of unary marks representing a' :