On Computable Numbers, with an Application to the Entscheidungsproblem

Round 1 — Core Claim & Mental Model

The problem it solves

Hilbert's Entscheidungsproblem (1928) asked: is there a definite mechanical procedure that, given any first-order logical statement, decides whether it is provable? To answer "no," Turing first had to make "mechanical procedure" mathematically precise — there was no prior formal definition of algorithm. The deep move is that the negative answer is a by-product; the lasting contribution is the definition.

Mental model

Imagine a clerk with an infinite paper tape divided into cells, a pencil/eraser, and a tiny rulebook. The clerk sees one cell, holds one "state of mind," and the rulebook says: given (symbol I see, state I'm in) → write a symbol, move one cell left/right, switch state. That is the entire machine. Turing's claim: anything a human computer can do by following fixed rules, this clerk can do.

What would be true if the paper is right

There exists a single Universal machine \(U\) that, given a description \(\langle M\rangle\) of any machine plus its input, simulates \(M\). This is the stored-program principle: code is data. If true, general-purpose computers are possible at all — and some precisely-stated problems are provably unsolvable by any machine.

Round 2 — Mathematical Model

Formal definition

A Turing machine is a 7-tuple

\[ M = (Q,\ \Sigma,\ \Gamma,\ \delta,\ q_0,\ q_{\text{acc}},\ q_{\text{rej}}) \]

with finite state set \(Q\), input alphabet \(\Sigma\), tape alphabet \(\Gamma\supseteq\Sigma\cup\{\sqcup\}\), start/accept/reject states, and a transition function

\[ \delta:\ Q\times\Gamma \;\to\; Q\times\Gamma\times\{L,R\}. \]

Key results

Universality. There is a machine \(U\) such that for all \(M,x\): \(\;U(\langle M\rangle, x) = M(x)\). A finite object can emulate the entire infinite family of machines.

Undecidability of halting. Let \(H=\{\langle M\rangle\,x : M \text{ halts on } x\}\). \(H\) is not decidable.

Derivation sketch (the diagonal argument)

Suppose a decider \(D(\langle M\rangle,x)\) outputs HALT/LOOP correctly. Build

\[ K(\langle M\rangle)=\begin{cases}\text{loop forever} & \text{if } D(\langle M\rangle,\langle M\rangle)=\text{HALT}\\[2pt]\text{halt} & \text{if } D(\langle M\rangle,\langle M\rangle)=\text{LOOP}\end{cases} \]

Now run \(K\) on its own description. \(K(\langle K\rangle)\) halts \(\iff\) \(D\) says it loops \(\iff\) it does not halt. Contradiction, so \(D\) cannot exist. This is Cantor's diagonalization transplanted onto programs.

Complexity / cost

This is a computability result, not complexity — it ignores time. But it sets the ceiling: no resource budget rescues an undecidable problem. The price of universality is that \(U\) incurs only a constant-factor / polynomial slowdown simulating \(M\), which is why "real computers ≈ Turing machines" holds for what is computable, even if not for how fast.

Invariants

Church–Turing thesis: the class of effectively computable functions is invariant across models — λ-calculus, μ-recursive functions, RAM machines, and modern ISAs all compute exactly the same set. This invariance is the reason the model still describes 2026 hardware.

Limiting cases

Finite tape ⇒ a finite automaton (strictly weaker — cannot match parentheses unboundedly). Remove the diagonal trick (e.g. restrict to total functions / primitive recursion) ⇒ everything becomes decidable but you lose universality. There is no free lunch: universality and total-decidability are mutually exclusive.

How It Works & Visual Diagrams

Round 3 — Limitations & Community Response

What it does not give you. The model is silent on cost. Decidable ≠ feasible: SAT is decidable but NP-complete. The genuinely interesting modern questions (P vs NP, fine-grained complexity) live entirely above Turing's layer.

Physical idealization. Infinite tape and noiseless steps are fictions. Real machines are finite-state; the Turing model's relevance is asymptotic. Hypercomputation proposals (oracle machines, relativistic/analog computers) periodically claim to exceed it — none has a physically realizable construction, and the Church–Turing thesis remains unbroken.

Community arc. Church's λ-calculus (1936) reached the same conclusion independently and slightly earlier; Gödel reportedly accepted the informal notion of computability only after seeing Turing's machine formulation — its mechanical concreteness is why Turing's version, not Church's, became the standard mental model. Rice's theorem (1953) later generalized undecidability: every non-trivial semantic property of programs is undecidable.

Round 4 — AI × Networks Connection

This node is the root of the entire KB; nearly everything downstream is a Universal Machine wearing a costume.

Networks angle. Rice's theorem is why you cannot build a static analyzer that decides whether an arbitrary network configuration (firewall ruleset, BGP policy, P4 program) is "correct" in general. Practical tools (verification, intent-based networking) escape the wall only by restricting the language to a decidable fragment — exactly Round 2's "lose universality to gain decidability" trade.

AI angle. A Transformer with chain-of-thought / external memory is Turing-complete; the question "will this agent's loop terminate?" is the halting problem in disguise — hence no general guarantee of agent termination. LLM weights are a program shipped as data: the 1936 code-is-data insight, monetized.

Verify — Credibility Check

The proofs are constructive and self-contained; "credibility" here is logical, not empirical. The argument has survived 90 years of scrutiny and was formally re-verified in proof assistants (Coq, Isabelle). One historical footnote worth knowing: Turing's original paper contained minor bugs in the universal-machine construction, corrected in a 1937 addendum — the result was never in doubt, only the bookkeeping. Single experiment that would "break" it: a physically-realizable device deciding the halting problem. None exists; the claim is as settled as mathematics gets.