Turing Machines & the Church-Turing Thesis

Before Turing, the word 'algorithm' was informal — it meant a step-by-step recipe, something a human could follow mechanically. But 'mechanically' itself was undefined. In the 1930s, three independent researchers — Alonzo Church (lambda calculus), Alan Turing (Turing machines), and Emil Post (Post correspondence systems) — each tried to make this precise. They arrived at different formalisms and then proved them all equivalent. This convergence is strong evidence that they had captured something real about the nature of computation.

Turing's key insight was to model the most general human computation process: a person sitting at a desk, with an infinite pad of paper, a pencil, and a finite set of rules. At each step, the person looks at the current symbol on the paper, consults their rules, and either writes a new symbol, moves attention left or right, or halts. This abstraction strips away everything inessential — speed, physical medium, cleverness — and keeps only the logical structure of sequential symbol manipulation.

The resulting model is surprisingly powerful. Any computation a modern computer can perform can be expressed as a Turing machine, just (often) much more slowly. The model's simplicity is a feature: it is simple enough to reason about mathematically, yet expressive enough to capture all computation. This is the key trade-off in any formal model.

A Turing machine M is a 7-tuple: M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject), where:

• Q is a finite, non-empty set of states.
• Σ is the input alphabet, not containing the blank symbol ␣.
• Γ is the tape alphabet, with Σ ⊂ Γ and ␣ ∈ Γ.
• δ: Q × Γ → Q × Γ × {L, R} is the transition function. Given the current state and the symbol under the head, it returns the new state, the symbol to write, and a direction to move (Left or Right).
• q₀ ∈ Q is the start state.
• q_accept ∈ Q is the accept state.
• q_reject ∈ Q is the reject state, with q_accept ≠ q_reject.

The tape is infinite in one direction (or both, depending on convention — they are equivalent). Initially, the input string w is written on positions 1 through |w|, the rest is blank (␣), and the head is at position 1.

At each step, the machine reads the symbol under the head, looks up δ, writes the new symbol, moves the head, and transitions to the new state. If it enters q_accept, it accepts. If it enters q_reject, it rejects. If it loops forever, it loops (does not halt).

This is subtle: a TM can fail to answer in one of two ways — explicit rejection (reaches q_reject) or looping. This distinction matters enormously for decidability vs. recognizability.

# Pseudocode: a simple TM that accepts strings of the form 0^n 1^n
# States: q_start, q_scan_right, q_match, q_scan_left, q_accept, q_reject
# Tape alphabet: {0, 1, X, Y, blank}
#
# Idea: repeatedly cross off one 0 (mark as X) and one 1 (mark as Y)
# until both are exhausted simultaneously.

transitions = {
    # (state, symbol) -> (new_state, write_symbol, direction)
    ('q_start', '0'):   ('q_scan_right', 'X', 'R'),  # cross off leftmost 0
    ('q_start', 'Y'):   ('q_check', 'Y', 'R'),
    ('q_start', blank): ('q_accept', blank, 'R'),

    ('q_scan_right', '0'):  ('q_scan_right', '0', 'R'),  # scan past 0s
    ('q_scan_right', 'Y'):  ('q_scan_right', 'Y', 'R'),  # scan past Ys
    ('q_scan_right', '1'):  ('q_scan_left', 'Y', 'L'),   # cross off matching 1
    ('q_scan_right', blank): ('q_reject', blank, 'R'),   # no 1 to match

    ('q_scan_left', '0'):  ('q_scan_left', '0', 'L'),   # scan back left
    ('q_scan_left', 'Y'):  ('q_scan_left', 'Y', 'L'),
    ('q_scan_left', 'X'):  ('q_start', 'X', 'R'),       # found X, start again

    ('q_check', 'Y'):   ('q_check', 'Y', 'R'),
    ('q_check', blank): ('q_accept', blank, 'R'),
    ('q_check', '1'):   ('q_reject', '1', 'R'),
}

To reason formally about what a TM does at each step, we use the notion of a configuration. A configuration captures the complete instantaneous state of the machine:

Configuration = (current state, tape contents, head position)

