Uniform mortality of deterministic Turing machines
Lax503819.Mortality · concepts/Lax503819/Mortality.lean · lax-503819
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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. means move right. These conventions describe all deterministic machines and give an effective interpretation of every table.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Computability.Reduce |
| 2 | import Mathlib.Computability.Primrec.List |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Uniform mortality of deterministic Turing machines |
| 7 | type: theorem |
| 8 | --- |
| 9 | A deterministic machine has finitely many states and tape symbols, and a |
| 10 | partial transition table. Each transition writes a symbol, changes state, |
| 11 | and moves exactly one cell left or right. There is no distinguished initial |
| 12 | state: mortality concerns every configuration. |
| 13 | |
| 14 | We use finite tape segments, halting when a transition is absent or the head |
| 15 | would leave the segment. Mortality means that one bound works for every |
| 16 | segment length, every tape content, every head position and every state. |
| 17 | This is the bounded finite-configuration formulation in Section 6.2. It is |
| 18 | equivalent to uniform mortality on unbounded tapes: every finite run uses a |
| 19 | finite segment, and every segment run embeds in an unbounded tape. The |
| 20 | connection to the infinite-run formulation of Hooper's theorem additionally |
| 21 | uses compactness, and belongs to the proof obligation, not the definition. |
| 22 | |
| 23 | States are 0,…,states−1 and symbols 0,…,symbols−1, where the stored counts |
| 24 | are increased by one to keep them nonempty. Table rows are indexed by states, |
| 25 | columns by symbols. Missing entries halt; output numbers are reduced modulo |
| 26 | the respective sizes. `true` means move right. These conventions describe |
| 27 | all deterministic machines and give an effective interpretation of every table. |
| 28 | -/ |
| 29 | |
| 30 | namespace Lax503819.Mortality |
| 31 | |
| 32 | abbrev Instruction := ℕ × ℕ × Bool |
| 33 | |
| 34 | structure Machine where |
| 35 | statesMinusOne : ℕ |
| 36 | symbolsMinusOne : ℕ |
| 37 | table : List (List (Option Instruction)) |
| 38 | |
| 39 | instance : 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 | |
| 46 | structure Configuration where |
| 47 | state : ℕ |
| 48 | tape : List ℕ |
| 49 | head : ℕ |
| 50 | |
| 51 | def 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. -/ |
| 56 | def 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. -/ |
| 67 | def run (m : Machine) : ℕ → Configuration → Option Configuration |
| 68 | | 0, c => some c |
| 69 | | n + 1, c => (step m c).bind (run m n) |
| 70 | |
| 71 | def 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. -/ |
| 75 | axiom mortality_undecidable : ¬ ComputablePred Mortal |
| 76 | |
| 77 | end Lax503819.Mortality |
| 78 |
Builds on
none
Used by
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments