SGL zigzag global correctness
Definitionsgl_zigzag_globalcomplexity-theorysipser-gacs-lautemannturing-machines
This auxiliary module lifts the local zigzag simulator correctness lemmas to complete runs of a two-tape base machine. It proves that the archive-preserving simulator reaches the configuration corresponding to a bounded base-machine run with polynomial overhead.
Definition code
import Definitions.Def_sgl_zigzag_correctness
import Mathlib.Tactic.FinCases
namespace SipserGacsLautemann
theorem zigzagScan_pad
(initial final : ZigzagScanLocal × Tape)
(steps bound : Nat)
(hle : steps ≤ bound)
(hrun :
(zigzagScanConfigurationStep^[steps]) initial = final)
(hfinal : final.1.isDone = true) :
(zigzagScanConfigurationStep^[bound]) initial = final := by
obtain ⟨extra, hbound⟩ :=
Nat.exists_eq_add_of_le hle
rw [hbound, Nat.add_comm,
Function.iterate_add_apply, hrun]
apply Function.iterate_fixed
rcases final with ⟨state, tape⟩
cases state <;> simp_all [zigzagScanConfigurationStep,
ZigzagScanLocal.isDone, zigzagScanLocalStep,
applyPhysicalAction, Tape.write, Tape.move]
abbrev ZigzagScanProduct :=
(Fin 2 → ZigzagScanLocal) × (Fin 2 → Tape)
def zigzagScanProductStep
(configuration : ZigzagScanProduct) :
ZigzagScanProduct :=
(fun i =>
(zigzagScanConfigurationStep
(configuration.1 i, configuration.2 i)).1,
fun i =>
(zigzagScanConfigurationStep
(configuration.1 i, configuration.2 i)).2)
theorem zigzagScanProductStep_iterate_apply
(configuration : ZigzagScanProduct)
(steps : Nat) (i : Fin 2) :
(((zigzagScanProductStep^[steps])
configuration).1 i,
((zigzagScanProductStep^[steps])
configuration).2 i) =
(zigzagScanConfigurationStep^[steps])
(configuration.1 i, configuration.2 i) := by
induction steps with
| zero => rfl
| succ steps ih =>
rw [Function.iterate_succ_apply']
rw [Function.iterate_succ_apply']
change
(zigzagScanConfigurationStep
(((zigzagScanProductStep^[steps])
configuration).1 i,
((zigzagScanProductStep^[steps])
configuration).2 i)) =
zigzagScanConfigurationStep
((zigzagScanConfigurationStep^[steps])
(configuration.1 i, configuration.2 i))
rw [ih]
theorem zigzagScanProductStep_iterate_eq
(configuration final : ZigzagScanProduct)
(steps : Nat)
(hrun :
∀ i : Fin 2,
(zigzagScanConfigurationStep^[steps])
(configuration.1 i, configuration.2 i) =
(final.1 i, final.2 i)) :
(zigzagScanProductStep^[steps]) configuration =
final := by
apply Prod.ext
· funext i
have hcomponent :=
zigzagScanProductStep_iterate_apply
configuration steps i
rw [hrun i] at hcomponent
exact congrArg Prod.fst hcomponent
· funext i
have hcomponent :=
zigzagScanProductStep_iterate_apply
configuration steps i
rw [hrun i] at hcomponent
exact congrArg Prod.snd hcomponent
def maxZigzagIndex (positions : Fin 2 → Int) : Nat :=
max (zigzagIndex (positions 0))
(zigzagIndex (positions 1))
theorem zigzagIndex_le_maxZigzagIndex
(positions : Fin 2 → Int) (i : Fin 2) :
zigzagIndex (positions i) ≤
maxZigzagIndex positions := by
fin_cases i
· exact Nat.le_max_left _ _
· exact Nat.le_max_right _ _
theorem zigzagScanProduct_physicalTapes
(archives : Fin 2 → List TapeSymbol)
(tapes : Fin 2 → Tape)
(positions : Fin 2 → Int)
(recordCount : Nat)
(hroom :
∀ i : Fin 2,
zigzagIndex (positions i) < recordCount) :
(zigzagScanProductStep^[
6 * maxZigzagIndex positions + 6])
(startScanLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount).move .right) =
(fun i =>
.done (tapes i).head
(ZigzagIndexClass.atIndex
(zigzagIndex (positions i))),
fun i =>
zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount) := by
apply zigzagScanProductStep_iterate_eq
intro i
obtain ⟨extra, hcount⟩ :=
Nat.exists_eq_add_of_le
(show zigzagIndex (positions i) + 1 ≤
recordCount by
exact Nat.succ_le_iff.mpr (hroom i))
have hscan :=
zigzagScan_physicalTape
(archives i) (tapes i) (positions i) extra
rw [← hcount] at hscan
apply zigzagScan_pad _ _
(6 * zigzagIndex (positions i) + 6)
(6 * maxZigzagIndex positions + 6)
· exact Nat.add_le_add_right
(Nat.mul_le_mul_left 6
(zigzagIndex_le_maxZigzagIndex
positions i)) 6
· simpa [startScanLocals] using hscan
· rfl
abbrev ZigzagUpdateProduct :=
(Fin 2 → ZigzagUpdateLocal) × (Fin 2 → Tape)
def zigzagUpdateProductStep
(writes : Fin 2 → TapeSymbol)
(moves : Fin 2 → HeadMove)
(configuration : ZigzagUpdateProduct) :
ZigzagUpdateProduct :=
(fun i =>
(zigzagUpdateConfigurationStep
(writes i) (moves i)
(configuration.1 i, configuration.2 i)).1,
fun i =>
(zigzagUpdateConfigurationStep
(writes i) (moves i)
(configuration.1 i, configuration.2 i)).2)
theorem zigzagUpdateProductStep_iterate_apply
(writes : Fin 2 → TapeSymbol)
(moves : Fin 2 → HeadMove)
(configuration : ZigzagUpdateProduct)
(steps : Nat) (i : Fin 2) :
((((zigzagUpdateProductStep writes moves)^[steps])
configuration).1 i,
(((zigzagUpdateProductStep writes moves)^[steps])
configuration).2 i) =
(zigzagUpdateConfigurationStep
(writes i) (moves i))^[steps]
(configuration.1 i, configuration.2 i) := by
induction steps with
| zero => rfl
| succ steps ih =>
rw [Function.iterate_succ_apply']
rw [Function.iterate_succ_apply']
change
zigzagUpdateConfigurationStep
(writes i) (moves i)
((((zigzagUpdateProductStep writes moves)^[
steps]) configuration).1 i,
(((zigzagUpdateProductStep writes moves)^[
steps]) configuration).2 i) =
zigzagUpdateConfigurationStep
(writes i) (moves i)
(((zigzagUpdateConfigurationStep
(writes i) (moves i))^[steps])
(configuration.1 i, configuration.2 i))
rw [ih]
theorem zigzagUpdateProductStep_iterate_eq
(writes : Fin 2 → TapeSymbol)
(moves : Fin 2 → HeadMove)
(configuration final : ZigzagUpdateProduct)
(steps : Nat)
(hrun :
∀ i : Fin 2,
((zigzagUpdateConfigurationStep
(writes i) (moves i))^[steps])
(configuration.1 i, configuration.2 i) =
(final.1 i, final.2 i)) :
((zigzagUpdateProductStep writes moves)^[steps])
configuration =
final := by
apply Prod.ext
· funext i
have hcomponent :=
zigzagUpdateProductStep_iterate_apply
writes moves configuration steps i
rw [hrun i] at hcomponent
exact congrArg Prod.fst hcomponent
· funext i
have hcomponent :=
zigzagUpdateProductStep_iterate_apply
writes moves configuration steps i
rw [hrun i] at hcomponent
exact congrArg Prod.snd hcomponent
theorem zigzagUpdateProduct_physicalTapes
(archives : Fin 2 → List TapeSymbol)
(tapes : Fin 2 → Tape)
(positions : Fin 2 → Int)
(recordCount : Nat)
(writes : Fin 2 → TapeSymbol)
(moves : Fin 2 → HeadMove)
(hroom :
∀ i : Fin 2,
zigzagIndex (positions i) + 2 < recordCount) :
((zigzagUpdateProductStep writes moves)^[
6 * maxZigzagIndex positions + 23])
(startUpdateLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount).move .right) =
(fun _ => .done,
fun i =>
zigzagPhysicalTape
(archives i)
(((tapes i).write (writes i)).move
(moves i))
((moves i).updatePosition (positions i))
recordCount) := by
apply zigzagUpdateProductStep_iterate_eq
intro i
have hupdate :=
zigzagUpdate_physicalTape
(archives i) (tapes i) (positions i)
recordCount (writes i) (moves i) (hroom i)
apply zigzagUpdate_pad
(writes i) (moves i) _ _
(6 * zigzagIndex (positions i) + 23)
(6 * maxZigzagIndex positions + 23)
· exact Nat.add_le_add_right
(Nat.mul_le_mul_left 6
(zigzagIndex_le_maxZigzagIndex
positions i)) 23
· simpa [startUpdateLocals] using hupdate
· rfl
theorem iterate_embed_until_done
{α β : Type*}
(localStep : α → α) (globalStep : β → β)
(embed : α → β) (done : α → Bool)
(initial : α) (bound : Nat)
(hstep :
∀ configuration,
done configuration = false →
globalStep (embed configuration) =
embed (localStep configuration))
(hfinal :
done ((localStep^[bound]) initial) = true) :
∃ steps ≤ bound,
(globalStep^[steps]) (embed initial) =
embed ((localStep^[steps]) initial) ∧
done ((localStep^[steps]) initial) = true := by
classical
let terminal : Nat → Prop :=
fun steps =>
done ((localStep^[steps]) initial) = true
have hexists : ∃ steps, terminal steps :=
⟨bound, hfinal⟩
let first := Nat.find hexists
have hfirst : terminal first :=
Nat.find_spec hexists
have hfirstLe : first ≤ bound :=
Nat.find_min' hexists hfinal
have hbefore :
∀ steps < first,
done ((localStep^[steps]) initial) = false := by
intro steps hlt
apply Bool.eq_false_of_not_eq_true
intro hterminal
exact (Nat.find_min hexists hlt) hterminal
have hembed :
∀ steps ≤ first,
(globalStep^[steps]) (embed initial) =
embed ((localStep^[steps]) initial) := by
intro steps hle
induction steps with
| zero => rfl
| succ steps ih =>
rw [Function.iterate_succ_apply',
Function.iterate_succ_apply']
rw [ih (Nat.le_trans (Nat.le_succ steps) hle)]
apply hstep
exact hbefore steps (Nat.lt_of_succ_le hle)
exact
⟨first, hfirstLe, hembed first (Nat.le_refl _),
hfirst⟩
def embedZigzagScanProduct
{baseStates : Nat} (baseState : Fin baseStates)
(configuration : ZigzagScanProduct) :
TypedConfiguration 2
(ZigzagSimulationState baseStates) :=
⟨.scanning baseState configuration.1,
configuration.2⟩
def embedZigzagUpdateProduct
{baseStates : Nat} (nextState : Fin baseStates)
(writes : Fin 2 → TapeSymbol)
(moves : Fin 2 → HeadMove)
(configuration : ZigzagUpdateProduct) :
TypedConfiguration 2
(ZigzagSimulationState baseStates) :=
⟨.updating nextState writes moves configuration.1,
configuration.2⟩
theorem zigzagSimulation_step_scan_not_done
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(baseState : Fin baseStates)
(configuration : ZigzagScanProduct)
(hnotDone :
allScanDone configuration.1 = false) :
(zigzagSimulationTypedMachine baseMachine).step
(embedZigzagScanProduct baseState configuration) =
embedZigzagScanProduct baseState
(zigzagScanProductStep configuration) := by
simp only [TypedMachine.step,
zigzagSimulationTypedMachine,
embedZigzagScanProduct]
rw [dif_neg (by simpa using hnotDone)]
rfl
theorem zigzagSimulation_step_update_not_done
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(nextState : Fin baseStates)
(writes : Fin 2 → TapeSymbol)
(moves : Fin 2 → HeadMove)
(configuration : ZigzagUpdateProduct)
(hnotDone :
allUpdateDone configuration.1 = false) :
(zigzagSimulationTypedMachine baseMachine).step
(embedZigzagUpdateProduct nextState
writes moves configuration) =
embedZigzagUpdateProduct nextState writes moves
(zigzagUpdateProductStep
writes moves configuration) := by
simp only [TypedMachine.step,
zigzagSimulationTypedMachine,
embedZigzagUpdateProduct]
rw [dif_neg (by simpa using hnotDone)]
rfl
theorem zigzagSimulation_scan_reaches_done
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(baseState : Fin baseStates)
(archives : Fin 2 → List TapeSymbol)
(tapes : Fin 2 → Tape)
(positions : Fin 2 → Int)
(recordCount : Nat)
(hroom :
∀ i : Fin 2,
zigzagIndex (positions i) < recordCount) :
∃ steps ≤ 6 * maxZigzagIndex positions + 6,
(((zigzagSimulationTypedMachine baseMachine).step)^[
steps])
(embedZigzagScanProduct baseState
(startScanLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount).move .right)) =
embedZigzagScanProduct baseState
(((zigzagScanProductStep^[steps])
(startScanLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount).move .right))) ∧
allScanDone
(((zigzagScanProductStep^[steps])
(startScanLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount).move .right))).1 =
true := by
apply iterate_embed_until_done
zigzagScanProductStep
(zigzagSimulationTypedMachine baseMachine).step
(embedZigzagScanProduct baseState)
(fun configuration =>
allScanDone configuration.1)
· intro configuration hnotDone
exact zigzagSimulation_step_scan_not_done
baseMachine baseState configuration hnotDone
· rw [zigzagScanProduct_physicalTapes
archives tapes positions recordCount hroom]
rfl
theorem zigzagSimulation_update_reaches_done
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(nextState : Fin baseStates)
(archives : Fin 2 → List TapeSymbol)
(tapes : Fin 2 → Tape)
(positions : Fin 2 → Int)
(recordCount : Nat)
(writes : Fin 2 → TapeSymbol)
(moves : Fin 2 → HeadMove)
(hroom :
∀ i : Fin 2,
zigzagIndex (positions i) + 2 < recordCount) :
∃ steps ≤ 6 * maxZigzagIndex positions + 23,
(((zigzagSimulationTypedMachine baseMachine).step)^[
steps])
(embedZigzagUpdateProduct nextState writes moves
(startUpdateLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount).move .right)) =
embedZigzagUpdateProduct nextState writes moves
(((zigzagUpdateProductStep writes moves)^[
steps])
(startUpdateLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount).move .right)) ∧
allUpdateDone
((((zigzagUpdateProductStep writes moves)^[
steps])
(startUpdateLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount).move .right)).1) =
true := by
apply iterate_embed_until_done
(zigzagUpdateProductStep writes moves)
(zigzagSimulationTypedMachine baseMachine).step
(embedZigzagUpdateProduct nextState writes moves)
(fun configuration =>
allUpdateDone configuration.1)
· intro configuration hnotDone
exact zigzagSimulation_step_update_not_done
baseMachine nextState writes moves
configuration hnotDone
· rw [zigzagUpdateProduct_physicalTapes
archives tapes positions recordCount
writes moves hroom]
rfl
theorem zigzagScanConfigurationStep_fixed_of_done
(configuration : ZigzagScanLocal × Tape)
(hdone : configuration.1.isDone = true) :
zigzagScanConfigurationStep configuration =
configuration := by
rcases configuration with ⟨state, tape⟩
cases state <;>
simp_all [ZigzagScanLocal.isDone,
zigzagScanConfigurationStep, zigzagScanLocalStep,
applyPhysicalAction, Tape.write, Tape.move]
theorem zigzagUpdateConfigurationStep_fixed_of_done
(write : TapeSymbol) (move : HeadMove)
(configuration : ZigzagUpdateLocal × Tape)
(hdone : configuration.1.isDone = true) :
zigzagUpdateConfigurationStep write move configuration =
configuration := by
rcases configuration with ⟨state, tape⟩
cases state <;>
simp_all [ZigzagUpdateLocal.isDone,
zigzagUpdateConfigurationStep, zigzagUpdateLocalStep,
applyPhysicalAction, Tape.write, Tape.move]
theorem zigzagScanProductStep_fixed_of_done
(configuration : ZigzagScanProduct)
(hdone : allScanDone configuration.1 = true) :
zigzagScanProductStep configuration =
configuration := by
have hcomponents :
∀ i : Fin 2,
(configuration.1 i).isDone = true := by
rw [allScanDone, Bool.and_eq_true] at hdone
intro i
fin_cases i
· exact hdone.1
· exact hdone.2
apply Prod.ext
· funext i
have hlocal :=
zigzagScanConfigurationStep_fixed_of_done
(configuration.1 i, configuration.2 i)
(hcomponents i)
exact congrArg Prod.fst hlocal
· funext i
have hlocal :=
zigzagScanConfigurationStep_fixed_of_done
(configuration.1 i, configuration.2 i)
(hcomponents i)
exact congrArg Prod.snd hlocal
theorem zigzagUpdateProductStep_fixed_of_done
(writes : Fin 2 → TapeSymbol)
(moves : Fin 2 → HeadMove)
(configuration : ZigzagUpdateProduct)
(hdone : allUpdateDone configuration.1 = true) :
zigzagUpdateProductStep writes moves configuration =
configuration := by
have hcomponents :
∀ i : Fin 2,
(configuration.1 i).isDone = true := by
rw [allUpdateDone, Bool.and_eq_true] at hdone
intro i
fin_cases i
· exact hdone.1
· exact hdone.2
apply Prod.ext
· funext i
have hlocal :=
zigzagUpdateConfigurationStep_fixed_of_done
(writes i) (moves i)
(configuration.1 i, configuration.2 i)
(hcomponents i)
exact congrArg Prod.fst hlocal
· funext i
have hlocal :=
zigzagUpdateConfigurationStep_fixed_of_done
(writes i) (moves i)
(configuration.1 i, configuration.2 i)
(hcomponents i)
exact congrArg Prod.snd hlocal
theorem iterate_eq_final_of_fixed
{α : Type*} (step : α → α)
(initial current final : α)
(steps bound : Nat)
(hle : steps ≤ bound)
(hcurrent :
(step^[steps]) initial = current)
(hfixed : step current = current)
(hfinal :
(step^[bound]) initial = final) :
current = final := by
obtain ⟨extra, hbound⟩ :=
Nat.exists_eq_add_of_le hle
rw [hbound, Nat.add_comm,
Function.iterate_add_apply, hcurrent] at hfinal
have hiterate :
(step^[extra]) current = current :=
Function.iterate_fixed hfixed extra
rw [hiterate] at hfinal
exact hfinal
theorem zigzagSimulation_scan_reaches_final
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(baseState : Fin baseStates)
(archives : Fin 2 → List TapeSymbol)
(tapes : Fin 2 → Tape)
(positions : Fin 2 → Int)
(recordCount : Nat)
(hroom :
∀ i : Fin 2,
zigzagIndex (positions i) < recordCount) :
∃ steps ≤ 6 * maxZigzagIndex positions + 6,
(((zigzagSimulationTypedMachine baseMachine).step)^[
steps])
(embedZigzagScanProduct baseState
(startScanLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount).move .right)) =
embedZigzagScanProduct baseState
(fun i =>
.done (tapes i).head
(ZigzagIndexClass.atIndex
(zigzagIndex (positions i))),
fun i =>
zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount) := by
obtain ⟨steps, hsteps, hglobal, hdone⟩ :=
zigzagSimulation_scan_reaches_done
baseMachine baseState archives tapes positions
recordCount hroom
let initial : ZigzagScanProduct :=
(startScanLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount).move .right)
let current :=
(zigzagScanProductStep^[steps]) initial
let final : ZigzagScanProduct :=
(fun i =>
.done (tapes i).head
(ZigzagIndexClass.atIndex
(zigzagIndex (positions i))),
fun i =>
zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount)
have hcurrent :
(zigzagScanProductStep^[steps]) initial =
current := rfl
have hfixed :
zigzagScanProductStep current = current :=
zigzagScanProductStep_fixed_of_done
current hdone
have hfinal :
(zigzagScanProductStep^[
6 * maxZigzagIndex positions + 6]) initial =
final := by
exact zigzagScanProduct_physicalTapes
archives tapes positions recordCount hroom
have hcanonical :
current = final :=
iterate_eq_final_of_fixed
zigzagScanProductStep initial current final
steps (6 * maxZigzagIndex positions + 6)
hsteps hcurrent hfixed hfinal
refine ⟨steps, hsteps, ?_⟩
simpa [initial, current, final, hcanonical] using hglobal
theorem zigzagSimulation_update_reaches_final
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(nextState : Fin baseStates)
(archives : Fin 2 → List TapeSymbol)
(tapes : Fin 2 → Tape)
(positions : Fin 2 → Int)
(recordCount : Nat)
(writes : Fin 2 → TapeSymbol)
(moves : Fin 2 → HeadMove)
(hroom :
∀ i : Fin 2,
zigzagIndex (positions i) + 2 < recordCount) :
∃ steps ≤ 6 * maxZigzagIndex positions + 23,
(((zigzagSimulationTypedMachine baseMachine).step)^[
steps])
(embedZigzagUpdateProduct nextState writes moves
(startUpdateLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount).move .right)) =
embedZigzagUpdateProduct nextState writes moves
(fun _ => .done,
fun i =>
zigzagPhysicalTape
(archives i)
(((tapes i).write (writes i)).move
(moves i))
((moves i).updatePosition (positions i))
recordCount) := by
obtain ⟨steps, hsteps, hglobal, hdone⟩ :=
zigzagSimulation_update_reaches_done
baseMachine nextState archives tapes positions
recordCount writes moves hroom
let initial : ZigzagUpdateProduct :=
(startUpdateLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount).move .right)
let current :=
((zigzagUpdateProductStep writes moves)^[steps])
initial
let final : ZigzagUpdateProduct :=
(fun _ => .done,
fun i =>
zigzagPhysicalTape
(archives i)
(((tapes i).write (writes i)).move
(moves i))
((moves i).updatePosition (positions i))
recordCount)
have hcurrent :
((zigzagUpdateProductStep writes moves)^[steps])
initial =
current := rfl
have hfixed :
zigzagUpdateProductStep writes moves current =
current :=
zigzagUpdateProductStep_fixed_of_done
writes moves current hdone
have hfinal :
((zigzagUpdateProductStep writes moves)^[
6 * maxZigzagIndex positions + 23]) initial =
final := by
exact zigzagUpdateProduct_physicalTapes
archives tapes positions recordCount
writes moves hroom
have hcanonical :
current = final :=
iterate_eq_final_of_fixed
(zigzagUpdateProductStep writes moves)
initial current final steps
(6 * maxZigzagIndex positions + 23)
hsteps hcurrent hfixed hfinal
refine ⟨steps, hsteps, ?_⟩
simpa [initial, current, final, hcanonical] using hglobal
def zigzagReadyConfiguration
{baseStates : Nat}
(configuration : Configuration 2 baseStates)
(archives : Fin 2 → List TapeSymbol)
(positions : Fin 2 → Int)
(recordCount : Nat) :
TypedConfiguration 2
(ZigzagSimulationState baseStates) :=
⟨.ready configuration.state,
fun i =>
zigzagPhysicalTape
(archives i) (configuration.tape i)
(positions i) recordCount⟩
theorem Tape.write_head (tape : Tape) :
tape.write tape.head = tape := by
cases tape
rfl
theorem zigzagSimulation_ready_step
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(configuration : Configuration 2 baseStates)
(archives : Fin 2 → List TapeSymbol)
(positions : Fin 2 → Int)
(recordCount : Nat)
(hresult :
baseMachine.result configuration.state = none) :
(zigzagSimulationTypedMachine baseMachine).step
(zigzagReadyConfiguration configuration archives
positions recordCount) =
embedZigzagScanProduct configuration.state
(startScanLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (configuration.tape i)
(positions i) recordCount).move .right) := by
unfold TypedMachine.step zigzagReadyConfiguration
embedZigzagScanProduct
rw [show
(zigzagSimulationTypedMachine baseMachine).result
(.ready configuration.state) =
none by
exact hresult]
simp only [zigzagSimulationTypedMachine]
congr 1
theorem zigzagSimulation_scan_done_step
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(baseState : Fin baseStates)
(archives : Fin 2 → List TapeSymbol)
(tapes : Fin 2 → Tape)
(positions : Fin 2 → Int)
(recordCount : Nat) :
let action :=
baseMachine.transition baseState
(fun i => (tapes i).head)
(zigzagSimulationTypedMachine baseMachine).step
(embedZigzagScanProduct baseState
(fun i =>
.done (tapes i).head
(ZigzagIndexClass.atIndex
(zigzagIndex (positions i))),
fun i =>
zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount)) =
embedZigzagUpdateProduct action.1
(fun i => (action.2 i).1)
(fun i => (action.2 i).2)
(startUpdateLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (tapes i) (positions i)
recordCount).move .right) := by
dsimp only
unfold TypedMachine.step embedZigzagScanProduct
embedZigzagUpdateProduct
simp only [zigzagSimulationTypedMachine,
allScanDone, ZigzagScanLocal.isDone,
ZigzagScanLocal.symbol, Bool.true_and,
↓reduceDIte, Tape.write_head]
theorem zigzagSimulation_update_done_step
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(nextState : Fin baseStates)
(archives : Fin 2 → List TapeSymbol)
(tapes : Fin 2 → Tape)
(positions : Fin 2 → Int)
(recordCount : Nat)
(writes : Fin 2 → TapeSymbol)
(moves : Fin 2 → HeadMove) :
(zigzagSimulationTypedMachine baseMachine).step
(embedZigzagUpdateProduct nextState writes moves
(fun _ => .done,
fun i =>
zigzagPhysicalTape
(archives i)
(((tapes i).write (writes i)).move
(moves i))
((moves i).updatePosition (positions i))
recordCount)) =
zigzagReadyConfiguration
⟨nextState,
fun i =>
((tapes i).write (writes i)).move
(moves i)⟩
archives
(fun i =>
(moves i).updatePosition (positions i))
recordCount := by
unfold TypedMachine.step embedZigzagUpdateProduct
zigzagReadyConfiguration
simp only [zigzagSimulationTypedMachine,
allUpdateDone, ZigzagUpdateLocal.isDone,
Bool.true_and, ↓reduceDIte, Tape.write_head,
Tape.move]
def ReachesWithin {α : Type*}
(step : α → α) (initial final : α)
(bound : Nat) : Prop :=
∃ steps ≤ bound,
(step^[steps]) initial = final
theorem ReachesWithin.refl
{α : Type*} (step : α → α) (initial : α)
(bound : Nat) :
ReachesWithin step initial initial bound :=
⟨0, Nat.zero_le _, rfl⟩
theorem ReachesWithin.mono
{α : Type*} {step : α → α}
{initial final : α} {firstBound secondBound : Nat}
(hreaches :
ReachesWithin step initial final firstBound)
(hle : firstBound ≤ secondBound) :
ReachesWithin step initial final secondBound := by
rcases hreaches with ⟨steps, hsteps, hrun⟩
exact ⟨steps, Nat.le_trans hsteps hle, hrun⟩
theorem ReachesWithin.trans
{α : Type*} {step : α → α}
{first second third : α}
{firstBound secondBound : Nat}
(hfirst :
ReachesWithin step first second firstBound)
(hsecond :
ReachesWithin step second third secondBound) :
ReachesWithin step first third
(firstBound + secondBound) := by
rcases hfirst with
⟨firstSteps, hfirstSteps, hfirstRun⟩
rcases hsecond with
⟨secondSteps, hsecondSteps, hsecondRun⟩
refine
⟨firstSteps + secondSteps,
Nat.add_le_add hfirstSteps hsecondSteps, ?_⟩
rw [Nat.add_comm, Function.iterate_add_apply,
hfirstRun, hsecondRun]
theorem ReachesWithin.one
{α : Type*} (step : α → α) (initial : α) :
ReachesWithin step initial (step initial) 1 :=
⟨1, Nat.le_refl _, rfl⟩
theorem zigzagSimulation_reaches_base_step
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(configuration : Configuration 2 baseStates)
(archives : Fin 2 → List TapeSymbol)
(positions : Fin 2 → Int)
(recordCount : Nat)
(hresult :
baseMachine.result configuration.state = none)
(hroom :
∀ i : Fin 2,
zigzagIndex (positions i) + 2 < recordCount) :
let action :=
baseMachine.transition configuration.state
(fun i => (configuration.tape i).head)
ReachesWithin
(zigzagSimulationTypedMachine baseMachine).step
(zigzagReadyConfiguration configuration archives
positions recordCount)
(zigzagReadyConfiguration
(baseMachine.step configuration) archives
(fun i =>
(action.2 i).2.updatePosition (positions i))
recordCount)
(12 * maxZigzagIndex positions + 32) := by
dsimp only
let action :=
baseMachine.transition configuration.state
(fun i => (configuration.tape i).head)
let scanInitial : ZigzagScanProduct :=
(startScanLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (configuration.tape i)
(positions i) recordCount).move .right)
let scanFinal : ZigzagScanProduct :=
(fun i =>
.done (configuration.tape i).head
(ZigzagIndexClass.atIndex
(zigzagIndex (positions i))),
fun i =>
zigzagPhysicalTape
(archives i) (configuration.tape i)
(positions i) recordCount)
let updateInitial : ZigzagUpdateProduct :=
(startUpdateLocals,
fun i =>
(zigzagPhysicalTape
(archives i) (configuration.tape i)
(positions i) recordCount).move .right)
let updateFinal : ZigzagUpdateProduct :=
(fun _ => .done,
fun i =>
zigzagPhysicalTape
(archives i)
(((configuration.tape i).write
(action.2 i).1).move (action.2 i).2)
((action.2 i).2.updatePosition (positions i))
recordCount)
let globalStep :=
(zigzagSimulationTypedMachine baseMachine).step
have hready :
ReachesWithin globalStep
(zigzagReadyConfiguration configuration archives
positions recordCount)
(embedZigzagScanProduct configuration.state
scanInitial)
1 := by
refine ⟨1, Nat.le_refl _, ?_⟩
simpa [globalStep, scanInitial] using
zigzagSimulation_ready_step
baseMachine configuration archives positions
recordCount hresult
have hscanRoom :
∀ i : Fin 2,
zigzagIndex (positions i) < recordCount := by
intro i
have := hroom i
omega
have hscan :
ReachesWithin globalStep
(embedZigzagScanProduct configuration.state
scanInitial)
(embedZigzagScanProduct configuration.state
scanFinal)
(6 * maxZigzagIndex positions + 6) := by
obtain ⟨steps, hsteps, hrun⟩ :=
zigzagSimulation_scan_reaches_final
baseMachine configuration.state archives
configuration.tape positions recordCount
hscanRoom
exact
⟨steps, hsteps,
by simpa [globalStep, scanInitial, scanFinal]
using hrun⟩
have hscanDone :
ReachesWithin globalStep
(embedZigzagScanProduct configuration.state
scanFinal)
(embedZigzagUpdateProduct action.1
(fun i => (action.2 i).1)
(fun i => (action.2 i).2)
updateInitial)
1 := by
refine ⟨1, Nat.le_refl _, ?_⟩
simpa [globalStep, scanFinal, updateInitial,
action] using
zigzagSimulation_scan_done_step
baseMachine configuration.state archives
configuration.tape positions recordCount
have hupdate :
ReachesWithin globalStep
(embedZigzagUpdateProduct action.1
(fun i => (action.2 i).1)
(fun i => (action.2 i).2)
updateInitial)
(embedZigzagUpdateProduct action.1
(fun i => (action.2 i).1)
(fun i => (action.2 i).2)
updateFinal)
(6 * maxZigzagIndex positions + 23) := by
obtain ⟨steps, hsteps, hrun⟩ :=
zigzagSimulation_update_reaches_final
baseMachine action.1 archives configuration.tape
positions recordCount
(fun i => (action.2 i).1)
(fun i => (action.2 i).2)
hroom
exact
⟨steps, hsteps,
by simpa [globalStep, updateInitial, updateFinal]
using hrun⟩
let steppedConfiguration : Configuration 2 baseStates :=
⟨action.1,
fun i =>
((configuration.tape i).write
(action.2 i).1).move (action.2 i).2⟩
have hbaseStep :
baseMachine.step configuration =
steppedConfiguration := by
simp [Machine.step, hresult, steppedConfiguration,
action]
have hupdateDone :
ReachesWithin globalStep
(embedZigzagUpdateProduct action.1
(fun i => (action.2 i).1)
(fun i => (action.2 i).2)
updateFinal)
(zigzagReadyConfiguration steppedConfiguration
archives
(fun i =>
(action.2 i).2.updatePosition (positions i))
recordCount)
1 := by
refine ⟨1, Nat.le_refl _, ?_⟩
simpa [globalStep, updateFinal,
steppedConfiguration] using
zigzagSimulation_update_done_step
baseMachine action.1 archives
configuration.tape positions recordCount
(fun i => (action.2 i).1)
(fun i => (action.2 i).2)
have htotal :=
((((hready.trans hscan).trans hscanDone).trans
hupdate).trans hupdateDone)
rw [hbaseStep]
apply htotal.mono
simp only [maxZigzagIndex]
omega
theorem zigzagIndex_updatePosition_le_add_two
(position : Int) (move : HeadMove) :
zigzagIndex (move.updatePosition position) ≤
zigzagIndex position + 2 := by
have hposition :=
zigzagIndex_updatePosition position move
simp only at hposition
cases hrelocation :
zigzagRelocation move
(ZigzagIndexClass.atIndex
(zigzagIndex position)) with
| none =>
rw [hrelocation] at hposition
omega
| some relocation =>
rcases relocation with ⟨direction, distance⟩
rw [hrelocation] at hposition
cases direction with
| inward =>
simp at hposition
omega
| outward =>
simp at hposition
have hdistance : distance.val / 3 ≤ 2 := by
omega
omega
def zigzagRunPositions
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(input : Fin 2 → List Bool) :
Nat → (Fin 2 → Int)
| 0 => fun _ => 0
| steps + 1 =>
let configuration := baseMachine.run input steps
match baseMachine.result configuration.state with
| some _ => zigzagRunPositions baseMachine input steps
| none =>
let action :=
baseMachine.transition configuration.state
(fun i => (configuration.tape i).head)
fun i =>
(action.2 i).2.updatePosition
(zigzagRunPositions baseMachine input steps i)
theorem zigzagRunPositions_index_bound
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(input : Fin 2 → List Bool)
(steps : Nat) (i : Fin 2) :
zigzagIndex
(zigzagRunPositions baseMachine input steps i) ≤
2 * steps := by
induction steps with
| zero =>
simp [zigzagRunPositions, zigzagIndex]
| succ steps ih =>
cases hresult :
baseMachine.result
(baseMachine.run input steps).state with
| some result =>
simp [zigzagRunPositions, hresult]
exact Nat.le_trans ih (by omega)
| none =>
simp only [zigzagRunPositions, hresult]
exact
Nat.le_trans
(zigzagIndex_updatePosition_le_add_two
(zigzagRunPositions baseMachine input steps i)
((baseMachine.transition
(baseMachine.run input steps).state
(fun i =>
((baseMachine.run input steps).tape i).head)
).2 i).2)
(by omega)
theorem maxZigzagIndex_runPositions_bound
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(input : Fin 2 → List Bool)
(steps : Nat) :
maxZigzagIndex
(zigzagRunPositions baseMachine input steps) ≤
2 * steps := by
unfold maxZigzagIndex
rw [Nat.max_le]
constructor
· exact zigzagRunPositions_index_bound
baseMachine input steps 0
· exact zigzagRunPositions_index_bound
baseMachine input steps 1
theorem zigzagSimulation_reaches_run
{baseStates : Nat}
(baseMachine : Machine 2 baseStates)
(input : Fin 2 → List Bool)
(archives : Fin 2 → List TapeSymbol)
(steps horizon : Nat)
(hsteps : steps ≤ horizon) :
ReachesWithin
(zigzagSimulationTypedMachine baseMachine).step
(zigzagReadyConfiguration
(baseMachine.run input 0) archives
(zigzagRunPositions baseMachine input 0)
(2 * horizon + 3))
(zigzagReadyConfiguration
(baseMachine.run input steps) archives
(zigzagRunPositions baseMachine input steps)
(2 * horizon + 3))
(steps * (24 * horizon + 32)) := by
induction steps with
| zero =>
exact ReachesWithin.refl _ _ _
| succ steps ih =>
have hstepsLe : steps ≤ horizon := by omega
have hprevious :=
ih hstepsLe
let configuration := baseMachine.run input steps
let positions :=
zigzagRunPositions baseMachine input steps
let recordCount := 2 * horizon + 3
let macroBound := 24 * horizon + 32
by_cases hhalted :
∃ result,
baseMachine.result configuration.state =
some result
· rcases hhalted with ⟨result, hresult⟩
have hmachineStep :
baseMachine.step configuration =
configuration :=
by
simp [Machine.step, hresult]
have hpositionStep :
zigzagRunPositions baseMachine input
(steps + 1) =
positions := by
simp [zigzagRunPositions, configuration,
positions, hresult]
have hrunStep :
baseMachine.run input (steps + 1) =
configuration := by
rw [Machine.run, hmachineStep]
have hstay :
ReachesWithin
(zigzagSimulationTypedMachine baseMachine).step
(zigzagReadyConfiguration configuration archives
positions recordCount)
(zigzagReadyConfiguration
(baseMachine.run input (steps + 1))
archives
(zigzagRunPositions baseMachine input
(steps + 1))
recordCount)
macroBound := by
rw [hrunStep, hpositionStep]
exact ReachesWithin.refl _ _ _
have hcombined := hprevious.trans hstay
simpa [configuration, positions, recordCount,
macroBound, Nat.succ_eq_add_one,
Nat.add_mul] using hcombined
· have hresult :
baseMachine.result configuration.state =
none := by
cases h :
baseMachine.result configuration.state with
| none => rfl
| some result =>
exact False.elim
(hhalted ⟨result, h⟩)
let action :=
baseMachine.transition configuration.state
(fun i => (configuration.tape i).head)
have hpositionStep :
zigzagRunPositions baseMachine input
(steps + 1) =
fun i =>
(action.2 i).2.updatePosition
(positions i) := by
simp [zigzagRunPositions, configuration,
positions, action, hresult]
have hrunStep :
baseMachine.run input (steps + 1) =
baseMachine.step configuration := by
rfl
have hroom :
∀ i : Fin 2,
zigzagIndex (positions i) + 2 <
recordCount := by
intro i
have hindex :=
zigzagRunPositions_index_bound
baseMachine input steps i
simp only [positions, recordCount]
omega
have hone :=
zigzagSimulation_reaches_base_step
baseMachine configuration archives positions
recordCount hresult hroom
have hmacro :
12 * maxZigzagIndex positions + 32 ≤
macroBound := by
have hmax :=
maxZigzagIndex_runPositions_bound
baseMachine input steps
simp only [positions, macroBound]
omega
have hone' := hone.mono hmacro
have hcombined := hprevious.trans hone'
rw [hrunStep, hpositionStep]
simpa [configuration, positions, recordCount,
macroBound, Nat.succ_eq_add_one,
Nat.add_mul] using hcombined
end SipserGacsLautemann
Source
Auxiliary formalization for the Prove2me mission The Sipser--Gacs--Lautemann Theorem.