Conventionally written as: u q v where q is the current state, u is the tape content to the left of the head, and v is the tape content from the head rightward (the first character of v is under the head).

For example: 011 q₃ 01# means the head is at the start of 01#, the tape reads 011 01#, and the machine is in state q₃.

We write C₁ ⊢ C₂ to mean configuration C₁ yields C₂ in one step. The machine M accepts input w if there is a sequence of configurations:

C_start ⊢ C₁ ⊢ C₂ ⊢ ... ⊢ C_accept

where C_start = q₀w (initial config) and C_accept contains q_accept.

This rigorous notion of computation as a sequence of configurations is important. It:

• Makes 'step' completely precise
• Allows us to count steps (time complexity)
• Allows us to bound space usage (measure tape used)
• Underlies the Cook-Levin theorem and all of complexity theory

The language of a TM M is L(M) = {w ∈ Σ* | M accepts w}. Languages recognized by some TM are called Turing-recognizable (or recursively enumerable). Languages decided by some TM that always halts are called decidable (or recursive). Every decidable language is Turing-recognizable, but not vice versa.

# Simulating configurations in Python
from collections import defaultdict

def simulate_tm(transitions, start, accept, reject, input_str, max_steps=10000):
    tape = defaultdict(lambda: '_')  # blank = '_'
    for i, ch in enumerate(input_str):
        tape[i] = ch
    head = 0
    state = start
    for step in range(max_steps):
        symbol = tape[head]
        if state == accept:
            return 'ACCEPT'
        if state == reject:
            return 'REJECT'
        key = (state, symbol)
        if key not in transitions:
            return 'REJECT'  # implicit reject on missing transition
        new_state, write, direction = transitions[key]
        tape[head] = write
        state = new_state
        head += (1 if direction == 'R' else -1)
    return 'LOOP (exceeded max_steps)'

The standard TM has one tape and one head. Many variants exist and are all equivalent in power (they recognize the same class of languages, though they may differ in efficiency).

A k-tape Turing machine has k tapes, each with its own read/write head. Its transition function is δ: Q × Γᵏ → Q × Γᵏ × {L, R}ᵏ. This is dramatically more convenient for algorithms (you can use different tapes as 'registers', a 'work scratch pad', etc.).

Theorem: Every k-tape TM has an equivalent single-tape TM.

Proof sketch (simulation): Encode all k tapes on one tape by interleaving. Use separator symbols. Mark the current head position on each virtual tape with a dot. A single-tape simulation sweeps back and forth across the encoded tape to simulate each step. If the multitape TM takes t steps, the simulation takes O(t²) steps (each step requires a linear sweep over content that may have grown linearly). This polynomial slowdown is crucial in complexity theory (it shows DTIME[t] on k-tape ⊆ DTIME[t²] on 1-tape).

The key insight: computational power (what can be computed) is the same, but efficiency (how fast) may differ. This separation of concerns — language class vs. complexity class — is fundamental.

# Conceptual encoding of 2-tape TM onto 1-tape:
# Original: tape1 = 'ab_...', tape2 = 'cd_...'
# Encoded:  '#a.b_#c.d_' (dots mark head position, # separate tapes)
# Each original step:
#   1. Sweep right to find all dotted symbols, record them
#   2. Sweep left applying transitions, update dotted symbols and directions
# Total overhead: O(tape_length) per original step
# If original uses t steps, tape can be at most t long, so total = O(t^2)

A nondeterministic Turing machine (NTM) is one where the transition function can have multiple possible outputs for a given (state, symbol) pair: δ: Q × Γ → P(Q × Γ × {L, R}). At each step, the machine may 'branch' into multiple computational threads, each following one choice.

An NTM accepts an input if at least one branch of its computation leads to an accept state.

Picture it as a tree of configurations: the root is the start configuration, each node branches into children (one per valid transition choice), and the machine accepts if any leaf in this tree is an accepting configuration.

NTMs are not meant to model a real machine — they are a mathematical tool. They capture the idea of 'guessing' a certificate: if you can nondeterministically guess a solution and verify it, then an NTM can accept your language.

Theorem: Every NTM has an equivalent deterministic TM (a DTM).

