Turing Machines
& Undecidability

Conventions vary: some books allow a stay move S, a two-way infinite tape, or a partial δ where "no rule" means reject. All give the same power.

from collections import defaultdict

class TM:
    """Deterministic single-tape TM.
    delta[(state, sym)] = (new_state, write, move), move in "LRS".
    A missing rule means reject."""
    def __init__(self, delta, start, accept="qacc", reject="qrej"):
        self.delta, self.start = delta, start
        self.accept, self.reject, self.blank = accept, reject, "_"

    def run(self, w, max_steps=10_000, on_step=None):
        tape = defaultdict(lambda: self.blank, enumerate(w))
        q, head, steps = self.start, 0, 0
        while q not in (self.accept, self.reject):
            if on_step: on_step(tape, q, head)
            if steps == max_steps:
                return "timeout", steps, self.contents(tape)
            if (q, tape[head]) not in self.delta:
                q = self.reject
                break
            q, tape[head], move = self.delta[(q, tape[head])]
            head += {"L": -1, "R": 1, "S": 0}[move]
            steps += 1
        if on_step: on_step(tape, q, head)
        return q, steps, self.contents(tape)

    def contents(self, tape):
        used = [i for i, s in tape.items() if s != self.blank]
        return "".join(tape[i] for i in range(min(used), max(used) + 1)
                       ) if used else ""

inc = TM({("right", "0"): ("right", "0", "R"),   # go to the end
          ("right", "1"): ("right", "1", "R"),
          ("right", "_"): ("carry", "_", "L"),
          ("carry", "1"): ("carry", "0", "L"),   # 1 + carry = 0
          ("carry", "0"): ("qacc",  "1", "S"),   # 0 + carry = 1
          ("carry", "_"): ("qacc",  "1", "S")},  # new leading 1
         start="right")

def show(tape, q, head):
    lo, hi = min([head, *tape]), max([head, *tape])
    left = "".join(tape[i] for i in range(lo, head)).strip("_")
    right = "".join(tape[i] for i in range(head, hi + 1)).rstrip("_")
    print(f"{left}[{q}]{right or '_'}")

inc.run("1011", on_step=show)
for w in ["0", "1", "111", "1001"]:
    print(w, "->", inc.run(w)[2])

[right]1011
1[right]011
10[right]11
101[right]1
1011[right]_
101[carry]1
10[carry]10
1[carry]000
1[qacc]100
0 -> 1
1 -> 10
111 -> 1000
1001 -> 1010

aabbcc  →  XaYbZc  →  XXYYZZ  →  accept

We proved with the pumping lemma that no PDA accepts this language. The TM's secret: it can re-read and rewrite the input.

d = {("q0", "a"): ("q1", "X", "R"),
     ("q0", "Y"): ("q4", "Y", "R"),
     ("q0", "_"): ("qacc", "_", "S"),     # n = 0
     ("q1", "b"): ("q2", "Y", "R"),
     ("q2", "c"): ("q3", "Z", "L"),
     ("q3", "X"): ("q0", "X", "R"),
     ("q4", "_"): ("qacc", "_", "S")}
for s in "aY":   d[("q1", s)] = ("q1", s, "R")   # skip right
for s in "bZ":   d[("q2", s)] = ("q2", s, "R")
for s in "abYZ": d[("q3", s)] = ("q3", s, "L")   # rewind
for s in "YZ":   d[("q4", s)] = ("q4", s, "R")   # final check
abc = TM(d, start="q0")
print(len(d), "rules")

17 rules

tests = ["", "abc", "aabbcc", "aabbc", "abcabc",
         "aaabbbccc", "acb", "aabbbcc"]
for w in tests:
    result, steps, _ = abc.run(w)
    print(f"{w!r:12} {result:5} after {steps:3} steps")

''           qacc  after   1 steps
'abc'        qacc  after   8 steps
'aabbcc'     qacc  after  23 steps
'aabbc'      qrej  after  13 steps
'abcabc'     qrej  after   7 steps
'aaabbbccc'  qacc  after  46 steps
'acb'        qrej  after   1 steps
'aabbbcc'    qrej  after  24 steps

for n in range(1, 8):
    steps = abc.run("a" * n + "b" * n + "c" * n)[1]
    print(n, steps, 4 * n * n + 3 * n + 1)

1 8 8
2 23 23
3 46 46
4 77 77
5 116 116
6 163 163
7 218 218

Hennie–Stearns (1966): k tapes can be simulated on two tapes with only an O(log t) factor slowdown.

