SGL move-left prefix reaches adapter
Definitionsgl_move_left_prefix_reachescomplexity-theorysipser-gacs-lautemannturing-machines
This reusable Lean module proves the generic ReachesWithin adapter for the Sipser--Gács--Lautemann move-left prefix construction. If an underlying typed Turing machine reaches a final configuration from the one-cell-left shifted initial configuration within some bound, then the prefixed machine that first performs the raw move-left step reaches the embedded final configuration from the ordinary input within one additional step. It also records that TypedMachine.run is the corresponding iterate of step from the initial configuration.
Definition code
import Definitions.Def_sgl_move_left_prefix
namespace SipserGacsLautemann
theorem TypedMachine.run_eq_iterate_step
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(input : Fin tapes → List Bool)
(steps : Nat) :
machine.run input steps =
(machine.step^[steps])
(machine.initialConfiguration input) := by
induction steps with
| zero => rfl
| succ steps ih =>
rw [TypedMachine.run, ih]
rw [Function.iterate_succ_apply']
theorem moveLeftPrefixTypedMachine_reaches
{tapes : Nat} {State : Type}
(machine : TypedMachine tapes State)
(input : Fin tapes → List Bool)
{final : TypedConfiguration tapes State}
{bound : Nat}
(hreaches :
ReachesWithin machine.step
(moveLeftInitialConfiguration machine input)
final bound) :
ReachesWithin
(moveLeftPrefixTypedMachine machine).step
((moveLeftPrefixTypedMachine machine).initialConfiguration
input)
(MoveLeftPrefixState.embedConfiguration final)
(bound + 1) := by
rcases hreaches with ⟨steps, hle, hsteps⟩
refine ⟨steps + 1, Nat.add_le_add_right hle 1, ?_⟩
rw [← TypedMachine.run_eq_iterate_step]
rw [moveLeftPrefixTypedMachine_run_succ]
rw [hsteps]
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission; standard Turing-machine composition bookkeeping for one-step machine prefixes.