The halting problem: why every call needs a budget (Turing 1936)

Turing defined computation with a machine that reads and writes a tape, and proved that no program can decide, for every machine and input, whether it eventually halts. Running a machine longer never settles the question: a machine that has not halted yet may halt later, or never. A blockchain that lets anyone submit programs therefore cannot check in advance that they terminate. It bounds them instead, with a step budget.

What to look for

All 20,736 two-state Turing machines are run from a blank tape with growing step budgets. Those that halt do so within six steps; some are caught repeating a configuration, which proves they loop. But a large group stays unknown at every budget: no finite budget sorts them.

The history behind this experiment: Breakthroughs in Replicated Execution.

Classify every two-state machine

import matplotlib.pyplot as plt

import blockchainkit as bk

machines = list(bk.vm.enumerate_machines(2))
budgets = [2, 4, 6, 10, 20, 50]
counts = {outcome: [] for outcome in ("halted", "looping", "unknown")}
for budget in budgets:
    tally = {outcome: 0 for outcome in counts}
    for rules in machines:
        tally[bk.vm.run_turing_machine(rules, max_steps=budget).outcome] += 1
    for outcome in counts:
        counts[outcome].append(tally[outcome])
print(counts)
assert counts["halted"][2] == counts["halted"][-1]  # Nothing halts after step 6...
assert counts["unknown"][-1] > 0  # ...yet many machines are still undecided.

{'halted': [9216, 9728, 9784, 9784, 9784, 9784], 'looping': [0, 336, 418, 430, 430, 430], 'unknown': [11520, 10672, 10534, 10522, 10522, 10522]}

A machine the budget cannot classify

This one writes 1s rightward forever without repeating a configuration.

runner = {
    ("A", 0): (1, 1, "A"),
    ("A", 1): (1, 1, "A"),
    ("B", 0): (0, 1, "A"),
    ("B", 1): (0, 1, "A"),
}
for budget in (10, 100, 1000):
    print(budget, bk.vm.run_turing_machine(runner, max_steps=budget).outcome)

fig, ax = plt.subplots(figsize=(7, 4))
for outcome, values in counts.items():
    ax.plot(budgets, values, "o-", label=outcome)
ax.set(xlabel="step budget", ylabel="machines", title="20,736 two-state machines")
ax.legend()
fig.tight_layout()

10 unknown
100 unknown
1000 unknown

Exercise

Write a cheap test that proves the runner machine never halts: what property of its state and the blank tape ahead makes the future repeat? Why can no such collection of tests cover every machine?