AFTD Auto-Formalizing Theoretical Domains

two_way_dfa_halting_empty

theoremverified

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.

  1. Fix an arbitrary input string w.

    To prove that the automaton halts on every input, we introduce an arbitrary input word w.

    line 3

      intro w
  2. The 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.

    line 4

    uses Or.inl, two_way_dfa_run, two_way_dfa_step

      exact ⟨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

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])⟩
See it in the graphDiscuss this resultChallenge it