Turing Machines — The Ultimate Model of Computation

The Turing Machine (TM) is the most powerful theoretical model of computation. Alan Turing invented it in 1936 — before electronic computers existed — to answer the question: "What does it mean to compute something?"

Formal definition — a TM is a 7-tuple (Q, Σ, Γ, δ, q0, qaccept, qreject):
- Q — finite set of states
- Σ — input alphabet (does not contain blank symbol ⊔)
- Γ — tape alphabet (Σ ⊂ Γ, contains ⊔ blank)
- δ — transition function: Q × Γ → Q × Γ × {L, R} (state, tape symbol → new state, write symbol, move Left or Right)
- q0 — start state
- qaccept — the accept state (machine halts and accepts)
- qreject — the reject state (machine halts and rejects)

How a TM works:
- Infinite tape divided into cells, each holding one symbol (initially: input on tape, rest blanks)
- Read/write head starts at leftmost input symbol
- Each step: read current cell → look up δ → write new symbol → move L or R → go to new state
- Halts when it reaches qaccept or qreject
- May LOOP FOREVER (never halts) — this is the key difference from DFA/PDA

Church-Turing Thesis (not provable, but universally accepted):
"Any function that can be computed by an algorithm can be computed by a Turing Machine."
Implication: TMs are as powerful as any real computer. Python, C, Java — all equivalent in power to a Turing Machine. They can all solve exactly the same set of problems (just at different speeds).

Decidable vs Recognizable vs Undecidable:
- Decidable (Recursive): TM always halts and gives correct answer. "Yes or No, always."
  Examples: Is n prime? Is this DFA equivalent to that DFA? Does this string match this regex?
- Recognizable (Recursively Enumerable): TM halts and accepts if input is in language. May loop forever on inputs NOT in language.
- Undecidable: No TM can decide the language. Not just "we haven't found one" — PROVEN impossible.

The Halting Problem — the most famous undecidable problem:
"Given a program P and input I, does P halt on I?"
Proof by contradiction (Turing, 1936):
① Assume a decider H(P, I) exists that always says "halts" or "loops"
② Build program D(P): if H(P,P) says "halts" → loop forever; if H(P,P) says "loops" → halt
③ Run D on itself: D(D)
   • If H(D,D) says "halts" → D loops forever → H was wrong
   • If H(D,D) says "loops" → D halts → H was wrong
④ Contradiction either way → H cannot exist ∎

