A Post–Turing machine is a "program formulation" of an especially simple type of Turing machine A Turing machine is a theoretical device that manipulates symbols contained on a strip of tape. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer. The "Turing" machine was described by Alan Turing in 193, comprising a variant of Emil Post Emil Leon Post, Ph.D., was a mathematician and logician's Turing-equivalent Turing completeness, named after Alan Turing, is significant in that every plausible design for a computing device so far advanced can be emulated by a universal Turing machine — an observation that has become known as the Church-Turing thesis. Thus, a machine that can act as a universal Turing machine can, in principle, perform any calculation model In the most general sense, a model is anything used in any way to represent anything else. Some models are physical objects, for instance, a toy model which may be assembled, and may even be made to work like the object it represents. However a conceptual model, may only be drawn on paper, described in words, or imagined in the mind. They are used of computation Computation is a general term for any type of process, algorithm or measurement; this often includes but is not limited to digital data. This includes phenomena ranging from human thinking to calculations with a more narrow meaning. Computation is a process following a well-defined model that is understood and can be expressed in an algorithm, 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 In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. Some examples are: sequence In mathematics, a sequence is an ordered list of objects . Like a set, it contains members (also called elements or terms), and the number of terms (possibly infinite) is called the length of the sequence. Unlike a set, order matters, and the exact same elements can appear multiple times at different positions in the sequence. A sequence is a of binary storage Computer data storage, often called storage or memory, refers to computer components, devices, and recording media that retain digital data used for computing for some interval of time. Computer data storage provides one of the core functions of the modern computer, that of information retention. It is one of the fundamental components of all locations, and a primitive programming language A programming language is an artificial language designed to express computations that can be performed by a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine, to express algorithms precisely, or as a mode of human communication 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 Martin David Davis, is an American mathematician, known for his work on Hilbert's tenth problem (Jackson 2008, p. 560). He received his Ph.D. from Princeton University in 1950, where his adviser was Alonzo Church (Jackson 2008, p. 560). He is Professor Emeritus at New York University. He is the co-inventor of the Davis-Putnam and the DPLL in 1973-1974 (Davis 1973, p.69ff). Later in 1980, Davis used the name "Turing-Post program" (Davis, in Steen p. 241).

Contents

1936: Post model

In his 1936 paper "Finite combinatory processes—formulation 1" (which can be found on page 289 of The Undecidable), Emil Post Emil Leon Post, Ph.D., was a mathematician and logician described a model of extreme simplicity which he conjectured is "logically equivalent Syntactically, p and q are equivalent if each can be proved from the other. Semantically, p and q are equivalent if they have the same truth value in every model 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 computationa[›].

Post's model employs a "symbol Mathematical logic is a subfield of mathematics with close connections to computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics. The unifying themes in mathematical logic include the study of the expressive power of formal systems and the 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 In mathematics, a finite set is a set that has a finite number of elements. For example,-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 In computer science, an instruction is a single operation of a processor defined by an instruction set architecture. In a broader sense, an "instruction" may be any representation of an element of an executable program, such as a bytecode), 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 In its simplest meaning in mathematics and logic, an operation is an action or procedure which produces a new value from one or more input values. There are two common types of operations: unary and binary. Unary operations involve only one value, such as negation and trigonometric functions. Binary operations, on the other hand, take two values,":

