Node C20: Universal Computation
Node C20: Universal Computation
C20 — Universal Computation { "id": "C20", "claim": "One abstract machine (Turing machine / lambda calculus) can simulate any other; some physical processes are computationally irreducible — no shortcut to their outcome exists.", "domain": ["mathematical logic", "computer science", "theoretical physics", "cellular automata"], "pattern": ["universality", "Turing_completeness", "computational_irreducibility", "simulation"], "mechanism": "Church-Turing thesis: any effectively calculable function is computable by a Turing machine. Universal Turing machine: a single machine that can simulate any other Turing machine given its description and input. Computational irreducibility (Wolfram): for some systems, the only way to determine the outcome is to run the full computation — no predictive compression exists.", "scale": "abstract → physical", "claim_tier": "T0 (core logic) / T3 (pancomputationalism)", "sources": [ "Church, A. (1936). 'An Unsolvable Problem of Elementary Number Theory.' Am. J. Math., 58, 345-363.", "Turing, A.M. (1936). 'On Computable Numbers, with an Application to the Entscheidungsproblem.' Proc. Lond. Math. Soc., 42, 230-265.", "von Neumann, J. (1945). 'First Draft of a Report on the EDVAC.' Moore School.", "Wolfram, S. (2002). A New Kind of Science. Wolfram Media. [Computational irreducibility, Rule 110.]" ], "dual": "Non-computable — a process that cannot be simulated by any Turing-equivalent machine; hypercomputation.", "falsifier": "A physical process provably non-simulable by any Turing machine — e.g., a system exploiting real numbers with infinite precision, or a quantum gravitational process beyond Turing computation. (Note: quantum computation is still within the extended Church-Turing thesis.)", "rival_frame": "The Church-Turing thesis is a hypothesis about physical reality, not a theorem. It may fail at quantum or biological scales. 'Computational irreducibility' is a vacuous claim — it says 'some things are hard to predict,' which is trivial. Wolfram's pancomputationalism is speculative metaphysics, not science.", "independence_check": "HIGH. Church (logic, Princeton, 1936) derived computability from lambda calculus. Turing (mathematics, Cambridge/Princeton, 1936) derived it from mechanical procedures and the Entscheidungsproblem. von Neumann (engineering, IAS, 1945) designed the stored-program computer architecture independently. Wolfram (physics/UIUC, 2002) derived irreducibility from cellular automata. Four independent origins, same concept: universal simulation.", "pattern_type": "mathematical", "maps_to_axiom": ["A3"] }
---
Corpus map
- Same node, other planes: Encyclopedia C20 · Inventory invariant
- Catalogue hub: Public Article · Schema