Implications of undecidability:
- Cannot write a perfect virus detector (would solve halting problem)
- Cannot write a perfect infinite-loop detector
- Cannot automatically verify all programs are correct (Rice's Theorem: all non-trivial properties of programs are undecidable)
- Gödel's incompleteness theorem is related: some true mathematical statements cannot be proven

Reductions: if problem A reduces to problem B (A ≤m B), then:
- If B is decidable → A is decidable
- If A is undecidable → B is undecidable
Used to prove new problems undecidable by reducing halting problem to them.

1# Turing Machine simulation
2
3class TuringMachine:
4    def __init__(self, transitions, start, accept, reject, blank="⊔"):
5        """
6        transitions: dict {(state, symbol): (new_state, write_sym, direction)}
7        direction: 'L' or 'R'
8        """
9        self.transitions = transitions
10        self.start       = start
11        self.accept      = accept
12        self.reject      = reject
13        self.blank       = blank
14
15    def run(self, input_string, max_steps=1000, verbose=False):
16        tape  = list(input_string) if input_string else [self.blank]
17        head  = 0
18        state = self.start
19        steps = 0
20
21        # Extend tape if head moves left of start
22        while head < 0:
23            tape.insert(0, self.blank)
24            head = 0
25
26        while steps < max_steps:
27            # Extend tape if needed
28            while head >= len(tape):
29                tape.append(self.blank)
30
31            symbol = tape[head]
32
33            if verbose and steps < 20:
34                tape_str = "".join(tape).rstrip(self.blank) or self.blank
35                print(f"  Step {steps:>3}: state={state} head={head} tape=[{tape_str}]")
36
37            if state == self.accept:
38                return True, steps
39            if state == self.reject:
40                return False, steps
41
42            key = (state, symbol)
43            if key not in self.transitions:
44                return False, steps   # implicit reject
45
46            new_state, write_sym, direction = self.transitions[key]
47            tape[head] = write_sym
48            state = new_state
49            head += 1 if direction == "R" else -1
50            if head < 0:
51                tape.insert(0, self.blank)
52                head = 0
53            steps += 1
54
55        return None, steps  # did not halt (possible infinite loop)
56
57# ── TM for aⁿbⁿ ───────────────────────────────────────
58# Algorithm: repeatedly cross off one 'a' and one 'b'
59tm_anbn = TuringMachine(
60    transitions = {
61        # Scan right, looking for 'a' to mark
62        ("q0","a"): ("q1","X","R"),   # mark 'a' as X, go find matching 'b'
63        ("q0","X"): ("q0","X","R"),   # skip already marked X's
64        ("q0","Y"): ("q3","Y","R"),   # all a's matched, verify only Y's remain
65        ("q0","⊔"): ("qa","⊔","R"),   # empty string → accept
66
67        # Moving right to find first 'b'
68        ("q1","a"): ("q1","a","R"),   # skip a's
69        ("q1","Y"): ("q1","Y","R"),   # skip marked b's
70        ("q1","b"): ("q2","Y","L"),   # mark 'b' as Y, go back left
71
72        # Moving left back to start
73        ("q2","a"): ("q2","a","L"),
74        ("q2","Y"): ("q2","Y","L"),
75        ("q2","X"): ("q0","X","R"),   # found leftmost X, restart
76
77        # Verifying no b's remain
78        ("q3","Y"): ("q3","Y","R"),
79        ("q3","⊔"): ("qa","⊔","R"),   # success!
80    },
81    start  = "q0",
82    accept = "qa",
83    reject = "qr",
84)
85
86print("TM: aⁿbⁿ")
87tests = [("", True), ("ab", True), ("aabb", True), ("aaabbb", True),
88         ("aab", False), ("abb", False), ("ba", False), ("abab", False)]
89for s, expected in tests:
90    result, steps = tm_anbn.run(s, verbose=False)
91    check = "✓" if result == expected else "✗"
92    print(f"  '{s}' → {'ACCEPT' if result else 'REJECT'} in {steps} steps {check}")
93
94# ── Halting Problem — cannot be solved ────────────────
95print("
96Halting Problem demonstration:")
97print("The following program CANNOT be decided in general:
98")
99halting_problem_pseudocode = """
100def does_halt(program, input):
101    # This function CANNOT exist for all programs
102    # Proof by contradiction:
103    
104    def diagonal(p):
105        if does_halt(p, p):
106            while True: pass   # loop if p(p) halts
107        else:
108            return              # halt if p(p) loops
109    
110    # diagonal(diagonal):
111    #   if does_halt(diagonal, diagonal) → True → loops → contradiction!
112    #   if does_halt(diagonal, diagonal) → False → halts → contradiction!
113    # Therefore does_halt() CANNOT EXIST ∎
114"""
115print(halting_problem_pseudocode)
116
117# ── Things that ARE decidable ──────────────────────────
118import sympy
119
120print("Decidable problems (TM always gives correct answer):")
121decidable = [
122    ("Is 104729 prime?",    sympy.isprime(104729)),
123    ("Is 104730 prime?",    sympy.isprime(104730)),
124    ("Does 'a*b' match 'aab'?", bool(__import__("re").match("a*b", "aab"))),
125    ("Is 2^31-1 prime?",    sympy.isprime(2**31-1)),
126]
127for question, answer in decidable:
128    print(f"  {question:<35} → {answer}")