The class of recognizable languages does not care about these details. That robustness is strong evidence that it is the "right" definition.

Quantum computers do not break the classic thesis. A TM can simulate them, only slowly.

def encode(tm):
    """<M>: every rule as q,s,p,w,m; then the start state."""
    rules = sorted(tm.delta.items())
    body = ";".join(f"{q},{s},{p},{w},{m}"
                    for (q, s), (p, w, m) in rules)
    return body + "#" + tm.start

code = encode(inc)
print(len(code), "chars:", code[:44] + "...")

111 chars: carry,0,qacc,1,S;carry,1,carry,0,L;carry,_,q...

Any reasonable encoding works. The machine that reads it can translate between encodings.

def U(code, w, max_steps=10_000):
    """Universal machine: parse <M>, then simulate M on w."""
    body, start = code.split("#")
    delta = {}
    for rule in body.split(";"):
        q, s, p, wr, m = rule.split(",")
        delta[(q, s)] = (p, wr, m)
    return TM(delta, start).run(w, max_steps)

print(U(encode(inc), "1011"))
print(U(encode(abc), "aabbcc")[0], U(encode(abc), "aabcc")[0])

('qacc', 8, '1100')
qacc qrej

Small universal TMs exist: Minsky (1962) found one with 7 states and 4 symbols. Wolfram's 2-state 3-symbol machine was shown universal by Alex Smith (2007), in a weak sense.

Picture an infinite table: row i is L_i, column n says whether n ∈ L_i. D flips the diagonal, so it differs from every row somewhere.

The same trick shows the reals are uncountable. Turing reused it for halting, and Gödel for incompleteness.

# A (finite) list of "languages" over N, as predicates
langs = [lambda n: n % 2 == 0,
         lambda n: n > 3,
         lambda n: n in {1, 2, 3},
         lambda n: False,
         lambda n: bin(n).count("1") == 2,
         lambda n: True]
D = lambda n: not langs[n](n)          # flip the diagonal

N = len(langs)
for i, L in enumerate(langs):
    row = " ".join("1" if L(n) else "." for n in range(N))
    print(f"L{i}: {row}   D differs at {i}: {D(i) != L(i)}")
print(" D:", " ".join("1" if D(n) else "." for n in range(N)))

L0: 1 . 1 . 1 .   D differs at 0: True
L1: . . . . 1 1   D differs at 1: True
L2: . 1 1 1 . .   D differs at 2: True
L3: . . . . . .   D differs at 3: True
L4: . . . 1 . 1   D differs at 4: True
L5: 1 1 1 1 1 1   D differs at 5: True
 D: . 1 . 1 1 .

Read down the diagonal of the table: 1 . 1 . . 1. D is its flip: . 1 . 1 1 ..

Picked "at random", a language is undecidable with probability 1. The decidable ones are the rare exception.

Suppose someone hands us halts(f): it returns True iff calling f() would finish. We build a program that does the opposite of whatever halts predicts about it.

def make_D(halts):
    """Build the program that defeats a claimed halting decider."""
    def D():
        if halts(D):
            while True:          # predicted to halt? loop forever
                pass
        return "halted"          # predicted to loop? halt at once
    return D

candidates = {"always yes": lambda f: True,
              "always no":  lambda f: False,
              "by name":    lambda f: f.__name__ != "D"}
for name, halts in candidates.items():
    D = make_D(halts)
    says = halts(D)
    if says:
        truth = "loops forever"            # D would enter while True
    else:
        truth = "returns " + repr(D())     # safe: we actually run it
    print(f"{name:10}  halts(D) = {says!s:5}  but D {truth}")

always yes  halts(D) = True   but D loops forever
always no   halts(D) = False  but D returns 'halted'
by name     halts(D) = False  but D returns 'halted'

The same f, in Python

def f(program, w):
    """Map <M, w> to <M_w>: a program that takes no input.
    M_w halts  iff  M halts on w."""
    return program + f"\nmain({w!r})\n"

M = '''def main(x):
    while x != "stop":
        pass'''
print(f(M, "stop"))

def main(x):
    while x != "stop":
        pass
main('stop')

• Of the language: if L(M₁) = L(M₂), both have P or neither does. It is about behavior, not code.
• Non-trivial: some TM has P and some TM does not.

T(x):  run M on w          # may loop
       if it accepts: run M_P on x

PCP has no machines in it: just strings. That makes it a great source for reductions, like CFG ambiguity and CFG intersection.

from collections import deque

