Reachability-to-result bridge for typed machines
Definitionsgl_reaches_resultcomplexity-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.