Proof sketch: The DTM simulates the NTM by doing a breadth-first search over the tree of configurations. It uses 3 tapes: one holds the input, one simulates the current branch, and one tracks which node in the BFS tree to explore next. The search explores all configurations level by level (by length of computation path), accepting if it ever finds an accept configuration.

Key asymmetry: The DTM simulation may be exponentially slower than the NTM (the BFS tree can have exponentially many nodes). Whether we can do better — whether every NTM-polynomial-time problem has a DTM-polynomial-time solution — is exactly the P vs NP question.

# NTM simulation via BFS over configuration tree
# Each 'configuration' = (state, tape_dict, head_position)
# We explore all configurations reachable in 1 step, then 2, etc.

from collections import deque

def simulate_ntm(ntm_transitions, start, accept, reject, input_str):
    """
    ntm_transitions: dict (state, symbol) -> list of (new_state, write, dir)
    Returns True if any branch accepts.
    """
    def config_to_key(state, tape, head):
        return (state, tuple(sorted(tape.items())), head)

    init_tape = {i: ch for i, ch in enumerate(input_str)}
    queue = deque([(start, init_tape, 0)])
    visited = set()

    while queue:
        state, tape, head = queue.popleft()
        if state == accept:
            return True
        if state == reject:
            continue
        key = config_to_key(state, tape, head)
        if key in visited:
            continue
        visited.add(key)
        symbol = tape.get(head, '_')
        for new_state, write, direction in ntm_transitions.get((state, symbol), []):
            new_tape = dict(tape)
            new_tape[head] = write
            new_head = head + (1 if direction == 'R' else -1)
            queue.append((new_state, new_tape, new_head))
    return False

An enumerator is a TM variant that outputs (prints) strings rather than accepting or rejecting them. It has an output tape and a special 'print' command. It runs indefinitely, printing a (possibly infinite, possibly with repetitions) list of strings.

The language enumerated by E is the set of all strings it ever prints: L(E) = {w | E eventually prints w}.

Theorem: A language L is Turing-recognizable if and only if some enumerator enumerates it.

Proof (→): Given a TM M that recognizes L, construct enumerator E: for n = 1, 2, 3, ..., run M on each string in Σ* of length ≤ n for n steps. Print any that accept. This interleaving ensures every string that M eventually accepts is eventually printed.

Proof (←): Given enumerator E, construct TM M that recognizes L(E): on input w, run E and accept when (if ever) it prints w.

This equivalence reveals a beautiful truth: Turing-recognizable languages are exactly those that can be systematically listed, even if the listing takes forever and you can't tell if a string is absent. Decidable languages are exactly those where you can both enumerate the language and enumerate its complement (Kleene's theorem).

Enumerators also show why we care about the distinction: a recognizer might run forever on a non-member (not useful in practice), but if you only need to search for solutions (like in automated theorem proving), recognition is sufficient.

# Enumerator for the language {0^n 1^n | n >= 0}
# Just generates strings in order and checks membership

def enumerator_0n1n():
    """Generator that yields strings in L = {0^n 1^n | n >= 1}"""
    n = 1
    while True:  # runs forever, printing each member
        yield '0' * n + '1' * n
        n += 1

# Corresponding recognizer: given input w, check if enumerator ever prints w
def recognizer_0n1n(w):
    """Accept iff w is in {0^n 1^n}"""
    for s in enumerator_0n1n():
        if s == w:
            return True
        if len(s) > len(w):  # strings only get longer
            return False     # w is not in the language

The Church-Turing Thesis (CTT) states:

Every function that is effectively computable by any algorithm can be computed by a Turing machine.

This is not a theorem — it cannot be proven because 'effectively computable' and 'algorithm' are informal, intuitive concepts. The CTT is a claim about the relationship between an informal notion and a formal one.

The evidence for the CTT is overwhelming:

