Turing Machine

The previous two lessons drew a limit with two models. A finite automaton reads its input in a single pass, and its memory is as large as its state count; a production rule generates more without growing its description, but requires a search to decide. Both share the same gap: they cannot change what they read.

This lesson loosens the limit as much as possible. The model has a tape that extends without bound in both directions; a symbol sits in every cell of the tape, and the machine reads the cell it is on, writes over it, moves one step right or left, and changes its state. This model’s name is the Turing machine, and the theory uses this name. Per the course’s rule, only the name is mentioned here: the person is not described, and the name appears in no code identifier. The only information the name carries is which concept in the theory the definition below corresponds to.

Tape and Machine

The tape by itself is not a new power, but a new form of memory. In a finite automaton, memory was bounded by the state count and could not grow with the input; on a tape, memory grows over the course of the run. The machine’s description, by contrast, is still finite: once the state count and symbol count are given, the transition table’s row count is fixed. This means a budget, and a budget means an exhaustive count.

• MC17 — The tape is empty in both directions; an empty cell carries the symbol 0, and a cell with 0 written on it is indistinguishable from a cell never written to. The alphabet has two symbols.
• MC18 — A cell’s content is a triple: the symbol to write, the direction to move, the new state. If the new state is k, the machine halts; the start state is 0, and the machine starts on a blank tape.
• MC19 — All k-state, two-symbol machines can be counted. The transition table has 2k cells, and each cell takes one of $2 \cdot 2 \cdot (k+1)$ options. 64 machines for k=1, 20,736 for k=2.
• MC20 — The budget is steps. One step consists of reading one cell, writing, and moving. Duration is not measured.
• MC21 — The “known to halt” count is cumulative: a machine seen to halt at a small budget is not counted again at a larger budget.

"""Machine family running on a tape: ALL k-state, 2-symbol machines."""
from itertools import product

WRITE = (0, 1)
MOVE = (-1, 1)


def machines(k):
    """Cell: (symbol to write, move, new state). New state k means HALT."""
    cell = [(w, m, s) for w in WRITE for m in MOVE for s in range(k + 1)]
    positions = [(state, symbol) for state in range(k) for symbol in (0, 1)]
    for choice in product(cell, repeat=len(positions)):
        yield dict(zip(positions, choice))


def run(machine, k, budget):
    """Blank tape. Returns: (halted, steps, number of 1s written to the tape)."""
    tape = {}
    position, state, step = 0, 0, 0
    while step < budget:
        symbol = tape.get(position, 0)
        write, move, next_state = machine[(state, symbol)]
        tape[position] = write
        position += move
        step += 1
        if next_state == k:
            return True, step, sum(tape.values())
        state = next_state
    return False, step, sum(tape.values())


def budget_sweep(k, budgets):
    all_machines = list(machines(k))
    known = set()
    print(f"k = {k} states, machine count {len(all_machines)}")
    for b in budgets:
        for i, m in enumerate(all_machines):
            if i not in known and run(m, k, b)[0]:
                known.add(i)
        print(f"  budget {b:4d}  known to halt {len(known):6d}"
              f"  unknown {len(all_machines) - len(known):6d}")
    return all_machines


BUDGETS = (1, 3, 6, 7, 10, 50, 200)
budget_sweep(1, BUDGETS)
all_machines = budget_sweep(2, BUDGETS)
print()
distribution = {}
best = None
for m in all_machines:
    halted, step, ones = run(m, 2, 200)
    if halted:
        distribution[step] = distribution.get(step, 0) + 1
        if best is None or (step, ones) > (best[1], best[2]):
            best = (m, step, ones)
print("step distribution of halting machines:", dict(sorted(distribution.items())))
print("longest halting run:", best[1], "steps ,", best[2], "ones")
print("transition table:", {f"s{s}y{y}": v for (s, y), v in best[0].items()})
print()
print("step  state  next  position  tape")
tape, position, state, step = {}, 0, 0, 0
while step < 200:
    symbol = tape.get(position, 0)
    write, move, next_state = best[0][(state, symbol)]
    tape[position] = write
    position += move
    step += 1
    display = "".join(str(tape.get(p, 0)) for p in range(min(tape), max(tape) + 1))
    print(f"{step:4d}  {state:5d}  {next_state:4d}  {position:5d}  {display}")
    if next_state == 2:
        break
    state = next_state

k = 1 states, machine count 64
  budget    1  known to halt     32  unknown     32
  budget    3  known to halt     32  unknown     32
  budget    6  known to halt     32  unknown     32
  budget    7  known to halt     32  unknown     32
  budget   10  known to halt     32  unknown     32
  budget   50  known to halt     32  unknown     32
  budget  200  known to halt     32  unknown     32
