Subroutine composition carrying state
Definitionsgl_state_algebraContinuing on the state reached: the data-carrying counterpart of andThen.
andThen branches on a Boolean, because the model's result : State → Option Bool returns exactly one bit. That is enough for control flow but not for carrying data between subroutines. A simulation must hand the simulated machine's state — an element of Fin\ states — from the subroutine that reads the tape symbols to the one that applies the transition, and one bit will not do it.
andThenState M₁ exit M₂ runs until it enters a state satisfying exit, then continues with applied to that state. An arbitrary finite amount of information therefore crosses the subroutine boundary in the control rather than on a tape, which matters in a model where tapes are scarce and the state space is free.
The keystone mirrors the one for andThen: if first exits at time in state , then after steps the composite is exactly after steps started on 's output tapes. Step counts add and tapes thread through, and HaltsExactly.andThenState packages this so that data-carrying compositions chain as freely as Boolean ones.
Structurally the proof is the same three-part argument — mirror the first phase, one hand-off step, mirror the continuation — with one refinement: in the first phase the composite reproduces 's behaviour including its stutter after halting, so the mirroring lemma needs no side condition relating exit to halting.
import Definitions.Def_sgl_scratch_tapes
/-!
# Continuing on the state reached
`andThen` branches on a **`Bool`**, because the model's `result : State → Option
Bool` returns exactly one bit. That is enough for control flow but not for
carrying *data* between subroutines: a simulation has to hand the simulated
machine's state — a `Fin states` — from the subroutine that reads the tape
symbols to the one that applies the transition.
`andThenState` closes that gap. It runs `M₁` until it enters a state satisfying
`exit`, then continues with `M₂` applied to *that state*, so an arbitrary finite
amount of information crosses the boundary in the control rather than on a tape.
Structurally it is the same three-part argument as `andThen`: mirror `M₁` while
it has not exited, one hand-off step, then mirror the continuation.
-/
namespace SipserGacsLautemann
variable {tapes : Nat} {S₁ S₂ : Type}
/-- Run `M₁` until it reaches an `exit` state, then continue with `M₂` applied to
that state. While in the first phase the composite mirrors `M₁` exactly,
including its stutter after halting. -/
def TypedMachine.andThenState (M₁ : TypedMachine tapes S₁) (exit : S₁ → Bool)
(M₂ : S₁ → TypedMachine tapes S₂) :
TypedMachine tapes (S₁ ⊕ S₁ × S₂) where
start := Sum.inl M₁.start
transition := fun state symbols =>
match state with
| Sum.inl s =>
if exit s then
(Sum.inr (s, (M₂ s).start), fun i => (symbols i, HeadMove.stay))
else
match M₁.result s with
| some _ => (Sum.inl s, fun i => (symbols i, HeadMove.stay))
| none =>
let action := M₁.transition s symbols
(Sum.inl action.1, action.2)
| Sum.inr (s, q) =>
let action := (M₂ s).transition q symbols
(Sum.inr (s, action.1), action.2)
result := fun state =>
match state with
| Sum.inl _ => none
| Sum.inr (s, q) => (M₂ s).result q
/-- First-phase configurations of an `andThenState` composite. -/
def TypedConfiguration.inLeftState (c : TypedConfiguration tapes S₁) :
TypedConfiguration tapes (S₁ ⊕ S₁ × S₂) :=
⟨Sum.inl c.state, c.tape⟩
/-- Second-phase configurations, tagged with the state that was handed over. -/
def TypedConfiguration.inRightState (s : S₁) (c : TypedConfiguration tapes S₂) :
TypedConfiguration tapes (S₁ ⊕ S₁ × S₂) :=
⟨Sum.inr (s, c.state), c.tape⟩
theorem TypedMachine.andThenState_result_inLeftState
(M₁ : TypedMachine tapes S₁) (exit : S₁ → Bool)
(M₂ : S₁ → TypedMachine tapes S₂) (c : TypedConfiguration tapes S₁) :
(M₁.andThenState exit M₂).result
(TypedConfiguration.inLeftState (S₂ := S₂) c).state = none := rfl
/-- Before the exit condition fires the composite mirrors `M₁` step for step. -/
theorem TypedMachine.andThenState_iterate_left
(M₁ : TypedMachine tapes S₁) (exit : S₁ → Bool)
(M₂ : S₁ → TypedMachine tapes S₂) (c : TypedConfiguration tapes S₁) :
∀ k : Nat,
(∀ j, j < k → exit ((M₁.step^[j]) c).state = false) →
(((M₁.andThenState exit M₂).step^[k])
(TypedConfiguration.inLeftState c) :
TypedConfiguration tapes (S₁ ⊕ S₁ × S₂)) =
TypedConfiguration.inLeftState ((M₁.step^[k]) c) := by
intro k
induction k with
| zero => intro _; rfl
| succ k ih =>
intro hfresh
have hprev : ∀ j, j < k → exit ((M₁.step^[j]) c).state = false :=
fun j hj => hfresh j (Nat.lt_succ_of_lt hj)
rw [Function.iterate_succ_apply', Function.iterate_succ_apply', ih hprev]
have hno : exit ((M₁.step^[k]) c).state = false :=
hfresh k (Nat.lt_succ_self k)
cases hres : M₁.result ((M₁.step^[k]) c).state with
| some r =>
simp [TypedMachine.step, TypedMachine.andThenState,
TypedConfiguration.inLeftState, hno, hres,
Tape.write_head_self, Tape.move]
| none =>
simp [TypedMachine.step, TypedMachine.andThenState,
TypedConfiguration.inLeftState, hno, hres]
/-- The hand-off: the state reached selects the continuation and the tapes cross
untouched. -/
theorem TypedMachine.andThenState_step_handoff
(M₁ : TypedMachine tapes S₁) (exit : S₁ → Bool)
(M₂ : S₁ → TypedMachine tapes S₂) {c : TypedConfiguration tapes S₁}
(hexit : exit c.state = true) :
(M₁.andThenState exit M₂).step (TypedConfiguration.inLeftState c) =
TypedConfiguration.inRightState c.state
⟨(M₂ c.state).start, c.tape⟩ := by
simp [TypedMachine.step, TypedMachine.andThenState,
TypedConfiguration.inLeftState, TypedConfiguration.inRightState, hexit,
Tape.write_head_self, Tape.move]
/-- After the hand-off the composite mirrors the continuation. -/
theorem TypedMachine.andThenState_iterate_right
(M₁ : TypedMachine tapes S₁) (exit : S₁ → Bool)
(M₂ : S₁ → TypedMachine tapes S₂) (s : S₁)
(c : TypedConfiguration tapes S₂) :
∀ k : Nat,
(((M₁.andThenState exit M₂).step^[k])
(TypedConfiguration.inRightState s c) :
TypedConfiguration tapes (S₁ ⊕ S₁ × S₂)) =
TypedConfiguration.inRightState s (((M₂ s).step^[k]) c) := by
intro k
induction k with
| zero => rfl
| succ k ih =>
rw [Function.iterate_succ_apply', Function.iterate_succ_apply', ih]
cases hres : (M₂ s).result (((M₂ s).step^[k]) c).state with
| some r =>
simp [TypedMachine.step, TypedMachine.andThenState,
TypedConfiguration.inRightState, hres]
| none =>
simp [TypedMachine.step, TypedMachine.andThenState,
TypedConfiguration.inRightState, hres]
/-- **Keystone, data-carrying form.** If `M₁` first exits at time `a` in state
`s`, the composite after `a + 1 + k` steps is `M₂ s` after `k` steps on `M₁`'s
output tapes. -/
theorem TypedMachine.andThenState_iterate
(M₁ : TypedMachine tapes S₁) (exit : S₁ → Bool)
(M₂ : S₁ → TypedMachine tapes S₂) (c : TypedConfiguration tapes S₁) (a : Nat)
(hexit : exit ((M₁.step^[a]) c).state = true)
(hfresh : ∀ j, j < a → exit ((M₁.step^[j]) c).state = false) (k : Nat) :
(((M₁.andThenState exit M₂).step^[a + 1 + k])
(TypedConfiguration.inLeftState c) :
TypedConfiguration tapes (S₁ ⊕ S₁ × S₂)) =
TypedConfiguration.inRightState ((M₁.step^[a]) c).state
(((M₂ ((M₁.step^[a]) c).state).step^[k])
⟨(M₂ ((M₁.step^[a]) c).state).start, ((M₁.step^[a]) c).tape⟩) := by
rw [show a + 1 + k = k + (1 + a) by omega,
Function.iterate_add_apply, Function.iterate_add_apply,
Function.iterate_one]
rw [M₁.andThenState_iterate_left exit M₂ c a hfresh]
rw [M₁.andThenState_step_handoff exit M₂ hexit]
exact M₁.andThenState_iterate_right exit M₂ _ _ k
/-- **Specs compose, carrying state.** The counterpart of
`HaltsExactly.andThen` for data-carrying hand-off. -/
theorem HaltsExactly.andThenState
{M₁ : TypedMachine tapes S₁} {exit : S₁ → Bool}
{M₂ : S₁ → TypedMachine tapes S₂} {c : TypedConfiguration tapes S₁}
{a k : Nat} {v : Bool}
(hexit : exit ((M₁.step^[a]) c).state = true)
(hfresh : ∀ j, j < a → exit ((M₁.step^[j]) c).state = false)
(h₂ : HaltsExactly (M₂ ((M₁.step^[a]) c).state)
((M₂ ((M₁.step^[a]) c).state).startCfg ((M₁.step^[a]) c).tape) k v) :
HaltsExactly (M₁.andThenState exit M₂)
(TypedConfiguration.inLeftState c) (a + 1 + k) v := by
constructor
· rw [M₁.andThenState_iterate exit M₂ c a hexit hfresh k]
exact h₂.halts
· intro j hj
rcases Nat.lt_or_ge j (a + 1) with hsmall | hbig
· have hfr : ∀ i, i < j → exit ((M₁.step^[i]) c).state = false :=
fun i hi => hfresh i (by omega)
rw [M₁.andThenState_iterate_left exit M₂ c j hfr]
exact M₁.andThenState_result_inLeftState exit M₂ _
· obtain ⟨m, hm⟩ := Nat.exists_eq_add_of_le hbig
have hmk : m < k := by omega
rw [hm, M₁.andThenState_iterate exit M₂ c a hexit hfresh m]
exact h₂.fresh m hmk
end SipserGacsLautemann