def pcp(dominoes, max_len=10):
    """BFS for a match; keep only states where one row
    is a prefix of the other."""
    todo = deque([((), "", "")])
    while todo:
        seq, top, bot = todo.popleft()
        if seq and top == bot:
            return [i + 1 for i in seq]
        if len(seq) == max_len:
            continue
        for i, (t, b) in enumerate(dominoes):
            T, B = top + t, bot + b
            if T.startswith(B) or B.startswith(T):
                todo.append((seq + (i,), T, B))
    return None                   # none found up to max_len

sipser = [("b", "ca"), ("a", "ab"), ("ca", "a"), ("abc", "c")]
print(pcp(sipser))
print(pcp([("abc", "ab"), ("ca", "a"), ("acc", "ba")]))
print(pcp([("a", "baa"), ("ab", "aa"), ("bba", "bb")]))

[2, 1, 3, 2, 4]
None
[3, 2, 3, 1]

First: a|b|ca|a|abc over ab|ca|a|ab|c both spell abcaaabc. Second: every top is longer, so no match ever. None from a bounded search proves nothing in general, which is the whole point.

import itertools
from collections import defaultdict

def bb_run(table, max_steps=10**6):
    """table["A"] = (rule on 0, rule on 1); rule like "1RB".
    Returns (steps, ones) if it halts, else None."""
    tape, head, q, steps = defaultdict(int), 0, "A", 0
    while q != "H" and steps < max_steps:
        write, move, q = table[q][tape[head]]
        tape[head] = int(write)
        head += 1 if move == "R" else -1
        steps += 1
    return (steps, sum(tape.values())) if q == "H" else None

# Exhaustive search over ALL 2-state machines
rules = [w + m + n for w in "01" for m in "LR" for n in "ABH"]
best, halted, total = (0, 0), 0, 0
for c in itertools.product(rules, repeat=4):
    total += 1
    r = bb_run({"A": c[:2], "B": c[2:]}, max_steps=100)
    if r:
        halted += 1
        best = (max(best[0], r[0]), max(best[1], r[1]))
print(total, "machines,", halted, "halt")
print("S(2) =", best[0], " Sigma(2) =", best[1])

20736 machines, 9784 halt
S(2) = 6  Sigma(2) = 4

A 100-step cap is safe here only because we already know S(2) = 6. For large n, no cap is ever known to be safe.

def parse(s):                  # standard text notation
    return {chr(65 + i): (r[:3], r[3:])
            for i, r in enumerate(s.split("_"))}

champions = {
    "BB(2)":         "1RB1LB_1LA1RH",
    "BB(3) Sigma":   "1RB1RH_0RC1RB_1LC1LA",
    "BB(3) S":       "1RB1RH_1LB0RC_1LC1LA",
    "BB(4)":         "1RB1LB_1LA0LC_1RH1LD_1RD0RA",
}
for name, s in champions.items():
    steps, ones = bb_run(parse(s))
    print(f"{name:12} {steps:4} steps, {ones:3} ones")

BB(2)           6 steps,   4 ones
BB(3) Sigma    14 steps,   6 ones
BB(3) S        21 steps,   5 ones
BB(4)         107 steps,  13 ones

For 3 states, the most-ones machine and the most-steps machine differ.

↑↑↑ is Knuth's arrow notation. 2↑↑5 is already a tower of five 2s, 2⁶⁵⁵³⁶.

A Python quine: prints its own source

s = 's = %r\nprint(s %% s)'
print(s % s)

s = 's = %r\nprint(s %% s)'
print(s % s)

%r inserts s quoted (part A as data). %% becomes %. The test file checks the output equals the source exactly.

A program that knows its own length

t = 't = %r\nprint(len(t %% t))'
print(len(t % t))

50

Simple code, unknown halting

def collatz_steps(n):
    """Does this loop end for every n >= 1? Nobody knows."""
    steps = 0
    while n != 1:
        n = 3 * n + 1 if n % 2 else n // 2
        steps += 1
    return steps

print([collatz_steps(n) for n in range(1, 13)])
print(collatz_steps(27), collatz_steps(97), collatz_steps(871))

[0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9]
111 118 178

The Collatz conjecture says this halts for every n. Checked past 2⁶⁸, still unproved. A general halting decider would settle it, and Goldbach, and many more.

Hilbert's program asked for a complete, consistent, decidable foundation. Gödel ruled out the first two together. Church and Turing ruled out the third.

This ladder is the arithmetical hierarchy (Kleene, Mostowski). Each level adds one quantifier, and one level of oracle.

Try each one before you open the answer.

Previous deck: context-free grammars and pushdown automata. Next: complexity, P vs NP.