two_way_dfa_halting_empty
Sanity: a two-state automaton with no transitions and s ≠ f halts on every input.
Statement
theorem two_way_dfa_halting_empty {σ : Type*} : two_way_dfa_halting (⟨fun _ _ => none, fun _ => none, fun _ => none, 0, 1⟩ : two_way_dfa σ (Fin 2))
- Source
- sanity lemma for two_way_dfa_halting
- Verified
- 23 Oct 2026
- Axioms
Quot.soundpropext- Built on 4
- two_way_dfaA two-way deterministic finite automaton over the alphabet σ with state set Q: a partial transition δ(q, a) ∈ Q × {left (false), right…
- two_way_dfa_runThe configuration after t steps of the computation from (s, 0) on w, or none once it has halted on an undefined transition.
- two_way_dfa_stepOne step on the input w: in configuration (q, i), at position 0 (left endmarker) apply δL and move to 1, at position |w|+1 (right…
- two_way_dfa_haltingA is halting: on every input its computation stops, by an undefined transition or by reaching the accepting configuration (f, 0).
The proof, explained
The empty two-way automaton has no transitions defined anywhere and starts at the left end-marker (position 0) in state 0. Choosing t = 1, a single step evaluates the left-boundary transition function δL, which is identically none, so the machine immediately halts.
Fix an arbitrary input string w.
To prove that the automaton halts on every input, we introduce an arbitrary input word w.
intro wThe automaton halts after t = 1 steps because no transition is defined from the initial configuration.
We supply t = 1 as the halting witness and select the left disjunct asserting that the computation terminates with none. At t = 0, the machine is at the left boundary marker in state 0 (configuration (0, 0)). Unfolding the definitions of two_way_dfa_run and two_way_dfa_step, the next step queries the left-boundary transition function δL on state 0; since δL is identically none, the step function produces none, so the machine halts after 1 step.
uses
Or.inl,two_way_dfa_run,two_way_dfa_stepexact ⟨1, Or.inl (by simp [two_way_dfa_run, two_way_dfa_step])⟩
Or.inl- If a proposition a holds, then the disjunction a ∨ b holds.
two_way_dfa_run- The configuration (state and head position) of a two-way DFA on input w after t steps, starting from the start state at position 0, or none if it has halted.
two_way_dfa_step- The single-step transition function of a two-way DFA: given the current state and head position, returns the next state and position, or none if no transition is defined.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem two_way_dfa_halting_empty {σ : Type*} : two_way_dfa_halting (⟨fun _ _ => none, fun _ => none, fun _ => none, 0, 1⟩ : two_way_dfa σ (Fin 2)) := by intro w exact ⟨1, Or.inl (by simp [two_way_dfa_run, two_way_dfa_step])⟩