What can be computed?

Can every precisely stated problem be solved by a mechanical procedure?

Several minimal formalisms captured the same class of effective procedures. By encoding procedures as data, they also made self-reference and the limits of procedure mathematically visible.

Formalization is powerful enough to define universal procedure and precise enough to prove that universal problem-solving is impossible.

Reconstruct the mechanism

1. Define a minimal executable formal system
2. Encode a procedure and its input as symbolic data
3. Construct a universal interpreter for encoded procedures
4. Use self-reference or reduction to expose a decision the interpreter cannot make generally

Execute a small Turing machine, sketch a universal interpreter, and explain a reduction showing why a universal halting decider contradicts itself.

Evidence and uncertainty

Parallel models and proofs matter. Resist collapsing Church, Post, Gödel, and Turing into one inevitable lone breakthrough.

• Computable numbers — Turing Digital Archive · King’s College Cambridge
• Early computing at Princeton — Princeton Alumni Weekly