---
title: Post–Turing machine
slug: post-turing-machine
qid: 
snapshot: enwiki-001345557172
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1345557172
tags: [11060667, 20476792, 22929052, 22977384, 23010699, 23017536, 23603337, 24043274, 24745119, 24745121, 26220375, 26748027, 28493675, 29265121]
---

# Post–Turing machine

> [!note] Provenance
> Snapshot `enwiki-001345557172` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1345557172> · Licensed CC BY-SA 4.0

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

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.&nbsp;69ff). Later in 1980, Davis used the name "Turing–Post program" (Davis, in Steen p.&nbsp;241). 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 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.&nbsp;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: 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): 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 (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. 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 }.
