IT lexicon › Programming › Post–Turing machine

Post–Turing machine

Programming På svenska → Updated: 2026-08-07

Emil Post's 1936 model of computation: a worker moving between boxes in an infinite row, following a numbered list of instructions — the same idea as Turing's, published the same year, independently.

Post described a "worker" in a room containing an infinite sequence of boxes, each either marked or unmarked. There were five instructions: mark the box, unmark it, move one box right, move one box left, branch on whether the box is marked. Each instruction names the number of the next one. That is a program in the modern sense — a numbered list with jumps — where Turing's machine expresses the same content as a state table.

Finite Combinatory Processes — Formulation 1 reached the Journal of Symbolic Logic only months after Turing's paper, and Post had to add a note in proof stating that the work was independent. The difference in reputation is that Post stopped at the model while Turing went on to prove what it cannot do. Post had already come close to the incompleteness theorems back in 1921 without publishing. The name "Post–Turing machine" was coined much later by Martin Davis.

← Back to the lexicon