VCML Paper 108: VCML Simulates Rule 110 -- Closing the Godel Chain via Cook 2004

Read full text
Authors: Gabriel Aubin-Moreau
Cited by: 0

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