Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Reachability-to-result bridge for typed machines

Definition
sgl_reaches_result

by Henry Yuen · Jul 24, 2026 · Mathlib c5ea003 (Lean v4.30.0)

complexity-theoryleansipser-gacs-lautemannturing-machines

This module packages generic reachability lemmas for the mission machine model. It proves that if a typed machine reaches a configuration whose state has a halting Boolean result within a time bound, then the machine has the same result at the full time bound. The bridge is provided both for raw typed-machine iteration and for the relabeled toMachine form used by the mission.

Formalization Note The main hypotheses are expressed using ReachesWithin, and the conclusion rewrites the timed run/result APIs used by acceptsWithin and rejectsWithin style obligations.

Definition code
import Definitions.Def_sgl_move_left_prefix_reaches

namespace SipserGacsLautemann

theorem ReachesWithin.exists_extra
    {α : Type*} {step : α → α}
    {initial final : α} {bound : Nat}
    (hreaches : ReachesWithin step initial final bound) :
    ∃ steps extra,
      steps + extra = bound ∧
        (step^[steps]) initial = final := by
  rcases hreaches with ⟨steps, hsteps, hrun⟩
  obtain ⟨extra, hbound⟩ := Nat.exists_eq_add_of_le hsteps
  exact ⟨steps, extra, hbound.symm, hrun⟩

theorem TypedMachine.iterate_eq_self_of_result_some
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (configuration : TypedConfiguration tapes State)
    {result : Bool}
    (hresult :
      machine.result configuration.state = some result)
    (extra : Nat) :
    (machine.step^[extra]) configuration = configuration := by
  induction extra with
  | zero => rfl
  | succ extra ih =>
      rw [Function.iterate_succ_apply]
      rw [machine.step_eq_self_of_result_some
        configuration hresult]
      rw [ih]

theorem TypedMachine.run_eq_of_reaches
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool)
    {final : TypedConfiguration tapes State}
    {bound : Nat}
    (hreaches :
      ReachesWithin machine.step
        (machine.initialConfiguration input) final bound)
    (hresult :
      ∃ result, machine.result final.state = some result) :
    machine.run input bound = final := by
  rcases hreaches.exists_extra with
    ⟨steps, extra, hbound, hrun⟩
  rcases hresult with ⟨result, hresult⟩
  rw [← hbound]
  rw [TypedMachine.run_eq_iterate_step]
  rw [Nat.add_comm, Function.iterate_add_apply]
  rw [hrun]
  clear hbound
  exact
    machine.iterate_eq_self_of_result_some
      final hresult extra

theorem TypedMachine.result_iterate_eq_of_reaches_result
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    {initial final : TypedConfiguration tapes State}
    {bound : Nat} {result : Bool}
    (hreaches :
      ReachesWithin machine.step initial final bound)
    (hresult :
      machine.result final.state = some result) :
    machine.result ((machine.step^[bound]) initial).state =
      some result := by
  rcases hreaches.exists_extra with
    ⟨steps, extra, hbound, hrun⟩
  rw [← hbound]
  rw [Nat.add_comm, Function.iterate_add_apply]
  rw [hrun]
  clear hbound
  rw [machine.iterate_eq_self_of_result_some
    final hresult extra]
  exact hresult

theorem TypedMachine.result_run_eq_of_reaches_result
    {tapes : Nat} {State : Type}
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool)
    {final : TypedConfiguration tapes State}
    {bound : Nat} {result : Bool}
    (hreaches :
      ReachesWithin machine.step
        (machine.initialConfiguration input) final bound)
    (hresult :
      machine.result final.state = some result) :
    machine.result (machine.run input bound).state =
      some result := by
  rw [machine.run_eq_of_reaches input
    hreaches ⟨result, hresult⟩]
  exact hresult

theorem TypedMachine.toMachine_result_run_eq_of_reaches_result
    {tapes : Nat} {State : Type} [Fintype State]
    (machine : TypedMachine tapes State)
    (input : Fin tapes → List Bool)
    {final : TypedConfiguration tapes State}
    {bound : Nat} {result : Bool}
    (hreaches :
      ReachesWithin machine.step
        (machine.initialConfiguration input) final bound)
    (hresult :
      machine.result final.state = some result) :
    machine.toMachine.result
        (machine.toMachine.run input bound).state =
      some result := by
  rw [TypedMachine.toMachine_run_encode]
  simpa [TypedConfiguration.encode, TypedMachine.toMachine]
    using
      machine.result_run_eq_of_reaches_result
        input hreaches hresult

end SipserGacsLautemann
Source
Prove2me Sipser--Gacs--Lautemann mission finite-state simulator infrastructure.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me