VCML Paper 108: VCML Simulates Rule 110 -- Closing the Godel Chain via Cook 2004
Abstract
Closes Bridge 2 of the VCML-Godel chain by proving VCML simulates Rule 110, a Turing-complete elementary cellular automaton (Cook 2004). Rule110.lean (ZERO SORRY, 2 classical axioms): (1) rule110_nand_correct: 15-NAND circuit = Rule-110 truth table, proved by decide (8 Bool triples). (2) vcml_implements_rule110: VCML computes Rule 110 via NAND (from TuringUniversal.lean). (3) cook_rule110_is_universal: axiom (Cook 2004, Complex Systems 15). (4) vcml_turing_universal_r110: VCML is Turing universal. (5) turing_halting_undecidable: axiom (Turing 1936). (6) vcml_has_undecidable_halting: VCML has Godel sentences. All Lean proofs zero sorry. Two axioms are classical published theorems. Empirical verification (paper108_rule110.py): Rule-110 truth table PASS, NAND circuit 8/8 PASS, VCML=NAND 4/4 PASS, simulation 21/21 steps PASS. Combined with Papers 102-107 and 5 Lean files: VCML-Godel chain complete.
Fields of Study & Subjects
Computability
Logic
AI Algorithms
programming
and type systems
Cellular Automata and Applications
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 13 March 2026
- Language
- EN
- Document type
- Preprint