Composing initialisation with the loop
Definitionsgl_merge_composeComposing initialisation with the loop, plus the bookkeeping the final theorem needs.
mergeComposite writes the initial region and then simulates; mergeComposite_spec says that from physical tapes matching the virtual ones below the host, with the host and both hosted virtual tapes empty, it halts with the simulated machine's answer in at most steps.
Two anticipated obstacles turned out not to exist. The index arithmetic relating to needs no casts at all: Nat.add recurses on its second argument, so the two are definitionally equal and every statement typechecks across the boundary unchanged. And the composite's state type — seventeen layers of sums and products over an Option of a function type — has a Fintype instance by ordinary synthesis, once Option's instance is in scope. The toMachine bridge then applies with no bespoke encoding.
Also here: running a machine is iterating its step; a halted machine stays put; and scratch padding does not change totalInputLength, so the two scratch-paddings of an input give the same time bound.
import Definitions.Def_sgl_merge_init
import Definitions.Def_sgl_polynomial_closures
import Mathlib.Data.Fintype.Option
import Mathlib.Data.Fintype.Sum
import Mathlib.Data.Fintype.Prod
import Mathlib.Data.Fintype.Pi
/-!
# Composing initialisation with the loop
Module F3 of DESIGN_step_spec_endgame, first part: the machine that writes the
initial region and then runs the simulation, together with the small facts the
final theorem needs about inputs and running times.
Two things anticipated as friction turned out not to be. The index arithmetic
relating `tapes + (scratch + 2)` to `(tapes + scratch) + 2` needs no casts —
`Nat.add` recurses on its second argument, so the two are *definitionally*
equal. And the composite's state type, deep as it is, has a `Fintype`
instance by synthesis once `Option`'s is in scope.
-/
namespace SipserGacsLautemann
set_option synthInstance.maxSize 4000
set_option synthInstance.maxHeartbeats 2000000
variable {states : Nat}
/-! ## Running a machine is iterating its step -/
theorem Machine.run_eq_iterate {n : Nat} (M : Machine n states)
(input : Fin n → List Bool) (t : Nat) :
M.run input t = (M.step^[t]) (initialConfiguration M input) := by
induction t with
| zero => rfl
| succ t ih => rw [Machine.run, ih, Function.iterate_succ_apply']
/-- A halted machine stays where it is. -/
theorem Machine.step_of_halted {n : Nat} (M : Machine n states)
(c : Configuration n states) (h : (M.result c.state).isSome) :
M.step c = c := by
unfold Machine.step
cases hr : M.result c.state with
| none => rw [hr] at h; simp at h
| some b => rfl
/-! ## Scratch padding does not change the input length -/
theorem totalInputLength_withScratch {tapes : Nat} (scratch : Nat)
(input : Fin tapes → List Bool) :
totalInputLength (withScratch scratch input) = totalInputLength input := by
classical
unfold totalInputLength
rw [List.sum_ofFn, List.sum_ofFn, Fin.sum_univ_add]
have hleft : ∀ i : Fin tapes,
((withScratch scratch input) (Fin.castAdd scratch i)).length =
(input i).length := by
intro i
have hlt : (Fin.castAdd scratch i).val < tapes := i.isLt
simp [withScratch, hlt]
have hright : ∀ i : Fin scratch,
((withScratch scratch input) (Fin.natAdd tapes i)).length = 0 := by
intro i
have hge : ¬ ((Fin.natAdd tapes i).val < tapes) := by simp
simp [withScratch, hge]
rw [Finset.sum_congr rfl (fun i _ => hleft i),
Finset.sum_congr rfl (fun i _ => hright i)]
simp
/-- The two scratch paddings of the same input agree wherever both are
defined, so the physical and virtual tapes coincide below the host. -/
theorem withScratch_agree {tapes : Nat} (scratch : Nat)
(input : Fin tapes → List Bool) (j : Nat) (hj : j < tapes + scratch) :
withScratch (scratch + 1) input ⟨j, by omega⟩ =
withScratch (scratch + 2) input ⟨j, by omega⟩ := by
by_cases h : j < tapes <;> simp [withScratch, h]
/-! ## The composite machine -/
/-- Write the initial region, then simulate. -/
noncomputable def mergeComposite (tapes' : Nat)
(M : Machine (tapes' + 2) states) (q₀ : Fin states) :=
(initRegion (Fin.last tapes')).andThen fun _ =>
mergeMachine tapes' M q₀
/-- **The composite decides what the simulated machine decides.** Given the
physical tapes (host empty) matching the virtual ones below the host, and the
two hosted virtual tapes empty, the composite halts with the simulated
machine's answer. -/
theorem mergeComposite_spec {tapes' : Nat} (M : Machine (tapes' + 2) states)
(virt : Configuration (tapes' + 2) states)
(base : Fin (tapes' + 1) → Tape) (rounds : Nat) (ans : Bool)
(hident : IdentPart tapes' virt base)
(hhost : ∀ sd, virt.tape (hostIdx tapes' sd) = ⟨[], TapeSymbol.blank, []⟩)
(hbase : base (Fin.last tapes') = ⟨[], TapeSymbol.blank, []⟩)
(hlive : ∀ i, i ≤ rounds → M.result ((M.step^[i]) virt).state = none)
(hhalt : M.result ((M.step^[rounds + 1]) virt).state = some ans) :
∃ total : Nat,
total ≤ 15 + (rounds + 1) * (500 * (1 + 2 * rounds) + 1501) ∧
HaltsExactly (mergeComposite tapes' M virt.state)
((mergeComposite tapes' M virt.state).startCfg base) total ans := by
classical
set R₀ := initRound M virt base hident hhost with hR₀
obtain ⟨loopTotal, hloopBound, hloop⟩ :=
mergeMachine_spec R₀ rounds ans (by simpa [hR₀] using hlive)
(by simpa [hR₀] using hhalt)
-- the initial region
obtain ⟨hinit, hinitTape⟩ := initRegion_spec (Fin.last tapes') base hbase
-- the loop starts where the initial region left off
have hstart : (mergeMachine tapes' M R₀.virt.state).startCfg R₀.park =
TypedConfiguration.inLoop R₀.virt.state
((stepProgram tapes' M R₀.virt.state).startCfg R₀.park) := rfl
have hloop' : HaltsExactly (mergeMachine tapes' M virt.state)
((mergeMachine tapes' M virt.state).startCfg
(Function.update base (Fin.last tapes')
(ParkedTape [initBlock] [TapeSymbol.blank]))) loopTotal ans := by
rw [show (Function.update base (Fin.last tapes')
(ParkedTape [initBlock] [TapeSymbol.blank])) = R₀.park from rfl]
exact hloop
have hchain := chainStepC hinit hinitTape hloop'
refine ⟨14 + 1 + loopTotal, ?_, hchain.1⟩
have hlen : R₀.blocks.length = 1 := rfl
rw [hlen] at hloopBound
have hnorm : 500 * (1 + 2 * rounds) + 1500 + 1 =
500 * (1 + 2 * rounds) + 1501 := by omega
rw [hnorm] at hloopBound
omega
end SipserGacsLautemann