Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Post machines

Post machines are a simple, Turing-equivalent model of computation (Emil Post) that uses a tape and a small set of instruction types to study computability and reductions.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Post machines give an alternative, low-level model of computation equivalent to Turing machines. Engineers use them when studying computability, reductions and undecidability proofs, and when converting high-level algorithms into minimal instruction sets for theoretical analysis (for example, when proving a problem is undecidable by reducing to a Post system or a tag system).

Key ideas

We build Post machines from very basic terms.

  • Alphabet: a finite set of symbols. Typical Post machine examples use alphabet {1, B} where B is a blank. We call symbols the letters that appear on the tape.

  • Tape: an infinite one-dimensional sequence of cells indexed by integers. Each cell holds one symbol from the alphabet. (If a course uses a semi-infinite tape, state that assumption explicitly.) Both two-way infinite and semi-infinite tapes are equivalent in computational power; choose one model and state it.

  • Head: a device that reads the symbol in the current tape cell and can move left or right by one cell.

  • Configuration: the complete instantaneous description of the machine: the tape contents, the head position, and the current instruction number. We notate configuration informally as (tape, head-position, instruction-number).

  • Instruction set (standard Post machine variant): A Post machine program is a finite list of numbered instructions. Each instruction is one of a few forms (below we define the canonical forms used in most textbooks):

    • Print s and goto i: write symbol s into the current cell, then continue with instruction i.
    • Move L and goto i: move head one cell left, then continue with instruction i.
    • Move R and goto i: move head one cell right, then continue with instruction i.
    • If symbol = s then goto i else goto j: conditional transfer depending on the symbol currently under the head.
    • Halt (Accept or Reject): stop execution. A program may have separate halt instructions that mean accept or reject, or a single Halt that simply stops.

    In words: a Post machine program is a numbered sequence of small imperative instructions that operate locally on the tape and change the next instruction number.

  • Determinism: The standard Post machine is deterministic — for any configuration there is exactly one applicable next instruction in this standard instruction set.

  • Semantics: Execution starts at instruction number 1 with an input written on the tape in a prescribed way (often the tape is blank except for a finite input string written on consecutive cells and the head placed on the leftmost symbol). At each step execute the current instruction, update the tape and head, and jump to the indicated instruction number. When a Halt is reached, the machine stops. In this standard form, every step is defined; halting occurs only via an explicit HALT.

  • Computability equivalence: The exact theorem usually stated in exams is: Theorem. A function (or language) is computable (decidable) by a Post machine iff it is computable (decidable) by a Turing machine. Equivalently: Post machines are Turing-equivalent.

    Proof sketch (standard exam-level): show simulation both ways.

    1. Simulate a Post machine by a Turing machine: the tape and head of the Post machine are identical to the TM tape and head; each Post instruction maps to a small TM subroutine (write, move, conditional read). The TM stores the current instruction number in its finite control and branches accordingly. This yields a straightforward step-by-step simulation.
    2. Simulate a Turing machine by a Post machine: encode the TM's finite control state as part of the Post instruction numbering or as a marked pattern on the tape; emulate TM transition function by read-and-write plus move instructions and jumps. Each TM transition becomes a short sequence of Post instructions. Because a Post machine can read the current symbol, write, move and make conditional jumps, it can implement any TM transition. Thus they are equivalent.
  • Variants: There are related models introduced by Post: Post canonical systems and Post tag systems. These are different in form (rewriting systems for strings), and are often used in undecidability proofs. Do not confuse the simple Post machine instruction model above with tag systems; if an exam asks specifically for a tag system, present the tag-system definition instead.

  • What to draw in diagrams (when required): Draw the tape as a horizontal row of boxes. Label index 0 (or left end if semi-infinite) and show head as an arrow pointing to the current box. Next to the tape, show a small table of numbered instructions (number on left, instruction text on right). For simulation proofs, draw a mapping table: “Post instruction sequence ↔ Turing transition” with arrows showing the encoding.

Formulas

Remember Post program instruction syntax lines (each is one instruction):

k: PRINT s; GOTO m — write symbol s into current cell, then go to instruction m.

k: MOVE R; GOTO m — move head one cell right, then go to instruction m.

k: MOVE L; GOTO m — move head one cell left, then go to instruction m.

k: IF_SYM = s THEN GOTO i ELSE GOTO j — if current cell symbol equals s, then next instruction is i, otherwise j.

k: HALT — stop execution (optionally HALT-ACCEPT or HALT-REJECT).

