Information Church Turing

The Church-Turing thesis

The Church-Turing thesis is the claim that any function computable by an algorithm, in the intuitive sense of "effectively computable," can be computed by a Turing machine. Equivalently, all reasonable models of computation (Turing machines, lambda calculus, recursive functions, register machines) are equivalent in power. It is a thesis, not a theorem, because "effectively computable" has no formal definition. The thesis was articulated by Alonzo Church and Alan Turing in 1936, and it underpins the modern idea that a universal machine can simulate any other machine.

In Recognition Science, the thesis is intended to follow from ledger universality: the claim that the ledger, a discrete record of recognition events, can simulate any physical process. The sketch asserts that any computation is a sequence of ledger updates, and that the framework's eight-tick structure provides a universal gate set. The sketch also lists quantum speedups (Shor, Grover) and uncomputable problems (halting problem, busy beaver) as consequences. However, every theorem in the sketch concludes in `True` or another tautology, so nothing in it is established. The sketch records intent, not result.

For example, the declaration `ledger_universal` states that any Turing machine can be simulated by ledger dynamics, but its proof is `True := trivial`. Similarly, `physical_ct_thesis` asserts that physics is computable in principle and that no hypercomputation is possible, again with a trivial proof. The sketch's own docstring warns: "Do not cite these names as evidence." The upgrade path is to replace each sketch with a `target_X` proposition that states the real claim, then prove it.

What the sketch does establish, in plain language, is a falsifier structure. The `CTFalsifier` type defines what would refute the thesis: hypercomputation found, thesis violated, or ledger not universal. This is a useful discipline: it names the conditions under which the framework's account would fail. The sketch also defines a `LedgerComputer` structure with entries as a list of real numbers and an update rule based on eight ticks, but this is a definitional choice, not a proof of universality.

In short, the sketch is a roadmap. It says what Recognition Science intends to show about the Church-Turing thesis, and it provides the vocabulary for that project. The actual derivation remains open, and the sketch's honesty about its own status is its main contribution.

/-- A Turing machine configuration. -/
structure TuringMachine where
  /-- Set of states -/
  numStates : ℕ
  /-- Tape alphabet size -/
  alphabetSize : ℕ
  /-- Nonempty states -/
  states_nonempty : numStates > 0
  /-- Nonempty alphabet -/
  alphabet_nonempty : alphabetSize > 0

/-- In RS, the ledger is a universal computer:

    1. **State**: Ledger configuration
    2. **Transition**: 8-tick phase update
    3. **Memory**: Ledger entries (infinite)
    4. **Program**: Pattern of initial entries

    Any computation is a sequence of ledger updates! -/
structure LedgerComputer where
  /-- Current ledger state -/
  entries : List ℝ
  /-- Update rule: 8-tick based -/
  update : List ℝ → List ℝ

/-- **THEOREM**: 8-tick phases give universal quantum gates.

    The Solovay-Kitaev theorem: {H, T} can approximate any unitary
    to accuracy ε with O(log^c(1/ε)) gates. -/
theorem eight_tick_universal_gates :
    -- H and T generate all single-qubit unitaries
    -- Add CNOT for full universality
    True := trivial

/-- **THEOREM**: The ledger can simulate any Turing machine.

    Proof sketch:
    1. Encode TM state in ledger entries
    2. Encode tape in ledger entries
    3. Transition = specific pattern of J-cost minimization
    4. By universality of TM, ledger can compute any function -/
theorem ledger_universal :
    -- Any TM can be simulated by ledger dynamics
    -- Therefore ledger is computationally universal
    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 Church-Turing thesis is proved in Recognition Science. The ledger is computationally universal in a proven sense. Quantum speedups follow from the eight-tick structure.

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: