TMC #0001: Turing Machine Simulator

"""
The Thinking Machine Chronicles #0001
Turing Machine Simulator
========================
A faithful Python implementation of the theoretical model described in Alan Turing's 1936 paper
"On Computable Numbers, with an Application to the Entscheidungsproblem".

A deterministic Turing machine is the 7-tuple:

    M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)

where:
  Q         — finite set of states
  Σ         — input alphabet (subset of Γ, not containing blank)
  Γ         — tape alphabet (Σ ∪ {blank})
  δ         — transition function: Q × Γ → Q × Γ × {L, R}
  q₀        — initial state
  q_accept  — accepting state
  q_reject  — rejecting state

Usage:
    python turing_machine.py
"""

from __future__ import annotations

import textwrap
from dataclasses import dataclass
from typing import Dict, List, Tuple

# ---------------------------------------------------------------------------
# Core model
# ---------------------------------------------------------------------------

TransitionKey = Tuple[str, str]  # (state, symbol)
TransitionVal = Tuple[str, str, str]  # (new_state, write_symbol, direction)


@dataclass
class TuringMachine:
    """
    Deterministic Turing machine.

    transitions: dict mapping (state, symbol) → (new_state, write_symbol, direction)
                 direction must be 'L' or 'R'
    initial_state: q₀
    accept_state:  q_accept  (default "ACCEPT")
    reject_state:  q_reject  (default "REJECT")
    blank:         the blank symbol (default "_")
    """

    transitions: Dict[TransitionKey, TransitionVal]
    initial_state: str
    accept_state: str = "ACCEPT"
    reject_state: str = "REJECT"
    blank: str = "_"

    def run(
        self,
        input_str: str,
        max_steps: int = 100_000,
        verbose: bool = False,
    ) -> Tuple[bool, str, int]:
        """
        Simulate the machine on input_str.

        Returns:
            (accepted, tape_contents, steps_taken)

        Raises:
            RuntimeError if max_steps is exceeded (machine likely loops).
        """
        # Initialise tape: blank pad on both sides for convenient extension
        tape: List[str] = [self.blank] + list(input_str) + [self.blank]
        head: int = 1  # points to first input symbol (index 0 is the left blank pad)
        state: str = self.initial_state
        steps: int = 0

        while state not in (self.accept_state, self.reject_state):
            if steps >= max_steps:
                raise RuntimeError(
                    f"Machine did not halt after {max_steps} steps. "
                    "It may loop on this input."
                )

            # Extend tape left if head fell off
            if head < 0:
                tape.insert(0, self.blank)
                head = 0

            # Extend tape right if head fell off
            if head >= len(tape):
                tape.append(self.blank)

            symbol = tape[head]

            if verbose:
                left = "".join(tape[:head])
                right = "".join(tape[head + 1 :])
                print(
                    f"  step {steps:5d}  [{state:15s}]  "
                    f"…{left[-12:]}[{symbol}]{right[:12]}…"
                )

            key: TransitionKey = (state, symbol)
            if key not in self.transitions:
                # Implicit reject: no transition defined
                state = self.reject_state
                break

            new_state, write, direction = self.transitions[key]
            tape[head] = write
            state = new_state
            head += 1 if direction == "R" else -1
            steps += 1

        tape_str = "".join(tape).strip(self.blank) or self.blank
        return state == self.accept_state, tape_str, steps

    def accepts(self, input_str: str, **kwargs) -> bool:
        accepted, _, _ = self.run(input_str, **kwargs)
        return accepted

    def print_transition_table(self) -> None:
        """Pretty-print the transition table."""
        print(f"\nTransition table — initial: {self.initial_state}")
        print(f"{'State':<18} {'Read':<8} {'Write':<8} {'Move':<6} {'→ State'}")
        print("-" * 56)
        for (state, sym), (new_state, write, direction) in sorted(
            self.transitions.items()
        ):
            print(f"  {state:<16} {sym:<8} {write:<8} {direction:<6} {new_state}")
        print()


# ---------------------------------------------------------------------------
# Example machines
# ---------------------------------------------------------------------------


def make_parity_machine() -> TuringMachine:
    """
    Decide whether the input (over {1}) contains an even number of 1s.

    States:
        even — have seen an even count of 1s so far
        odd  — have seen an odd count of 1s so far

    Accepts iff |input| is even (including the empty string).
    """
    return TuringMachine(
        transitions={
            ("even", "1"): ("odd", "1", "R"),
            ("even", "_"): ("ACCEPT", "_", "R"),
            ("odd", "1"): ("even", "1", "R"),
            ("odd", "_"): ("REJECT", "_", "R"),
        },
        initial_state="even",
    )