1. Convergence: Lambda calculus, TMs, Post correspondence, μ-recursive functions, RAM machines, register machines — all independently defined, all proven equivalent.
2. Robustness: Every reasonable variation of the TM model (multitape, nondeterministic, 2D tape, probabilistic, etc.) is equivalent in power.
3. No counterexamples: Despite decades of effort, no one has produced a physically realizable computational model that computes something a TM cannot.
4. Physical Church-Turing Thesis: Extended versions claim that even quantum computers do not exceed TM power (though they may be vastly faster). This remains an open conjecture.

A crucial corollary: if you give a precise algorithmic description of a problem (a finite, terminating set of rules), the CTT licenses us to say 'a TM can solve it' without explicitly constructing the TM. In practice, we often describe algorithms in pseudocode or high-level languages and appeal to the CTT to conclude a TM exists.

The CTT also gives us a definition: we define 'algorithm' to mean 'TM'. This is how CS theory bootstraps itself. Every theorem in computability theory uses this definition.

To reason about Turing machines as inputs to other Turing machines, we need a way to encode a TM as a string. This is a crucial conceptual step — it turns TMs from mathematical objects into data.

Since a TM M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject) is finite, we can encode it as a string over {0, 1}. The standard notation is ⟨M⟩ for the encoding of M, and ⟨M, w⟩ for the encoding of the pair (M, w).

This encoding is like source code: a string of symbols that describes a computation. Some TMs take the description of other TMs as input. This self-referential quality is what enables:

• The Universal Turing Machine (a TM that runs any TM)
• Undecidability proofs (diagonalization over all TM descriptions)
• Rice's Theorem (properties of programs are undecidable)

The encoding is not unique — many valid encodings exist. What matters is that:

1. Every TM has at least one valid encoding.
2. Given ⟨M⟩, we can (algorithmically) recover M.
3. We can enumerate all valid encodings in some order.

An important convention: every string is a valid 'encoding' — strings that don't parse as a valid TM description are treated as encoding some fixed trivial machine (e.g., one that immediately rejects everything). This avoids edge cases in proofs.

# Conceptual encoding of a TM as a string
# A TM with states {q0, q1, q_acc, q_rej}, tape alphabet {0, 1, B}
# can be encoded by listing transitions:
# Format: state_index symbol_index new_state_index write_symbol_index direction
# All separated by # with states/symbols assigned canonical indices

# Example: encode delta(q0, 0) = (q1, 1, R) as "0 0 1 1 R"
# Full encoding of M = concatenation of all transition rows, separated by ## 

def encode_tm(transitions):
    """
    transitions: list of (state, read, new_state, write, direction) tuples
    Returns a string encoding of the TM.
    """
    rows = []
    for (q, r, q2, w, d) in transitions:
        rows.append(f"{q}#{r}#{q2}#{w}#{d}")
    return "##".join(rows)

The Universal Turing Machine U is a single TM that, given the encoding ⟨M, w⟩ as input, simulates the computation of M on w. If M accepts w, U accepts. If M rejects w, U rejects. If M loops on w, U loops.

Why this is astonishing: Before the UTM, a 'computer' was a single-purpose machine — you built a different device for each computation. The UTM shows that a single, fixed machine can simulate any other machine, given a description. This is the theoretical invention of the stored-program computer — the idea that code and data live in the same memory and a processor interprets the code.

Von Neumann and colleagues, building ENIAC and EDVAC, independently discovered the stored-program idea. But Turing had the mathematical version a decade earlier.

How U works (sketch):

1. U has 3 tapes (using multitape equivalence): the description ⟨M⟩, the simulated tape of M, and a record of M's current state.
2. Each step: look up the current state of M and the symbol under M's head in ⟨M⟩'s transition table, update the simulated tape and state accordingly.

Consequences:

• The language of U, L(U) = {⟨M, w⟩ | M accepts w}, is Turing-recognizable. This language is called A_TM (the acceptance problem).
• A_TM is NOT decidable (we will see why via diagonalization — if a TM could decide A_TM, we could construct a paradoxical TM).
• The UTM's existence means undecidability is not about insufficient cleverness — it's a structural fact about self-reference.

# High-level structure of a Universal TM simulator in Python
# (A real implementation; uses Python as a high-level TM)