Symbols used: s denotes a symbol of the tape alphabet; k,i,j,m are instruction numbers (positive integers).

When writing programs, number instructions consecutively for clarity but jumps can go to any number; there must be finitely many instructions.

Worked examples

Example 1 — Program to append a 1 (unary increment) to the right end of a (possibly empty) unary string of 1s, input placed starting at cell 0 with head at cell 0, blank symbol B and tape infinite to right.

Program (numbered): 1: IF_SYM = 1 THEN GOTO 2 ELSE GOTO 4 2: MOVE R; GOTO 1 3: (not used) 4: PRINT 1; HALT

Intent and explanation: scan right until we find a blank B, then write 1 and halt. Step-by-step for input tape [cells indexed 0..]: cell0=1, cell1=1, cell2=B, head starts at cell0.

  1. Instr 1: symbol=1 → goto 2.
  2. Instr 2: MOVE R → head now at cell1; goto 1.
  3. Instr 1: symbol=1 → goto 2.
  4. Instr 2: MOVE R → head now at cell2; goto 1.
  5. Instr 1: symbol=B → goto 4.
  6. Instr 4: PRINT 1 → cell2 becomes 1; HALT. Final tape: 1 1 1. (Works for any number of 1s.)

Example 2 — Recogniser for language L = {strings that start with 1}. Input alphabet {1,0}, blank B. Place input starting at cell0 and head at cell0. The machine should HALT-ACCEPT if first symbol is 1, HALT-REJECT otherwise.

Program: 1: IF_SYM = 1 THEN GOTO 2 ELSE GOTO 3 2: HALT-ACCEPT 3: HALT-REJECT

Trace: If cell0 has 1, instruction 1 jumps to 2 and accepts. If cell0 has 0 or B, jumps to 3 and rejects.

Example 3 — Simulating a single Turing transition: show how to implement a TM transition (q, a) → (q', b, R) in Post instructions. Design: encode TM state q as the current Post instruction region. Suppose at instruction block labeled Q_q we want to implement: if current symbol = a then write b, move right and enter state q'. Then a small Post subprogram: Q_q_start: IF_SYM = a THEN GOTO Q_q_do ELSE GOTO Q_q_other Q_q_do: PRINT b; MOVE R; GOTO Q_qprime_start Q_q_other: ... (handle other symbols) Q_qprime_start: ... (instructions for q') This construction is the basis of the simulation proof.

Common mistakes

  • Forgetting to specify the blank symbol and initial head position when giving a program.
  • Writing nondeterministic-looking instructions without clarifying determinism (Post machines as described are deterministic).
  • Using instruction numbers incorrectly (forgetting that GOTO must point to an existing instruction or to HALT).
  • In simulation proofs, not explaining how finite control (TM states) is represented in the Post program (you must show encoding: e.g., different instruction blocks per TM state).
  • Not describing halting convention (does HALT mean accept? separate HALT-ACCEPT / HALT-REJECT?) — always state it.

For your exam

Possible question types:

  • Define a Post machine and list its instruction forms. (Include formal semantics: what is a configuration and how steps are taken.)
  • Show with a diagram how to simulate a TM by a Post machine (or vice versa). (Full marks: show encoding of state, tape, and provide a sample mapping of a TM transition to a Post instruction sequence.)
  • Write a Post program for a simple string operation (append a symbol, test first symbol, move to end). (Full marks: give clear instruction list, initial configuration, and step-by-step trace on an example input.)
  • Explain differences between Post machine, Post tag system and Post canonical system. (Full marks: define each one briefly and state where each is used.)
  • Prove or state the theorem that Post machines are Turing-equivalent. (Full marks: give accurate statement and a clear proof sketch of simulation both ways.)

Always include: clear assumptions (infinite tape vs semi-infinite, blank symbol, input placement, halting/accepting convention), the instruction list numbered, and a trace for one concrete input.

Quick check

  1. What are the five canonical instruction types of a standard Post machine?
  2. How do you represent the TM state inside a Post machine when proving equivalence?
  3. True/False: A Post tag system and a standard Post machine are syntactically the same model.

Answers: 1: PRINT s; MOVE R; MOVE L; IF_SYM = s THEN GOTO i ELSE GOTO j; HALT. 2: Represent state by using different blocks of Post instructions (i.e., instruction-number ranges) corresponding to each TM state, jumping to the appropriate block to simulate entering a state. 3: False — a tag system is a rewriting system on strings and is different from the imperative Post machine model.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?