def make_palindrome_machine() -> TuringMachine:
    """
    Decide whether the input over {0, 1} is a palindrome.

    Algorithm:
      1. q_start: skip matched (X) symbols; on first unmatched c ∈ {0,1},
         mark it X and enter seek_right_c.
      2. seek_right_c: scan right past all symbols to the blank (right edge).
      3. find_right_c: from blank, scan LEFT past X's.
         - Reach blank without finding unmatched → lone middle symbol → ACCEPT.
         - Find symbol matching c → mark X, scan_back.
         - Find symbol not matching c → REJECT.
      4. scan_back: scan left to blank, then loop back to q_start.
      5. q_start on blank → ACCEPT (all symbols consumed).

    Correctly handles both even and odd-length palindromes.
    """
    return TuringMachine(
        transitions={
            # --- q_start: skip matched X's; process next unmatched symbol ---
            ("q_start", "0"): ("seek_right_0", "X", "R"),
            ("q_start", "1"): ("seek_right_1", "X", "R"),
            ("q_start", "X"): ("q_start", "X", "R"),
            ("q_start", "_"): ("ACCEPT", "_", "R"),
            # --- Scan right to the blank (right edge) -----------------------
            ("seek_right_0", "0"): ("seek_right_0", "0", "R"),
            ("seek_right_0", "1"): ("seek_right_0", "1", "R"),
            ("seek_right_0", "X"): ("seek_right_0", "X", "R"),
            ("seek_right_0", "_"): ("find_right_0", "_", "L"),
            ("seek_right_1", "0"): ("seek_right_1", "0", "R"),
            ("seek_right_1", "1"): ("seek_right_1", "1", "R"),
            ("seek_right_1", "X"): ("seek_right_1", "X", "R"),
            ("seek_right_1", "_"): ("find_right_1", "_", "L"),
            # --- From right edge, scan left past X's to rightmost unmatched -
            # Reaching blank: the left-marked symbol was the middle → ACCEPT
            ("find_right_0", "X"): ("find_right_0", "X", "L"),
            ("find_right_0", "_"): ("ACCEPT", "_", "R"),
            ("find_right_0", "0"): ("scan_back", "X", "L"),  # match
            ("find_right_0", "1"): ("REJECT", "1", "R"),  # mismatch
            ("find_right_1", "X"): ("find_right_1", "X", "L"),
            ("find_right_1", "_"): ("ACCEPT", "_", "R"),
            ("find_right_1", "1"): ("scan_back", "X", "L"),  # match
            ("find_right_1", "0"): ("REJECT", "0", "R"),  # mismatch
            # --- Scan back left to start ------------------------------------
            ("scan_back", "0"): ("scan_back", "0", "L"),
            ("scan_back", "1"): ("scan_back", "1", "L"),
            ("scan_back", "X"): ("scan_back", "X", "L"),
            ("scan_back", "_"): ("q_start", "_", "R"),
        },
        initial_state="q_start",
    )


def make_unary_adder() -> TuringMachine:
    """
    Add two unary numbers separated by a '+'.

    Input:  111+11    (representing 3 + 2)
    Output: 11111     (representing 5)

    Algorithm (two phases):
      Phase 1: scan right to '+', replace it with '1'.
               Tape now holds (m+1+n) ones — one too many.
      Phase 2: scan right to blank, back up one cell, erase last '1'.
               Result: exactly (m+n) ones.

    Correctness: "m·1s + n·1s" → replace '+' with '1' → "(m+1+n)·1s" →
    erase rightmost '1' → "(m+n)·1s". ✓
    """
    return TuringMachine(
        transitions={
            # Phase 1: scan right to '+'
            ("q0", "1"): ("q0", "1", "R"),
            ("q0", "+"): ("q1", "1", "R"),  # replace '+' with '1'
            # Phase 2: scan right to blank
            ("q1", "1"): ("q1", "1", "R"),
            ("q1", "_"): ("q2", "_", "L"),  # back up one cell
            # Erase the last '1'
            ("q2", "1"): ("ACCEPT", "_", "R"),
        },
        initial_state="q0",
    )


# ---------------------------------------------------------------------------
# Universal TM concept: encoding and decoding
# ---------------------------------------------------------------------------

import json


def encode_tm(tm: TuringMachine) -> str:
    """
    Encode a TM as a JSON string.

    This demonstrates the key insight of the Universal Turing Machine:
    a machine's description is just data.  A UTM reads this encoding and
    simulates the described machine — exactly what a CPU does with a program.
    """
    return json.dumps(
        {
            "transitions": {
                f"{k[0]}\x1f{k[1]}": list(v) for k, v in tm.transitions.items()
            },
            "initial_state": tm.initial_state,
            "accept_state": tm.accept_state,
            "reject_state": tm.reject_state,
            "blank": tm.blank,
        },
        indent=2,
    )


def decode_tm(s: str) -> TuringMachine:
    """
    Reconstruct a TM from its JSON encoding.

    This is what the Universal Turing Machine does: it reads the encoding ⟨M⟩
    and interprets it to simulate M on the provided input w.
    """
    d = json.loads(s)
    return TuringMachine(
        transitions={
            tuple(k.split("\x1f")): tuple(v)  # type: ignore[arg-type]
            for k, v in d["transitions"].items()
        },
        initial_state=d["initial_state"],
        accept_state=d["accept_state"],
        reject_state=d["reject_state"],
        blank=d["blank"],
    )