def universal_tm(tm_description, input_string):
    """
    Simulates TM described by tm_description on input_string.
    tm_description: dict with 'transitions', 'start', 'accept', 'reject'
    Returns 'ACCEPT', 'REJECT', or loops forever.
    """
    M = parse_tm_description(tm_description)  # decode <M>
    # Now simulate M on input_string step by step
    tape = list(input_string) + ['_'] * 1000
    state = M['start']
    head = 0
    while True:
        if state == M['accept']:
            return 'ACCEPT'
        if state == M['reject']:
            return 'REJECT'
        symbol = tape[head] if 0 <= head < len(tape) else '_'
        key = (state, symbol)
        if key not in M['transitions']:
            return 'REJECT'  # stuck = reject
        new_state, write, direction = M['transitions'][key]
        tape[head] = write
        state = new_state
        head += 1 if direction == 'R' else -1
        # Note: no termination check — this CAN loop forever, matching UTM semantics

def parse_tm_description(desc):
    return desc  # assume already structured for clarity

A language L is decidable if there exists a TM M that always halts, accepts every string in L, and rejects every string not in L. A decider (or total TM) always halts.

A language is Turing-recognizable (RE) if some TM accepts exactly its members (but may loop on non-members).

The most famous undecidable problem: the halting problem.

Define: HALT_TM = {⟨M, w⟩ | M halts (accepts or rejects) on input w}

Theorem: HALT_TM is undecidable.

But the canonical starting point is usually A_TM = {⟨M, w⟩ | M accepts w}.

Theorem: A_TM is undecidable. (Turing 1936)

Proof (diagonalization): Assume for contradiction that some TM H decides A_TM. So:

• H(⟨M, w⟩) = accept if M accepts w
• H(⟨M, w⟩) = reject if M does not accept w

Construct TM D: on input ⟨M⟩, run H on ⟨M, ⟨M⟩⟩, then do the opposite:

• If H accepts, then D rejects.
• If H rejects, then D accepts.

Now ask: what does D do on input ⟨D⟩?

• If D accepts ⟨D⟩, then H accepts ⟨D, ⟨D⟩⟩, meaning D accepts ⟨D⟩ — but then D should reject. Contradiction.
• If D rejects ⟨D⟩, then H rejects ⟨D, ⟨D⟩⟩, meaning D does not accept ⟨D⟩ — but then D should accept. Contradiction.

Either way, contradiction. So H cannot exist. A_TM is undecidable.

This argument is Cantor's diagonalization in disguise — the same technique used to prove the reals are uncountable. It is one of the most important proof techniques in mathematics.

# The diagonalization argument, made vivid as a table:
#
# Build an infinite table: rows = TMs M1, M2, M3, ...
#                          cols = their encodings <M1>, <M2>, <M3>, ...
# Entry (i,j) = 'A' if Mi accepts <Mj>, 'R' otherwise
#
# D is defined to *flip* the diagonal:
# D on input <Mi>: opposite of what Mi does on <Mi>
#
# D's behavior on the diagonal:
#   D(<M1>) = opposite of M1(<M1>)
#   D(<M2>) = opposite of M2(<M2>)
#   D(<D>)  = ??? (row for D must disagree with EVERY row)
#
# => D cannot be any Mi in the table
# => The assumption that H can decide A_TM is false

#         <M1>  <M2>  <M3>  ...  <D>  ...
# M1   [  A     R     A    ...  ???  ]
# M2   [  R     A     R    ...  ???  ]
# M3   [  A     A     R    ...  ???  ]
# ...  [  ...                        ]
# D    [  R     R     A    ...  ???  ]  <- D flips diagonal: R,R,A,...
# If D is Mk, then D(<Mk>) = flip of Mk(<Mk>) = flip of D(<Mk>). Paradox.

How do we prove that problems other than A_TM are undecidable? We use reductions.

A mapping reduction from language A to language B (written A ≤_m B) is a computable function f: Σ* → Σ* such that for all w: w ∈ A ⟺ f(w) ∈ B.

Informally: 'solving B solves A'. If we can transform any instance of A into an instance of B (preserving membership), then B is at least as hard as A.

Key theorem: If A ≤_m B and B is decidable, then A is decidable. Equivalently (contrapositive): if A ≤_m B and A is undecidable, then B is undecidable.