(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 [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".

1947: Post's formal reduction of the Turing 5-tuples to 4-tuples

As briefly mentioned in the article Turing machine A Turing machine is a theoretical device that manipulates symbols contained on a strip of tape. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer. The "Turing" machine was described by Alan Turing in 193, 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 p. 294 Undecidable):

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 4 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

where sequential execution Execution in computer and software engineering is the process by which a computer or a virtual machine carries out the instructions of a computer program. The instructions in the program trigger sequences of simple actions on the executing machine. Those actions produce effects according to the semantics of the instructions in the program is assumed, and Post's single "if ... then ... else In computer science, conditional statements, conditional expressions and conditional constructs are features of a programming language which perform different computations or actions depending on whether a programmer-specified boolean condition evaluates to true or false. Apart from the case of branch predication, this is always achieved by" 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.)

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 a undergraduate Undergraduate education is an education level taken prior to gaining a first degree , hence in many subjects in many educational systems, undergraduate education is post-secondary education up to the level of a bachelor's degree, such as in the United States, where a university entry level is known as undergraduate, while students of higher student of Emil Post's. Along with Stephen Kleene Stephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science. One of many distinguished students of Alonzo Church, Kleene, along with Alan Turing, Emil Post, and others, is best known as a founder of the branch of mathematical logic known as recursion theory. Kleene's work grounds the study of he completed his PhD under Alonzo Church Alonzo Church was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, Church–Turing thesis, Frege–Church ontology, and the Church–Rosser theorem (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):

"Write 1
"Write B
"To A if read 1
"To A if read B
"RIGHT
"LEFT

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" (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 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).

PRINT σ ;Replace scanned symbol with σ
IF σ GOTO L ;IF scanned symbol is σ THEN goto "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

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 { 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 goto "the first" instruction labelled L
IF 1 GOTO L ;IF scanned symbol is 1 THEN goto "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

Atomizing Turing quintuples into a sequence of Post-Turing instructions

The following "reduction" (decomposition, atomizing) method -- from 2-symbol Turing 5-tuples to a sequence of 2-symbol 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 B-machine (italics in original, cf Minsky (1961) p. 439).

(Minsky's reduction to what he calls "a sub-routine" 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 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

(i) an initial conditional "jump" (goto, branch), followed by
(ii) 2 tape-action instructions for the "0" case -- Print or Erase or None, followed by Left or Right or None, followed by
(iii) an unconditional "jump" for the "0" case to its next instruction
(iv) 2 tape-action instructions for the "1" case -- Print or Erase or None, followed by Left or Right or None, followed by
(v) an unconditional "jump" for the "1" case to its next instruction

for a total of 1+2+1+2+1= 7 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 (Turing state) Tape symbol Print operation Tape motion Final m-configuration (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 5-tuples, 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 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 S Print operation Tape motion Final m-configuration
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 jump-to "number" (address, location):

Initial m-configuration & symbol S Print operation Tape motion Final m-configuration case S=0 Print operation Tape motion Final m-configuration 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
jump-to instruction # 5 B B

Per the Post-Turing machine conventions each of the Print, Erase, Left, and Right instructions consist of two actions:

(i) Tape action: { P, E, L, R}, then
(ii) Table action: go to next instruction in sequence

And per the Post-Turing machine conventions the conditional "jumps" J0xxx, J1xxx consist of two actions:

(i) Tape action: look at symbol on tape under the head
(ii) 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 2-action sequence:

(i) Tape action: look at symbol on tape under the head
(ii) 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.

(i) { J0xxx, J1xxx }
(ii) { J1xxx, Jxxx }
(iii) { J0xxx, Jxxx },

but the use of all three { J0xxx, J1xxx, Jxxx } does eliminate extra instructions. In the 2-state Busy Beaver example that we use only { J1xxx, Jxxx }.

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 (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 2-state Turing-machine busy beaver:

Current state A: Current state B:
Write symbol: Move tape: Next state: Write symbol: Move tape: Next state:
tape symbol is 0: 1 R B 1 L A
tape symbol is 1: 1 L B 1 N H

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 #: 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
Jump-to #: 5 8 8 12 1 15
Turing-state label: A B H

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 (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

The state diagram of a two-state busy beaver (little drawing, right-hand corner) 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 #: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Instruction: J1 P R J P L J J1 P L J P N J L J0 E R J1 H
Jump-to #: 5 8 8 12 1 15 20 17
Turing-state label: A B *

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 (of 7 Post-Turing instructions). To accomplish the same task a Post-Turing machine will (usually) require fewer Post-Turing states than a Turing-machine, because (i) a jump (go-to) can occur to any Post-Turing instruction (e.g. P, E, L, R) within the Turing-state, (ii) a grouping of move-instructions such as L, L, L, P are possible, etc.:

Instruction #: 16 17 18 19 20
Instruction: J0 E R J1 H
Jump-to #: 20 17

Example: Multiply 3 x 4 with a Post-Turing machine

An example of "multiply" a x b = c on a Post-Turing machine. At the start, the tape (shown on the left) has two numbers on it -- a' = 3' (4 marks), b' = 4' (5 marks). (A single mark would represent "0".) At the end the tape will have the product c' = 12' (13 marks) to the right of b. Note "top" and "bottom" are there just to clarify what the P-T machine is doing.

This example is a reference to show how a "multiply" computation would proceed on a single-tape, 2-symbol { blank, 1 } Post-Turing machine model.

This particular "multiply" algorithm is recursive through two loops. The head moves. It starts to the far left (the top) of the string of unary marks representing a' :

  • Move head far right. Establish (i.e. "clear") register c by placing a single blank and then a mark to the right of b
  • a_loop: Move head right once, test for the bottom of a' (a blank). If blank then done else erase mark;
  • Move head right to b' . Move head right once past the top mark of b' ;
  • b_loop: If head is at the bottom of b' (a blank) then move head to far left of a' , else:
  • Erase a mark to locate counter (a blank) in b' .
  • Increment c' : Move head right to top of c' and increment c' .
  • Move head left to the counter inside b' ,
  • Repair counter: print a mark in the blank counter.
  • Decrement b' -count: Move head right once.
  • Return to b_loop.
Multiply a x b = c, for example: 3 x 4 = 12. The scanned square is indicated by brackets around the mark i.e. [ | ]. An extra mark serves to indicate the symbol "0":
At the start of the computation a' is 4 unary marks, then a separator blank, b' is 5 unary marks, then a separator mark. An unbounded number of empty spaces must be available for c to the right:
....a'.b'.... = : ....[ | ] | | | . | | | | | ....
During the computation the head shuttles back and forth from a' to b' to c' back to b' then to c' , then back to b' , then to c' ad nauseam Ad nauseam is a Latin term used to describe an argument which has been continuing "to [the point of] nausea". For example, the sentence "This topic has been discussed ad nauseam" signifies that the topic in question has been discussed extensively and that those involved in the discussion are sick and tired of it while the machine counts through b' and increments c' . Multiplicand a' is slowly counted down (its marks erased -- shown for reference with x's below). A "counter" inside b' moves to the right through b (an erased mark shown being read by the head as [ . ] ) but is reconstructed after each pass when the head returns from incrementing c' :
....a.b.... = : ....xxx | . | | [ . ] | | . | | | | | | | ...
At end of computation: c' is 13 marks = "successor of 12" appearing to the right of b' . a' has vanished in process of the computation
....b.c = ......... | | | | | . | | | | | | | | | | | | | ...

Footnotes

^ a: Difference between Turing- and Post-Turing machine models

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 2-way 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 (time-sequential) actions specified on a line in a Turing table: (i) print-symbol/erase/do-nothing followed by (ii) move-tape-left/move-tape-right/do-nothing followed by (iii) test-tape-go-to-next-instruction: 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 3-actions further into two types of 2-actions. The first type is a "print/erase" action, the second is a "move tape left/right action": (1.i) print-symbol/erase/do-nothing followed by (1.ii) test-tape-go-to-next-instruction, OR (2.ii) move-tape-left/move-tape-right/do-nothing followed by (2.ii) test-tape-go-to-next-instruction.

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 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)

In fact Post's treatment (1936) is ambiguous; both (1.1) and (2.1) could be followed by "(.ii) go to next instruction in numerical sequence". This represents a further atomization into three types of instructions: (1) print-symbol/erase/do-nothing then go-to-next-instruction-in-numerical-sequence, (2) move-tape-left/move-tape-right/do-nothing then go-to-next-instruction-in-numerical-sequence (3)test-tape then go-to-instruction-xxx-else-go-to-next-instruction-in-numerical-sequence.

References

Categories: Recursion theory | Computational models The category of Computational Models lists abstract models for investigating computing machines. Standard computational models assume discrete time paradigm

 

The above information uses material from Wikipedia and is licensed under the GNU Free Documentation License The purpose of this License is to make a manual, textbook, or other functional and useful document "free" in the sense of freedom: to assure everyone the effective freedom to copy and redistribute it, with or without modifying it, either commercially or noncommercially. Secondarily, this License preserves for the author and publisher a.
Some facts may not have been fully verified for accuracy. [Disclaimers Wikipedia is an online open-content collaborative encyclopedia, that is, a voluntary association of individuals and groups working to develop a common resource of human knowledge. The structure of the project allows anyone with an Internet connection to alter its content. Please be advised that nothing found here has necessarily been reviewed by]
This page was last archived by our server on Sat Jul 31 02:34:32 2010. [ refresh local cache ]
Displaying this page or its contents does not use any Wikimedia Foundation's resources.
The owners of this site proudly support the Wikimedia Foundation.

[Hide]▼
'Formulation 1' Blogs
Diagnostic formulation Kuruvilla K, Kuruvilla A - Indian J Psychiatry
indianjpsychiatry.org
Diagnostic formulation Kuruvilla K, Kuruvilla A - Indian J Psychiatry

Kuruvilla K, Kuruvilla Anju

Wed, 07 Apr 2010 00:17:57 GM

Psychiatrists at various levels of seniority working in a teaching hospital were asked to list what should be included in a diagnostic . formulation. . The results are shown in [Table . 1. ]. The following three points are striking-firstl​y, ...

Google Blogs Search: Formulation 1,
Sun Jul 4 04:06:14 2010
[Hide]▲