Post–Turing machine

A Post–Turing machine computes by repeatedly applying a finite program to the symbol currently scanned on an unbounded tape. The tape is divided into discrete cells, commonly containing a mark or a blank, and a head can read, write, and move one cell left or right. The program consists of numbered instructions that may print or erase a mark, move the head, test the scanned cell, transfer control to another instruction, or halt.

At any moment, the machine’s complete configuration is determined by its tape contents, head position, and current instruction. A computation is the sequence of configurations produced from an initial arrangement. Input is conventionally encoded on a finite portion of the tape, while unused cells are blank; output may be left on the tape when the machine halts.¹

The Post–Turing machine emerged from Emil Post’s independent 1936 analysis of finite combinatory processes. Post described a worker carrying out elementary operations on a potentially endless sequence of marked spaces, with decisions governed by a finite set of instructions. Alan Turing’s contemporaneous model used a more explicitly defined machine with internal states and a tape alphabet, but the two descriptions capture the same underlying idea of effective symbolic calculation.²

The difference is chiefly one of presentation. Post’s formulation emphasizes a small list of primitive commands and conditional transfers, whereas the conventional Turing machine emphasizes states and transition rules. A compiler-like translation can replace each Post instruction with a finite collection of state transitions, and the reverse translation is also possible. Neither model gains computational abilities unavailable to the other.³

A Post–Turing machine can compute exactly the functions and recognize exactly the languages computable by a standard Turing machine. This equivalence places it among the formal models used to define computability, alongside recursive functions, lambda calculus, and register machines. The equivalence concerns what can be computed in principle, not how quickly a computation runs; different encodings and translations can impose substantial overhead.

Its finite program and unbounded tape make the model suitable for proving limits as well as capabilities. There are precisely describable problems for which no Post–Turing machine can halt with the correct answer on every input, including the halting problem. Such results support the Church–Turing thesis, which connects these formal models with the broader informal notion of an effectively calculable procedure, although the thesis itself is not a theorem about an independently formalized physical concept.¹⁴

The name covers a family of closely related presentations rather than one universally fixed instruction set. Some versions use only a binary tape alphabet and separate commands for marking, erasing, moving, and branching; others package writing and movement into conditional instructions. These variations remain equivalent when they have finite control and an unbounded tape, but they should not be confused with Post’s tag systems, which are different string-rewriting models.

Post’s work also helped establish the importance of reducing computation to very small primitive operations. His 1936 paper presented a formulation before the later terminology of programming languages and stored-program computers had become standard. Post–Turing machines therefore function both as historical artifacts and as convenient teaching models: their commands resemble assembly instructions, while their tape makes questions about undecidability and formal specification visible at the smallest scale.

finite control

The bounded part of a machine that stores its current instruction or state and determines the next operation.

tape alphabet

The finite set of symbols that may occur in tape cells, usually including a designated blank symbol.

configuration

A complete description of the tape, head location, and current instruction at one stage of a computation.

halting problem

The problem of determining, for arbitrary programs and inputs, whether the computation eventually stops; it is undecidable for Turing-equivalent models.

tag system

A string-rewriting formalism introduced by Emil Post, distinct from a Post–Turing machine despite the shared historical association.