k = 2 states, machine count 20736
  budget    1  known to halt   6912  unknown  13824
  budget    3  known to halt   9600  unknown  11136
  budget    6  known to halt   9784  unknown  10952
  budget    7  known to halt   9784  unknown  10952
  budget   10  known to halt   9784  unknown  10952
  budget   50  known to halt   9784  unknown  10952
  budget  200  known to halt   9784  unknown  10952

step distribution of halting machines: {1: 6912, 2: 2304, 3: 384, 4: 128, 5: 16, 6: 40}
longest halting run: 6 steps , 4 ones
transition table: {'s0y0': (1, -1, 1), 's0y1': (1, 1, 1), 's1y0': (1, 1, 0), 's1y1': (1, -1, 2)}

step  state  next  position  tape
   1      0     1     -1  1
   2      1     0      0  11
   3      0     1      1  11
   4      1     0      2  111
   5      0     1      1  1111
   6      1     2      0  1111

Three numbers side by side. Budget: step budget 1 to 200, family size 64 and 20,736. What the budget answers: in the two-state family, 9784 machines were seen to halt; in the one-state family, 32. What the budget fails to answer: in the two-state family, 10,952 machines did not halt at this budget, and this number did not change at all when the budget was raised from 6 to 200.

The real information the budget sweep gives is the saturation point. The count is 6912 at step 1, 9600 at step 3, 9784 at step 6, and constant from there on. The step distribution shows this in a single line: 6912 machines halt in one step, 2304 in two, and only 40 machines halt in six steps. That every halting run in this family takes at most 6 steps is a known result of the theory; the measurement agrees with this result, it does not establish it.

The 6912 in the first row can also be calculated, and calculating it tests the measurement’s correctness. Because the machine starts on a blank tape, the first cell read is always the intersection of state 0 and symbol 0. That cell has 12 options, and in 4 of them the new state is the halting state; that is, exactly one third of all machines halt on the very first step. One third of 20,736 is 6912, and the table gives exactly this. The measurement hitting an expected number does not verify it, but missing it would have shown a flaw; this kind of check is sought for every number in this course.

The final table is one machine’s trace, and it shows what the tape is for. The machine starts on a blank tape, writes to the left on the first step, then turns right, and halts on the sixth step after writing 1 to four cells. Steps three and five, where it visits the same cell twice, deserve attention: the machine reads what it wrote earlier and makes its decision based on that. A finite automaton has no counterpart to this.

A Single Procedure Runs Every Machine

There is a single procedure that does every run above: run. The machine is not embedded inside this procedure; it is supplied as an argument. Each of the 20,736 machines is a transition table, that is, data, and a single procedure executes the whole of this data. This is the model’s defining property: one machine’s description can be another machine’s input. This is why this model is counted as universal — because it can carry a program as data.

From here follows the theory’s most frequently cited claim. The Church–Turing thesis states that everything intuitively called “computable by a procedure” is computable with this model. The word “thesis” in the name is not an accident: this is not a proven proposition; it is a correspondence established between a formal model and the informal notion of “procedure.” It cannot be proved, because one of its two sides is undefined; it can be tested, because every newly proposed model has so far computed the same set as this model.

Universality also has a measurable side. The previous lesson established a distinction: what grows with the input was the description in the automaton, the run in the production rule. In the tape model, the description never grows: a two-state machine’s transition table is four lines, and it stays four lines no matter how many cells are written on the tape. The only thing that grows is the run — the step count and the number of cells used. This shows plainly where the power comes from: a finite description, an unbounded working area.

The practical consequence the thesis brings to this lesson is this: if this model cannot decide a question, then searching for a procedure that can decide it is also pointless. What the next section measures sits exactly at the edge of this limit.

Can a Proof Say What the Budget Cannot

“Did not halt at this budget” and “never halts” are not the same statement, and the second is never written from a single run in this course. But sometimes a proof can be extracted from within a run. Because the tape is blank in both directions, the machine’s configuration depends only on the state and the position of the 1’s on the tape, relative to the head. If the same configuration occurs a second time, the machine repeats the movement in between forever; if it did not halt in the first cycle, it will not halt in any cycle. This is not an observation, it is an inference.

• MC22 — A configuration is the pair (state, set of cells carrying a 1, relative to the head). A cell written with 0 is indistinguishable from a blank cell.
• MC23 — A repeated configuration is a loop certificate; the machine never halts on that run.
• MC24 — Failing to find a certificate says nothing. The result splits into three sets: halted, loop, and unknown.
• MC25 — The loop scan is swept too: it is repeated at budgets 10, 50, and 200.
• MC26 — Cycle detection in a graph was established in the Data Structures course and is not explained again here; the only difference here is that the nodes are not given in advance and are generated during the run.

