Turing Machines

A Turing machine is the canonical model of computation: a read/write head moving along an infinite tape of cells, driven by a finite table of rules. It is the purest test of the engine’s core idea — that a domain is described by entities, states and messages, with no hand-written control loop. Several scenarios in the catalog are full Turing machines, from Turing’s own 1936 examples to small universal machines by Wolfram, Rogozhin and Minsky.

This page covers how they are built: the single-head / self-growing-tape pattern that every Turing scenario shares, and the one variation that lets Wolfram’s machine run over a non-blank background.

The two machines: a head and a tape of cells

Every Turing scenario is exactly two state machines:

Head — one entity, always active. It holds the control state of the machine (Turing’s b/c/e/f, or states A/B, or t0–t6) and a single current reference to the tape cell sitting under the head. On each turn it reads the symbol in current, looks up the rule for (state, symbol), writes the new symbol back into current, transitions to the next control state, and moves left or right by re-pointing current at a neighbour.
Cell — one entity per tape square. A cell stores its symbol and references to its left and right neighbours. Once built, a cell is passive: it does nothing until the head writes into it.

The head reads and writes through its reference (self.current.symbol) and moves by following the neighbour references (self.current.left / self.current.right). There is no global scan of the tape and no central scheduler stepping the cells — the head is the only active entity, and the tape is just a linked structure it walks over.

The Turing scenarios

Each scenario ships a self-contained, step-by-step replay of its run. The table links to each one on the main site.

Scenario	States × Symbols	What it does	Halts?
Turing’s First Example	4 × 1	Prints `0 1 0 1 …` rightward forever	No
Turing’s Second Example	7 × 4	Prints growing blocks of 1s by copying the last block and adding one	No
Palindrome Decider	6 × 3	Erases matching ends and sweeps inward; decides if the input is a palindrome	Accept / Reject
Wolfram (2,3) Machine	2 × 3	The smallest machine proved universal (2007), over an alternating background	No
Rogozhin (4,6) Machine	4 × 6	Rogozhin’s 1996 small universal machine on an un-encoded input	Has a halt state
Minsky (7,4) Machine	7 × 4	Minsky’s 1967 universal machine; halts on the demo input after 23 steps	Yes

The blank-only first example has a single tape column because it never reads what it writes — it only ever visits blank squares — so its rule table has one entry per state. Every other machine reads the symbol under the head, so its table has one column per symbol.

The self-growing tape

A real Turing machine’s tape is infinite, but an infinite tape cannot be pre-allocated. Instead the tape grows itself, one cell at a time, exactly as far as the computation reaches. When the head needs to move onto a square that does not exist yet, the current cell builds it.

The head’s current cell spawns the next square and wires it both ways; the new cell goes passive immediately, so the tape is always exactly as long as the run has reached.

The mechanism is a short message exchange, the same scan-free scheme used by the BusyBeaver scenarios:

The head asks its current cell to extend the tape — it emits a GrowRight (or GrowLeft) message toward the neighbour direction it is about to move.
The cell receiving that message spawns a fresh neighbour Cell, wired with a left (or right) reference back to itself.
The new cell, in its first active turn, sends an IAmYourRight message back so the parent records the reverse reference, then passivates.

Cell:
  states:
    Idle:
      passive_on_entry: true          # a built cell does nothing until written to
      messages_accepted:
        - message: GrowRight
          handlers:
            - { name: gr, actions: [ { type: new_entity, entity: Cell, state: FreshRight,
                  references: { left: self } } ] }
        - message: IAmYourRight
          handlers:
            - { name: iyr, actions: [ { type: set_reference, reference: right, source: sender },
                  { type: update, field: has_right, operator: set, value: 1 } ] }
    FreshRight:
      events:
        - name: reg
          actions:
            - { type: emit_message, target: left, message: IAmYourRight }
            - { type: transition, state: Idle }

Because a cell only ever grows the one neighbour the head is about to step onto, the tape stays exactly as long as it needs to be. A non-halting machine grows its tape forever — one new passive cell per excursion past the current end — while the active step-set stays a single head. The dataset you export is therefore the precise trace of how far the computation actually travelled.

Variation: a non-blank background (Wolfram’s weak universality)

Most Turing machines start on a blank tape. Wolfram’s (2,3) machine is weakly universal: it is universal only when run over an infinite, non-blank, periodic background — for this scenario, the alternating pattern … 0 1 0 1 0 1 … extending forever in both directions.

An infinite alternating tape cannot be pre-populated any more than a blank one can, so the same self-growing pattern carries it with one addition. Each cell stores an immutable bg field — the background digit it was born holding — alongside its mutable symbol:

A cell’s symbol starts equal to its bg (the content the head reads on first visit) and is overwritten by the head thereafter.
When a cell grows a neighbour, it hands that neighbour the opposite bg. Adjacent cells therefore always differ, so the revealed tape reads … 0 1 0 1 … in both directions.
bg itself never changes, so the background stays correct even behind the head, where the head has already overwritten symbol.

The result is an infinite alternating background that is revealed one cell at a time as the head walks off either end, with no pre-population and no global state.