Branch selection across state types
Definitionsgl_machine_eithercomplexity-theoryinfrastructuretheoretical-computer-scienceturing-machines
Branch selection between machines of different state types.
andThen and andThenState dispatch into a family over one fixed state type, so two continuation branches must share their state type — which structurally different branches never do. TypedMachine.either A B runs on the sum: the Boolean selects which component starts, each component simulates its machine exactly (step-for-step, by induction), and HaltsExactly transfers along both embeddings. This is the missing dispatch primitive for top-level branches — the dilation's empty-input case, and ahead, the scheduler families'.
Definition code
import Definitions.Def_sgl_shift_seg
/-!
# Branch selection between machines of different state types
`andThen`/`andThenState` dispatch into a *family* over a fixed state type, so
two continuation branches must share their state type — which structurally
different branches never do. `TypedMachine.either A B` runs on the sum type:
the Boolean selects which component starts, and each component simulates its
machine exactly. This is the missing combinator for top-level dispatches
(dilation's empty-input branch; later, the scheduler families' branches).
-/
namespace SipserGacsLautemann
variable {tapes : Nat} {SA SB : Type}
/-- Run `A` (on `true`) or `B` (on `false`), over the sum of their states. -/
def TypedMachine.either (A : TypedMachine tapes SA) (B : TypedMachine tapes SB)
(choose : Bool) : TypedMachine tapes (SA ⊕ SB) where
start := if choose then Sum.inl A.start else Sum.inr B.start
transition := fun s symbols =>
match s with
| .inl sa => ((A.transition sa symbols).1 |> Sum.inl,
(A.transition sa symbols).2)
| .inr sb => ((B.transition sb symbols).1 |> Sum.inr,
(B.transition sb symbols).2)
result := fun s =>
match s with
| .inl sa => A.result sa
| .inr sb => B.result sb
/-- The left component simulates `A` exactly. -/
theorem TypedMachine.either_step_inl (A : TypedMachine tapes SA)
(B : TypedMachine tapes SB) (choose : Bool) (k : Nat)
(sa : SA) (T : Fin tapes → Tape) :
(((A.either B choose).step^[k]) ⟨Sum.inl sa, T⟩ :
TypedConfiguration tapes (SA ⊕ SB)) =
⟨Sum.inl ((A.step^[k]) ⟨sa, T⟩).state, ((A.step^[k]) ⟨sa, T⟩).tape⟩ := by
induction k generalizing sa T with
| zero => rfl
| succ k ih =>
rw [Function.iterate_succ_apply, Function.iterate_succ_apply]
have hstep : (A.either B choose).step ⟨Sum.inl sa, T⟩ =
⟨Sum.inl (A.step ⟨sa, T⟩).state, (A.step ⟨sa, T⟩).tape⟩ := by
cases hres : A.result sa with
| some v =>
simp only [TypedMachine.step, TypedMachine.either, hres]
| none =>
simp only [TypedMachine.step, TypedMachine.either, hres]
rw [hstep]
have := ih (A.step ⟨sa, T⟩).state (A.step ⟨sa, T⟩).tape
rw [show (⟨(A.step ⟨sa, T⟩).state, (A.step ⟨sa, T⟩).tape⟩ :
TypedConfiguration tapes SA) = A.step ⟨sa, T⟩ from rfl] at this
exact this
/-- The right component simulates `B` exactly. -/
theorem TypedMachine.either_step_inr (A : TypedMachine tapes SA)
(B : TypedMachine tapes SB) (choose : Bool) (k : Nat)
(sb : SB) (T : Fin tapes → Tape) :
(((A.either B choose).step^[k]) ⟨Sum.inr sb, T⟩ :
TypedConfiguration tapes (SA ⊕ SB)) =
⟨Sum.inr ((B.step^[k]) ⟨sb, T⟩).state, ((B.step^[k]) ⟨sb, T⟩).tape⟩ := by
induction k generalizing sb T with
| zero => rfl
| succ k ih =>
rw [Function.iterate_succ_apply, Function.iterate_succ_apply]
have hstep : (A.either B choose).step ⟨Sum.inr sb, T⟩ =
⟨Sum.inr (B.step ⟨sb, T⟩).state, (B.step ⟨sb, T⟩).tape⟩ := by
cases hres : B.result sb with
| some v =>
simp only [TypedMachine.step, TypedMachine.either, hres]
| none =>
simp only [TypedMachine.step, TypedMachine.either, hres]
rw [hstep]
have := ih (B.step ⟨sb, T⟩).state (B.step ⟨sb, T⟩).tape
rw [show (⟨(B.step ⟨sb, T⟩).state, (B.step ⟨sb, T⟩).tape⟩ :
TypedConfiguration tapes SB) = B.step ⟨sb, T⟩ from rfl] at this
exact this
/-- `HaltsExactly` transfers along the left embedding. -/
theorem HaltsExactly.either_inl {A : TypedMachine tapes SA}
(B : TypedMachine tapes SB) (choose : Bool)
{sa : SA} {T : Fin tapes → Tape} {t : Nat} {v : Bool}
(h : HaltsExactly A ⟨sa, T⟩ t v) :
HaltsExactly (A.either B choose) ⟨Sum.inl sa, T⟩ t v := by
constructor
· rw [TypedMachine.either_step_inl]
exact h.halts
· intro j hj
rw [TypedMachine.either_step_inl]
exact h.fresh j hj
/-- `HaltsExactly` transfers along the right embedding. -/
theorem HaltsExactly.either_inr (A : TypedMachine tapes SA)
{B : TypedMachine tapes SB} (choose : Bool)
{sb : SB} {T : Fin tapes → Tape} {t : Nat} {v : Bool}
(h : HaltsExactly B ⟨sb, T⟩ t v) :
HaltsExactly (A.either B choose) ⟨Sum.inr sb, T⟩ t v := by
constructor
· rw [TypedMachine.either_step_inr]
exact h.halts
· intro j hj
rw [TypedMachine.either_step_inr]
exact h.fresh j hj
@[simp] theorem TypedMachine.either_start_true (A : TypedMachine tapes SA)
(B : TypedMachine tapes SB) :
(A.either B true).start = Sum.inl A.start := rfl
@[simp] theorem TypedMachine.either_start_false (A : TypedMachine tapes SA)
(B : TypedMachine tapes SB) :
(A.either B false).start = Sum.inr B.start := rfl
end SipserGacsLautemann
Source
Sum-type dispatch combinator; builds on Def_sgl_shift_seg.