Convergence Encyclopedia: C20 — Universal Computation

F1 — Tier. T0 (mathematical — Church-Turing thesis is a definition of computability); T3 (pancomputationalism — the claim that physical reality is computational is philosophical, not empirical). Load-bearing only at T0.

F2 — Sources.

• Church, A. (1936). “An unsolvable problem of elementary number theory.” American Journal of Mathematics, 58(2), 345–363.
• Turing, A.M. (1936). “On computable numbers, with an application to the Entscheidungsproblem.” Proceedings of the London Mathematical Society, 42(2), 230–265.
• Post, E.L. (1936). “Finite combinatory processes — formulation 1.” Journal of Symbolic Logic, 1(3), 103–105.
• von Neumann, J. (1945). “First draft of a report on the EDVAC.” Moore School of Electrical Engineering, University of Pennsylvania.
• Wolfram, S. (2002). A New Kind of Science. Wolfram Media. (Principle of computational equivalence — T3.)

F3 — Domains. Mathematics (computability theory), computer science (programming languages, architecture), physics (digital physics — T3), philosophy of mind (computationalism).

F4 — Scale. Formal (symbolic) → physical (silicon, ~10⁻¹⁰ m) → abstract (Turing machine as mathematical object).

F5 — Falsifier. A physical process that cannot be simulated by a Turing machine to arbitrary precision — a “hypercomputer” exploiting physical phenomena beyond computable functions (e.g., Pour-El & Richards 1989 on wave equation computability; speculative quantum gravity computations). Note: The Church-Turing thesis is a hypothesis about physical reality, not a theorem. Its falsification would require demonstrating a physical process that computes a non-recursive function.

F6 — Rival (strongest form). The Church-Turing thesis is a hypothesis about physical reality, not a mathematical theorem. It states that any function computable by any physical process is computable by a Turing machine. This is an empirical generalization, not a proof. It has held for all known computational models (lambda calculus, recursive functions, tag systems, cellular automata, quantum circuits — the latter within BQP), but it could in principle be falsified by a physical hypercomputer. (Copeland 2002 “Hypercomputation” Minds and Machines 12:461; Davis 2004 “The myth of hypercomputation” rebuttal.)

F7 — Independence. HIGH. Church (logic, Princeton), Turing (mathematics, Cambridge), Post (logic, City College New York) — three independent formulations of computability in 1936, published within months of each other, with no cross-communication. von Neumann’s stored-program architecture (1945) was independent of the logical foundations. Wolfram’s principle of computational equivalence (2002) is a later philosophical extension.

F8 — Pattern type. Mathematical.

F9 — Maps. A3 (pattern-dynamics).

---

Corpus map

• Previous: Convergence Encyclopedia: C19
• Next: Convergence Encyclopedia: C21
• Encyclopedia start: The Schema
• Same node, other planes: Catalogue node C20 · Catalogue hub
• Kin corpora: Total Structure · Signature of the Grain