Information Church Turing Halting Undecidable

The halting problem's status

The halting problem is a classical question in computability theory: given a program and an input, can an algorithm decide in finite time whether the program will eventually stop, or run forever? In 1936 Alan Turing proved that no such general algorithm exists. The problem is undecidable: there is no single procedure that answers correctly for every possible program and input. This result is one of the foundational limits of computation, alongside the Church-Turing thesis, which states that any effectively computable function can be computed by a Turing machine.

The Recognition Science framework includes a declaration named halting_undecidable. In plain language, this declaration records the same classical fact: no algorithm can decide halting for all programs. The declaration is a formal statement in the framework's machine-checked library of formal theorems. However, the declaration concludes in True, a tautology. It does not carry a proof of undecidability from the framework's own principles. The declaration is a sketch, not a result; the library's own documentation says so explicitly.

What the declaration does not claim is important. It does not claim to have derived the halting problem's undecidability from the framework's ledger or recognition principles. It does not claim that the framework has a new proof of Turing's theorem. It does not claim that the framework's account of computation, based on a discrete record of events called a ledger, has been shown to reproduce the classical undecidability result. The declaration is an intent marker: it records what the framework aims to establish, not what it has established.

The framework's broader target is to derive the Church-Turing thesis from the idea that the ledger can simulate any physical process. The declaration ledger_universal also concludes in True, meaning it is a sketch as well. The framework does provide a falsifier structure: if hypercomputation were found, or the ledger were shown not to be universal, the thesis would be falsified. But that structure is a definition, not a proof. The classical undecidability of the halting problem stands on Turing's 1936 argument, independent of the framework.

/-- **THEOREM**: The halting problem is undecidable.

    Proof: Diagonal argument (Turing 1936).

    In RS terms: The ledger cannot predict its own halting
    without running itself, which defeats the purpose. -/
theorem halting_undecidable :
    -- No algorithm can decide halting for all programs
    -- This is a fundamental limit
    True := trivial

/-- **THEOREM**: The halting problem is undecidable.

    Proof: Diagonal argument (Turing 1936).

    In RS terms: The ledger cannot predict its own halting
    without running itself, which defeats the purpose. -/
theorem halting_undecidable :
    -- No algorithm can decide halting for all programs
    -- This is a fundamental limit
    True := trivial

/-- The derivation would be falsified if:
    1. Hypercomputation demonstrated
    2. CT thesis violated
    3. Ledger non-universal -/
structure CTFalsifier where
  hypercomputation_found : Prop
  ct_violated : Prop
  ledger_not_universal : Prop
  falsified : hypercomputation_found ∨ ct_violated → False

What this page does not claim

The framework has proved the halting problem is undecidable from its own principles. The declaration halting_undecidable is a theorem with a substantive proof. The framework has established the Church-Turing thesis or the universality of the ledger.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Information/ChurchTuring.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: