Configuration-tracking composition
Definitionsgl_step_chainConfiguration-tracking composition: the chaining tools of the step program.
The outer simulation loop's round record evaluates its next, stop and verdict functions on the round body's terminal state, so the step program's specification must pin its final configuration exactly — tapes and state. chainStepC, chainStepD and chainStepS are the configuration-tracking forms of junction composition, for constant, verdict-dispatching and state-dispatching continuations respectively: each junction contributes one inRight layer to an explicit nested terminal term, on which those functions evaluate by rfl.
carryQ sits at a chain's end with one job: place the simulated machine's next state into the terminal term where a shallow peel can find it. peelB and peelS are the layer projections; a fixed pipeline of them extracts the payload from the fixed nesting.
import Definitions.Def_sgl_read_bits
/-!
# Configuration-tracking composition
Module E of the merge_empty plan, third part: the chaining tools for the step
program.
The outer simulation loop's `LoopRound` record evaluates `next`, `stop` and
`verdict` on the round body's **terminal state**, so the step program's
specification must pin its final configuration exactly — tapes *and* state.
`chainStepC` and `chainStepD` are the config-tracking forms of `chainStep`:
each junction contributes one `inRight` layer to an explicit nested terminal
term, on which those functions evaluate by `rfl`.
At the chain's end sits `carryQ`, whose one job is to place the simulated
machine's next state into the terminal term where a shallow peel can find it.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-! ## Config-tracking chain steps -/
/-- Constant continuation, full final configuration. -/
theorem chainStepC {S₁ S₂ : Type} {M₁ : TypedMachine tapes S₁}
{M₂ : TypedMachine tapes S₂} {T T' : Fin tapes → Tape}
{a : Nat} {b : Bool} {k : Nat} {v : Bool}
(h₁ : HaltsExactly M₁ (M₁.startCfg T) a b)
(htp : ((M₁.step^[a]) (M₁.startCfg T)).tape = T')
(h₂ : HaltsExactly M₂ (M₂.startCfg T') k v) :
HaltsExactly (M₁.andThen fun _ => M₂)
((M₁.andThen fun _ => M₂).startCfg T) (a + 1 + k) v ∧
((M₁.andThen fun _ => M₂).step^[a + 1 + k])
((M₁.andThen fun _ => M₂).startCfg T) =
TypedConfiguration.inRight b ((M₂.step^[k]) (M₂.startCfg T')) := by
constructor
· exact HaltsExactly.andThen (M₂ := fun _ => M₂) h₁ (by rw [htp]; exact h₂)
· have hcfg : (M₁.andThen fun _ => M₂).startCfg T =
TypedConfiguration.inLeft (M₁.startCfg T) := rfl
rw [hcfg, TypedMachine.andThen_iterate M₁ (fun _ => M₂) _ a b h₁.halts
h₁.fresh k, htp]
rfl
/-- Verdict-dispatching continuation, full final configuration. -/
theorem chainStepD {S₁ S₂ : Type} {M₁ : TypedMachine tapes S₁}
(M₂ : Bool → TypedMachine tapes S₂) {T T' : Fin tapes → Tape}
{a : Nat} {b : Bool} {k : Nat} {v : Bool}
(h₁ : HaltsExactly M₁ (M₁.startCfg T) a b)
(htp : ((M₁.step^[a]) (M₁.startCfg T)).tape = T')
(h₂ : HaltsExactly (M₂ b) ((M₂ b).startCfg T') k v) :
HaltsExactly (M₁.andThen M₂) ((M₁.andThen M₂).startCfg T) (a + 1 + k) v ∧
((M₁.andThen M₂).step^[a + 1 + k]) ((M₁.andThen M₂).startCfg T) =
TypedConfiguration.inRight b
(((M₂ b).step^[k]) ((M₂ b).startCfg T')) := by
constructor
· exact HaltsExactly.andThen h₁ (by rw [htp]; exact h₂)
· have hcfg : (M₁.andThen M₂).startCfg T =
TypedConfiguration.inLeft (M₁.startCfg T) := rfl
rw [hcfg, TypedMachine.andThen_iterate M₁ M₂ _ a b h₁.halts h₁.fresh k,
htp]
rfl
/-- State-dispatching continuation (through `andThenState`), full final
configuration. The first machine's exit state is remembered in the composite's
terminal term. -/
theorem chainStepS {S₁ S₂ : Type} {M₁ : TypedMachine tapes S₁}
{exit : S₁ → Bool} (M₂ : S₁ → TypedMachine tapes S₂)
{T T' : Fin tapes → Tape} {a : Nat} {st : S₁} {k : Nat} {v : Bool}
(hexit : exit ((M₁.step^[a]) (M₁.startCfg T)).state = true)
(hfresh : ∀ j, j < a →
exit ((M₁.step^[j]) (M₁.startCfg T)).state = false)
(hst : ((M₁.step^[a]) (M₁.startCfg T)).state = st)
(htp : ((M₁.step^[a]) (M₁.startCfg T)).tape = T')
(h₂ : HaltsExactly (M₂ st) ((M₂ st).startCfg T') k v) :
HaltsExactly (M₁.andThenState exit M₂)
((M₁.andThenState exit M₂).startCfg T) (a + 1 + k) v ∧
((M₁.andThenState exit M₂).step^[a + 1 + k])
((M₁.andThenState exit M₂).startCfg T) =
TypedConfiguration.inRightState st
(((M₂ st).step^[k]) ((M₂ st).startCfg T')) := by
have hcfg : (M₁.andThenState exit M₂).startCfg T =
TypedConfiguration.inLeftState (M₁.startCfg T) := rfl
constructor
· rw [hcfg]
exact HaltsExactly.andThenState hexit hfresh (by rw [hst, htp]; exact h₂)
· rw [hcfg, TypedMachine.andThenState_iterate M₁ exit M₂ _ a hexit hfresh k,
hst, htp]
rfl
/-! ## Carrying the next state out of the chain -/
/-- Halt after one step, with a payload in the state where the loop's `next`
function can read it. -/
def carryQ {Q : Type} (q : Q) : TypedMachine tapes (Option Q) where
start := none
transition := fun _ symbols => (some q, fun j => (symbols j, HeadMove.stay))
result := fun s => match s with
| some _ => some false
| none => none
theorem carryQ_run {Q : Type} (q : Q) (tape : Fin tapes → Tape) :
((carryQ (tapes := tapes) q).step^[1]) ((carryQ q).startCfg tape) =
⟨some q, tape⟩ := by
show (carryQ q).step ((carryQ q).startCfg tape) = _
simp only [TypedMachine.step, carryQ]
congr 1
theorem carryQ_spec {Q : Type} (q : Q) (tape : Fin tapes → Tape) :
HaltsExactly (carryQ (tapes := tapes) q) ((carryQ q).startCfg tape) 1
false := by
constructor
· rw [carryQ_run]
rfl
· intro j hj
have : j = 0 := by omega
subst this
rfl
/-! ## Peeling the terminal term -/
/-- One `andThen` layer of a terminal state. -/
def peelB {S₁ S₂ : Type} : S₁ ⊕ Bool × S₂ → Option S₂
| .inr (_, s) => some s
| .inl _ => none
/-- One `andThenState` layer of a terminal state. -/
def peelS {S₁ S₂ : Type} : S₁ ⊕ S₁ × S₂ → Option S₂
| .inr (_, s) => some s
| .inl _ => none
@[simp] theorem peelB_inRight {S₁ S₂ : Type} (b : Bool)
(c : TypedConfiguration tapes S₂) :
peelB (S₁ := S₁) (TypedConfiguration.inRight b c).state = some c.state :=
rfl
@[simp] theorem peelS_inRightState {S₁ S₂ : Type} (st : S₁)
(c : TypedConfiguration tapes S₂) :
peelS (TypedConfiguration.inRightState st c).state = some c.state := rfl
end SipserGacsLautemann