# ---------------------------------------------------------------------------
# Halting problem demonstrator
# ---------------------------------------------------------------------------


def halting_problem_demo() -> None:
    """
    Demonstrate that no TM can decide A_TM in general.

    We cannot build a decider H that always correctly answers
    "does M accept w?" — Turing's 1936 diagonalisation proof shows why.

    What we CAN do is build a recogniser: a machine that runs M on w and
    accepts if M accepts — but may loop forever if M loops.
    """
    print(
        textwrap.dedent("""
    ┌─────────────────────────────────────────────────────────────────────┐
    │  THE HALTING PROBLEM (A_TM)                                         │
    │                                                                     │
    │  A_TM = { ⟨M, w⟩ : M is a TM that accepts w }                      │
    │                                                                     │
    │  Theorem (Turing 1936): A_TM is UNDECIDABLE.                        │
    │                                                                     │
    │  Proof (diagonalisation sketch):                                    │
    │   1. Assume decider H exists: H(⟨M,w⟩) = accept iff M accepts w.   │
    │   2. Build D(⟨M⟩): calls H(⟨M, ⟨M⟩⟩) and does the OPPOSITE.       │
    │   3. Ask: what does D do on input ⟨D⟩?                              │
    │      • If D accepts ⟨D⟩ → H said "D rejects ⟨D⟩" → D rejects. ✗   │
    │      • If D rejects ⟨D⟩ → H said "D accepts ⟨D⟩" → D accepts. ✗   │
    │   4. Contradiction → H cannot exist. □                              │
    │                                                                     │
    │  Consequence: we cannot in general prove that a program terminates. │
    │  This is why static analysis tools give warnings, not guarantees.   │
    └─────────────────────────────────────────────────────────────────────┘
    """)
    )


# ---------------------------------------------------------------------------
# Main demo
# ---------------------------------------------------------------------------


def main() -> None:
    print("=" * 68)
    print("  THE THINKING MACHINE CHRONICLES #0001")
    print("  Turing Machine Simulator")
    print("=" * 68)

    # ── 1. Parity machine ──────────────────────────────────────────────────
    print("\n── Example 1: Parity Checker (even number of 1s?) ──────────────\n")
    parity = make_parity_machine()
    parity.print_transition_table()

    for n in range(7):
        inp = "1" * n
        accepted, tape, steps = parity.run(inp)
        verdict = "ACCEPT" if accepted else "REJECT"
        print(f"  input={inp!r:12s}  count={n}  → {verdict}  ({steps} steps)")

    # ── 2. Palindrome checker ──────────────────────────────────────────────
    print("\n── Example 2: Palindrome Checker ({0,1}*) ──────────────────────\n")
    palindrome = make_palindrome_machine()

    cases = [
        ("", True),
        ("0", True),
        ("1", True),
        ("00", True),
        ("01", False),
        ("010", True),
        ("011", False),
        ("0110", True),
        ("0101", False),
        ("10001", True),
        ("10011", False),
        ("11011", True),
    ]

    for inp, expected in cases:
        accepted, _, steps = palindrome.run(inp)
        ok = "✓" if (accepted == expected) else "✗"
        verdict = "ACCEPT" if accepted else "REJECT"
        print(f"  {ok}  input={inp!r:10s}  → {verdict}  ({steps} steps)")

    # ── 3. Unary adder ─────────────────────────────────────────────────────
    print("\n── Example 3: Unary Adder (m+n → m+n ones) ─────────────────────\n")
    adder = make_unary_adder()

    for a, b in [(0, 0), (1, 0), (0, 3), (2, 3), (4, 5)]:
        inp = "1" * a + "+" + "1" * b
        try:
            accepted, result, steps = adder.run(inp, max_steps=50_000)
        except RuntimeError as exc:
            print(f"  {a} + {b}: ERROR — {exc}")
            continue
        total = result.count("1")
        ok = "✓" if total == a + b else "✗"
        print(f"  {ok}  {a} + {b} = {total}  (tape: {result!r}, {steps} steps)")

    # ── 4. Universal TM concept ────────────────────────────────────────────
    print("\n── Example 4: Encoding a TM (Universal Machine concept) ─────────\n")
    print("  Encoding the parity machine as a JSON string (its description ⟨M⟩):\n")
    encoded = encode_tm(parity)
    preview = encoded[:200] + "  …" if len(encoded) > 200 else encoded
    for line in preview.splitlines():
        print(f"    {line}")

    print("\n  Decoding and re-running: same results expected…")
    reconstructed = decode_tm(encoded)
    for n in (0, 2, 4):
        a1, _, _ = parity.run("1" * n)
        a2, _, _ = reconstructed.run("1" * n)
        ok = "✓" if a1 == a2 else "✗"
        print(f"  {ok}  input={'1' * n!r}: original={a1}, reconstructed={a2}")

    # ── 5. Halting problem ─────────────────────────────────────────────────
    halting_problem_demo()


if __name__ == "__main__":
    main()