Uniform mortality of deterministic Turing machines

Lax503819.Mortality · concepts/Lax503819/Mortality.lean · lax-503819

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    A deterministic machine has finitely many states and tape symbols, and a partial transition table. Each transition writes a symbol, changes state, and moves exactly one cell left or right. There is no distinguished initial state: mortality concerns every configuration.

    We use finite tape segments, halting when a transition is absent or the head would leave the segment. Mortality means that one bound works for every segment length, every tape content, every head position and every state. This is the bounded finite-configuration formulation in Section 6.2. It is equivalent to uniform mortality on unbounded tapes: every finite run uses a finite segment, and every segment run embeds in an unbounded tape. The connection to the infinite-run formulation of Hooper's theorem additionally uses compactness, and belongs to the proof obligation, not the definition.

    States are 0,…,states−1 and symbols 0,…,symbols−1, where the stored counts are increased by one to keep them nonempty. Table rows are indexed by states, columns by symbols. Missing entries halt; output numbers are reduced modulo the respective sizes. truetrue means move right. These conventions describe all deterministic machines and give an effective interpretation of every table.

    Concept map
    1 concept; 1 descendant hidden
    100%
    Proven claimThis conceptRelated conceptA → B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Mathlib.Computability.Reduce
    2import Mathlib.Computability.Primrec.List
    3
    4/-!
    5---
    6title: Uniform mortality of deterministic Turing machines
    7type: theorem
    8---
    9A deterministic machine has finitely many states and tape symbols, and a
    10partial transition table. Each transition writes a symbol, changes state,
    11and moves exactly one cell left or right. There is no distinguished initial
    12state: mortality concerns every configuration.
    13
    14We use finite tape segments, halting when a transition is absent or the head
    15would leave the segment. Mortality means that one bound works for every
    16segment length, every tape content, every head position and every state.
    17This is the bounded finite-configuration formulation in Section 6.2. It is
    18equivalent to uniform mortality on unbounded tapes: every finite run uses a
    19finite segment, and every segment run embeds in an unbounded tape. The
    20connection to the infinite-run formulation of Hooper's theorem additionally
    21uses compactness, and belongs to the proof obligation, not the definition.
    22
    23States are 0,…,states−1 and symbols 0,…,symbols−1, where the stored counts
    24are increased by one to keep them nonempty. Table rows are indexed by states,
    25columns by symbols. Missing entries halt; output numbers are reduced modulo
    26the respective sizes. `true` means move right. These conventions describe
    27all deterministic machines and give an effective interpretation of every table.
    28-/
    29
    30namespace Lax503819.Mortality
    31
    32abbrev Instruction := ℕ × ℕ × Bool
    33
    34structure Machine where
    35 statesMinusOne : ℕ
    36 symbolsMinusOne : ℕ
    37 table : List (List (Option Instruction))
    38
    39instance : Primcodable Machine :=
    40 Primcodable.ofEquiv (ℕ × ℕ × List (List (Option Instruction)))
    41 { toFun := fun m => (m.statesMinusOne, m.symbolsMinusOne, m.table)
    42 invFun := fun (q, a, t) => ⟨q, a, t⟩
    43 left_inv := fun _ => rfl
    44 right_inv := fun _ => rfl }
    45
    46structure Configuration where
    47 state : ℕ
    48 tape : List ℕ
    49 head : ℕ
    50
    51def WellFormed (m : Machine) (c : Configuration) : Prop :=
    52 c.state < m.statesMinusOne + 1
    53 (∀ a ∈ c.tape, a < m.symbolsMinusOne + 1) ∧ c.head < c.tape.length
    54
    55/-- A step on a finite tape; leaving its boundary halts. -/
    56def step (m : Machine) (c : Configuration) : Option Configuration := do
    57 let a ← c.tape[c.head]?
    58 let (q, b, right) ← (m.table.getD c.state []).getD a none
    59 if !right && c.head == 0 then none else
    60 let h := if right then c.head + 1 else c.head - 1
    61 if h < c.tape.length then
    62 some ⟨q % (m.statesMinusOne + 1),
    63 c.tape.set c.head (b % (m.symbolsMinusOne + 1)), h⟩
    64 else none
    65
    66/-- After n attempts to take a step, `none` means that the run has halted. -/
    67def run (m : Machine) : ℕ → Configuration → Option Configuration
    68 | 0, c => some c
    69 | n + 1, c => (step m c).bind (run m n)
    70
    71def Mortal (m : Machine) : Prop :=
    72 ∃ n : ℕ, ∀ c : Configuration, WellFormed m c → run m n c = none
    73
    74/-- Hooper's undecidability theorem, in its uniform finite-tape form. -/
    75axiom mortality_undecidable : ¬ ComputablePred Mortal
    76
    77end Lax503819.Mortality
    78
    Show Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…