TuringMachine
TuringMachine defines a basic Turing machine via a positive natural number of states and a positive alphabet size. Researchers deriving the Church-Turing thesis from ledger universality in Recognition Science cite it as the entry point to computational models. The declaration is a direct structure definition that enforces non-emptiness through simple inequalities on natural numbers.
claimA Turing machine consists of positive integers $n_s > 0$ (number of states) and $n_a > 0$ (alphabet size).
background
The module Information.ChurchTuring targets derivation of the Church-Turing thesis from Recognition Science via ledger universality: the ledger simulates physical processes, computations are ledger-update sequences, and the 8-tick structure supplies a universal gate set. Upstream dependencies include the Tape type (an infinite sequence of cell states from CellularAutomata), J-cost structures from PhiForcingDerived, spectral emergence of gauge groups and three generations from SpectralEmergence, and ledger factorization from DAlembert. These embed the computational model inside the φ-ladder, D=3 geometry, and eight-tick octave of the forcing chain.
proof idea
This is a structure definition with four fields: two natural-number carriers and two positivity proofs. No lemmas or tactics are invoked; the declaration simply packages the minimal data for a Turing machine configuration.
why it matters in Recognition Science
It supplies the base type for the downstream UniversalTM structure, which asserts simulation of arbitrary machines and thereby supports the module's claim that the Church-Turing thesis follows from ledger universality. The placement aligns with the eight-tick octave (T7) and universal gate set in the Recognition Science forcing chain, grounding effective computation in physical ledger dynamics.
scope and limits
- Does not specify any transition function or tape contents.
- Does not prove existence or universality of any machine.
- Does not connect the structure to ledger updates or 8-tick dynamics.
- Does not address equivalence with lambda calculus or other models.
formal statement (Lean)
46structure TuringMachine where
47 /-- Set of states -/
48 numStates : ℕ
49 /-- Tape alphabet size -/
50 alphabetSize : ℕ
51 /-- Nonempty states -/
52 states_nonempty : numStates > 0
53 /-- Nonempty alphabet -/
54 alphabet_nonempty : alphabetSize > 0
55
56/-- A TM transition: (state, symbol) → (new_state, new_symbol, direction). -/