Example: HALT_TM ≤_m A_TM. Given ⟨M, w⟩, define M' that runs M on w; if M halts and accepts, accept; if M halts and rejects, accept (we change reject to accept). Now M halts on w ⟺ M' accepts w. So a decider for A_TM gives a decider for HALT_TM.

Rice's Theorem: Every non-trivial property of the language of a TM is undecidable. More precisely: let P be a property of TM languages (a set of Turing-recognizable languages) that is non-trivial (some TMs have it, some don't). Then {⟨M⟩ | L(M) ∈ P} is undecidable.

This is sweeping: you cannot decide if a TM's language is empty, finite, regular, context-free, contains a specific string, or anything else non-trivial. This is why perfect static analysis is impossible in general.

# Illustration of a mapping reduction in Python
# Reducing HALT_TM to A_TM:
# f(<M, w>) = <M', w> where M' is M modified to not reject

def reduce_halt_to_atm(M_encoding, w):
    """
    Given (M, w) for HALT_TM, produce (M', w) for A_TM.
    M' simulates M but converts all REJECTs to ACCEPTs.
    """
    M = parse_tm_description(M_encoding)
    M_prime = dict(M)
    # In M', whenever M would reject, instead accept
    M_prime['reject'] = M_prime['accept']  # make reject = accept state
    # Now M' accepts iff M halts (either accepts or rejects)
    # M' loops iff M loops
    return (encode_tm_description(M_prime), w)

# If we had a decider D_A for A_TM:
#   D_HALT(M, w) = D_A(reduce_halt_to_atm(M, w))
# Since D_HALT would decide HALT_TM (known undecidable),
# D_A cannot exist => A_TM is undecidable (alternate proof route)

The full landscape of language complexity has a clean structure at the computability level:

Decidable (Recursive): Languages where a TM always halts and decides membership. Closed under complement, union, intersection, concatenation. Examples: any regular language, any CFL, any language over a fixed finite alphabet with a decidable property. Also: the language of valid propositional tautologies (co-NP-complete, but decidable), satisfiability (NP-complete, decidable).

Turing-Recognizable (RE): Strictly larger. A TM accepts members but may loop on non-members. A_TM is the canonical example. Closed under union and intersection, but NOT closed under complement.

Co-Turing-Recognizable (co-RE): The complement of an RE language. A TM rejects non-members but may loop on members. The complement of A_TM, called Ā_TM, is co-RE but not RE.

Key theorem: L is decidable ⟺ L is both RE and co-RE. Proof: if L and its complement are both RE, run their recognizers in parallel; one must halt. This gives a decider.

Non-RE languages: Most languages are not even Turing-recognizable. A counting argument: there are uncountably many languages (2^|Σ*|) but only countably many TMs (each is a finite string). So 'most' problems are completely beyond computation. A_TM is at the 'easy end' of undecidability.

This hierarchy is analogous to — and the inspiration for — the polynomial hierarchy (P ⊆ NP, co-NP, PH...) in complexity theory. The same structural intuitions apply at different scales.

# The parallel recognizer technique: deciding L when L and ~L are both RE
# This shows decidable = RE ∩ co-RE

import threading

def parallel_decider(recognizer_L, recognizer_complement_L, input_str):
    """
    Given recognizers for L and its complement, decide L.
    One of them MUST eventually accept; we return based on which one does.
    (In a real TM this is interleaved, not parallel threads)
    """
    result = [None]

    def run_L():
        if recognizer_L(input_str):  # accepts iff w in L
            result[0] = 'ACCEPT'

    def run_comp():
        if recognizer_complement_L(input_str):  # accepts iff w not in L
            result[0] = 'REJECT'

    # Simulate by interleaving steps of both recognizers
    # (real TM uses a 2-tape NTM or step-by-step interleaving)
    t1 = threading.Thread(target=run_L)
    t2 = threading.Thread(target=run_comp)
    t1.start(); t2.start()
    # The first to finish gives the answer
    # Exactly one will finish (since L and ~L partition Sigma*)
    t1.join(); t2.join()
    return result[0]