"""How many of the machines the budget cannot answer are settled by a CERTIFICATE."""
from itertools import product

WRITE = (0, 1)
MOVE = (-1, 1)


def machines(k):
    cell = [(w, m, s) for w in WRITE for m in MOVE for s in range(k + 1)]
    positions = [(state, symbol) for state in range(k) for symbol in (0, 1)]
    for choice in product(cell, repeat=len(positions)):
        yield dict(zip(positions, choice))


def resolve(machine, k, budget):
    """Returns: ('halted' | 'loop' | 'unknown', steps).

    The tape is blank in both directions; so if the same configuration, shifted
    relative to position, occurs a second time, the machine repeats the same
    movement forever.
    """
    tape = {}
    position, state, step = 0, 0, 0
    seen = {(0, frozenset())}
    while step < budget:
        symbol = tape.get(position, 0)
        write, move, next_state = machine[(state, symbol)]
        tape[position] = write
        position += move
        step += 1
        if next_state == k:
            return "halted", step
        state = next_state
        signature = (state, frozenset(p - position for p, v in tape.items() if v))
        if signature in seen:
            return "loop", step
        seen.add(signature)
    return "unknown", step


for k in (1, 2):
    all_machines = list(machines(k))
    print(f"k = {k} states, machine count {len(all_machines)}")
    latest = 0
    for budget in (10, 50, 200):
        tally = {"halted": 0, "loop": 0, "unknown": 0}
        for m in all_machines:
            result, step = resolve(m, k, budget)
            tally[result] += 1
            if result == "loop":
                latest = max(latest, step)
        print(f"  budget {budget:4d}  halted {tally['halted']:6d}"
              f"  loop certified {tally['loop']:6d}"
              f"  unknown {tally['unknown']:6d}")
    print(f"  latest step a loop was caught at: {latest}")

k = 1 states, machine count 64
  budget   10  halted     32  loop certified     16  unknown     16
  budget   50  halted     32  loop certified     16  unknown     16
  budget  200  halted     32  loop certified     16  unknown     16
  latest step a loop was caught at: 1
k = 2 states, machine count 20736
  budget   10  halted   9784  loop certified   5040  unknown   5912
  budget   50  halted   9784  loop certified   5040  unknown   5912
  budget  200  halted   9784  loop certified   5040  unknown   5912
  latest step a loop was caught at: 8

Alongside the 9784 machines the budget settles in the two-state family, 5040 machines settled by the certificate are added. 5912 machines remain, and this lesson says nothing about them. Most of the remainder are machines that drift in one direction on the tape: because they write to a new cell every step, their configuration never repeats, even though a human eye looking at them can see that they do not halt. The proof tool’s scope is exactly as large as the pattern it looks for.

Splitting into three sets is itself this course’s method. A two-set report — only “halted” and “did not halt” — would turn the measurement into a verdict; the third set keeps a written record of where the verdict stops. The same structure shows up in the one-state family too: 32 halted, 16 certified, 16 unknown. When the family grew 324-fold, the ratios changed, but the third set never emptied.

The same numbers come out at all three budgets, and the reason is in the last line: a loop is caught at the latest by step 8. That is, there is no difference at all between budget 10 and budget 200 for this measure. In the same lesson, two separate budget sweeps gave two separate results: the halting scan saturated at 6, the loop scan at 8. The saturation point is a property of the question, not of the budget.

Summary

• A tape machine can write to the cell it reads and move in both directions; its memory grows over the course of the run, while its description stays finite.
• All machines in two-symbol families can be counted: 64 machines in the one-state family, 20,736 in the two-state family.
• When the step budget is swept, the halting-machine count progresses as 6912, 9600, 9784 and saturates at step 6; raising the budget to 200 does not change this number at all.
• The longest halting run takes 6 steps and writes four 1’s to the tape; that the upper bound in this family is 6 is a result of the theory, and the measurement merely agrees with it.
• A single run procedure executes all 20,736 machines; a machine’s description is data, and this is why the model is counted as universal.
• Of the 10,952 machines that do not halt within the budget, 5040 are settled by a loop certificate based on repeated configuration; the measurement says nothing about the remaining 5912.

Next Step

In this lesson, the “halted” count came from a budget, and the “never halts” count came from a certificate, and the sum of the two did not close the family. The next lesson asks whether this gap is a coincidence. On a one-line rule, the budget will be swept from 5 to 200, all one thousand starting points will be seen to halt, and right at that point the lesson’s most important sentence will be written: observation is not proof.