A subroutine algebra for the mission machine model
Definitionsgl_subroutine_algebraA subroutine algebra for the mission's multitape machine model: sequencing, branching, bounded iteration, and the bridge that makes a loop a first-class subroutine.
The mission's DecidesInPolynomialTime obliges one to exhibit an explicit machine and count its steps. The development already supplies a multi-track tape encoding, the polynomial time-bound algebra, and a verified single verifier call — but no way to run one machine and then another. A scheduler issuing polynomially many calls therefore cannot be assembled from the single-call result, and every construction becomes a monolithic machine with bespoke run lemmas.
Subroutine specifications. HaltsExactly M c t v records that , started in configuration , runs for exactly steps and then reports verdict . Every combinator consumes and produces such specifications, so machines are verified by chaining specifications rather than by unfolding run.
Sequencing and branching. TypedMachine.andThen M₁ M₂ runs and, the instant it halts with answer , hands its tapes to — turning 's verdict into control flow rather than termination, which is the "return from subroutine" the bare model lacks. The keystone states that after steps the composite is exactly after steps on 's output tapes: step counts add and tapes thread through. Because the continuation depends on the previous verdict, the same combinator supplies branching. Composition costs nothing in the state space, which is finite, input-independent, and relabelled into an initial segment of the naturals only at the end.
Iteration. TypedMachine.repeatUntilFalse re-enters the body whenever it reports true, on the body's own output tapes, and halts when it reports false. The loop counter therefore lives on the tapes rather than in the state space — which is what makes an input-dependent number of rounds expressible at all.
A loop is a subroutine. Locating a loop at its round boundaries is not enough to compose it; one also needs that it does not halt in between. repeatUntilFalse_spec closes that gap: given per-round specifications and a final round reporting false, the whole loop is a single HaltsExactly obligation of cost
evaluated by loopCost_const to at constant per-round cost. Loops therefore nest inside andThen chains freely.
Primitives. Three machines suffice: act performs one local action on every tape and continues; test reads the symbols under the heads and reports a Boolean without disturbing the tapes; halt stops with a fixed verdict. Together with sequencing and iteration they form a complete structured-programming language over the model, and they are the only place raw tape reasoning occurs.
import Definitions.Def_sgl_move_left_prefix_reaches
import Mathlib.Data.Fintype.Sum
import Mathlib.Data.Fintype.Prod
/-!
# A subroutine algebra for the mission machine model
Everything in this mission is currently built by exhibiting one monolithic
`TypedMachine` and reasoning about `run` directly. That does not scale past a
single subroutine: there is a verified *single* verifier call
(`encodedVerifierCall_accepts_iff`) but no way to say "run `M₁` to completion,
then continue with `M₂` starting from `M₁`'s final tapes".
This module supplies exactly that missing combinator, `TypedMachine.andThen`,
together with the composition theorem for its step counts. Every remaining
frontier obligation (schedulers that make polynomially many verifier calls and
aggregate the answers) is an iterate of this one combinator.
-/
namespace SipserGacsLautemann
variable {tapes : Nat} {S₁ S₂ : Type}
/-- Run `M₁`; the moment it halts with answer `b`, hand the tapes to `M₂ b`.
The composite never halts inside the `M₁` phase, so `M₁`'s verdict becomes
ordinary control flow instead of termination. -/
def TypedMachine.andThen (M₁ : TypedMachine tapes S₁)
(M₂ : Bool → TypedMachine tapes S₂) :
TypedMachine tapes (S₁ ⊕ Bool × S₂) where
start := Sum.inl M₁.start
transition := fun state symbols =>
match state with
| Sum.inl s =>
match M₁.result s with
| some b =>
(Sum.inr (b, (M₂ b).start), fun i => (symbols i, HeadMove.stay))
| none =>
let action := M₁.transition s symbols
(Sum.inl action.1, action.2)
| Sum.inr (b, s) =>
let action := (M₂ b).transition s symbols
(Sum.inr (b, action.1), action.2)
result := fun state =>
match state with
| Sum.inl _ => none
| Sum.inr (b, s) => (M₂ b).result s
/-- Configurations of the first phase, embedded into the composite. -/
def TypedConfiguration.inLeft (c : TypedConfiguration tapes S₁) :
TypedConfiguration tapes (S₁ ⊕ Bool × S₂) :=
⟨Sum.inl c.state, c.tape⟩
/-- Configurations of the second phase, embedded into the composite. -/
def TypedConfiguration.inRight (b : Bool) (c : TypedConfiguration tapes S₂) :
TypedConfiguration tapes (S₁ ⊕ Bool × S₂) :=
⟨Sum.inr (b, c.state), c.tape⟩
theorem Tape.write_head_self (tape : Tape) : tape.write tape.head = tape := rfl
/-- During the first phase the composite mirrors `M₁` step for step. -/
theorem TypedMachine.andThen_iterate_left
(M₁ : TypedMachine tapes S₁) (M₂ : Bool → TypedMachine tapes S₂)
(c : TypedConfiguration tapes S₁) :
∀ k : Nat,
(∀ j, j < k → M₁.result ((M₁.step^[j]) c).state = none) →
(((M₁.andThen M₂).step^[k]) (TypedConfiguration.inLeft c) :
TypedConfiguration tapes (S₁ ⊕ Bool × S₂)) =
TypedConfiguration.inLeft ((M₁.step^[k]) c) := by
intro k
induction k with
| zero => intro _; rfl
| succ k ih =>
intro hfresh
have hprev : ∀ j, j < k → M₁.result ((M₁.step^[j]) c).state = none :=
fun j hj => hfresh j (Nat.lt_succ_of_lt hj)
rw [Function.iterate_succ_apply', Function.iterate_succ_apply', ih hprev]
have hnone : M₁.result ((M₁.step^[k]) c).state = none :=
hfresh k (Nat.lt_succ_self k)
simp [TypedMachine.step, TypedMachine.andThen,
TypedConfiguration.inLeft, hnone]
/-- The single hand-off step: `M₁`'s verdict selects the continuation and the
tapes are carried across untouched. -/
theorem TypedMachine.andThen_step_handoff
(M₁ : TypedMachine tapes S₁) (M₂ : Bool → TypedMachine tapes S₂)
{c : TypedConfiguration tapes S₁} {b : Bool}
(hhalt : M₁.result c.state = some b) :
(M₁.andThen M₂).step (TypedConfiguration.inLeft c) =
TypedConfiguration.inRight b ⟨(M₂ b).start, c.tape⟩ := by
simp [TypedMachine.step, TypedMachine.andThen,
TypedConfiguration.inLeft, TypedConfiguration.inRight, hhalt,
Tape.write_head_self, Tape.move]
/-- During the second phase the composite mirrors `M₂ b` step for step —
including after `M₂ b` halts, since both sides then stutter. -/
theorem TypedMachine.andThen_iterate_right
(M₁ : TypedMachine tapes S₁) (M₂ : Bool → TypedMachine tapes S₂)
(b : Bool) (c : TypedConfiguration tapes S₂) :
∀ k : Nat,
(((M₁.andThen M₂).step^[k]) (TypedConfiguration.inRight b c) :
TypedConfiguration tapes (S₁ ⊕ Bool × S₂)) =
TypedConfiguration.inRight b (((M₂ b).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₂ b).result (((M₂ b).step^[k]) c).state with
| some r =>
simp [TypedMachine.step, TypedMachine.andThen,
TypedConfiguration.inRight, hres]
| none =>
simp [TypedMachine.step, TypedMachine.andThen,
TypedConfiguration.inRight, hres]
/-- **Keystone.** If `M₁` first halts at time `a` with answer `b`, then the
composite, after `a + 1 + k` steps, is exactly `M₂ b` after `k` steps started
on `M₁`'s final tapes. Step counts add; tapes thread through. -/
theorem TypedMachine.andThen_iterate
(M₁ : TypedMachine tapes S₁) (M₂ : Bool → TypedMachine tapes S₂)
(c : TypedConfiguration tapes S₁) (a : Nat) (b : Bool)
(hhalt : M₁.result ((M₁.step^[a]) c).state = some b)
(hfresh : ∀ j, j < a → M₁.result ((M₁.step^[j]) c).state = none)
(k : Nat) :
(((M₁.andThen M₂).step^[a + 1 + k]) (TypedConfiguration.inLeft c) :
TypedConfiguration tapes (S₁ ⊕ Bool × S₂)) =
TypedConfiguration.inRight b
(((M₂ b).step^[k]) ⟨(M₂ b).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₁.andThen_iterate_left M₂ c a hfresh]
rw [M₁.andThen_step_handoff M₂ hhalt]
exact M₁.andThen_iterate_right M₂ b _ k
/-- The composite's verdict is the continuation's verdict. -/
theorem TypedMachine.andThen_result_inRight
(M₁ : TypedMachine tapes S₁) (M₂ : Bool → TypedMachine tapes S₂)
(b : Bool) (c : TypedConfiguration tapes S₂) :
(M₁.andThen M₂).result (TypedConfiguration.inRight b c).state =
(M₂ b).result c.state := rfl
/-- The composite started on `input` is the first phase started on `input`. -/
theorem TypedMachine.andThen_initialConfiguration
(M₁ : TypedMachine tapes S₁) (M₂ : Bool → TypedMachine tapes S₂)
(input : Fin tapes → List Bool) :
(M₁.andThen M₂).initialConfiguration input =
TypedConfiguration.inLeft (M₁.initialConfiguration input) := rfl
/-- End-to-end form: a verdict for the composite, read off from the two phases.
This is the shape a scheduler proof consumes. -/
theorem TypedMachine.andThen_result_run
(M₁ : TypedMachine tapes S₁) (M₂ : Bool → TypedMachine tapes S₂)
(input : Fin tapes → List Bool) (a : Nat) (b : Bool)
(hhalt :
M₁.result ((M₁.step^[a]) (M₁.initialConfiguration input)).state = some b)
(hfresh :
∀ j, j < a →
M₁.result ((M₁.step^[j]) (M₁.initialConfiguration input)).state = none)
(k : Nat) (verdict : Bool)
(hsecond :
(M₂ b).result
(((M₂ b).step^[k])
⟨(M₂ b).start,
((M₁.step^[a]) (M₁.initialConfiguration input)).tape⟩).state =
some verdict) :
(M₁.andThen M₂).result
((M₁.andThen M₂).run input (a + 1 + k)).state = some verdict := by
rw [TypedMachine.run_eq_iterate_step, M₁.andThen_initialConfiguration M₂ input,
M₁.andThen_iterate M₂ _ a b hhalt hfresh k]
exact hsecond
/-! ## Halting specifications
`HaltsExactly` packages "started here, this machine runs for exactly this many
steps and then reports this verdict". It is the interface every combinator
below consumes and produces, so subroutine specs compose without ever
unfolding `run`. -/
/-- `body` started at `c` first halts after exactly `steps` steps, reporting
`verdict`. -/
structure HaltsExactly (body : TypedMachine tapes S₁)
(c : TypedConfiguration tapes S₁) (steps : Nat) (verdict : Bool) : Prop where
halts : body.result ((body.step^[steps]) c).state = some verdict
fresh : ∀ j, j < steps → body.result ((body.step^[j]) c).state = none
/-! ## Bounded iteration
`repeatUntilFalse` turns a subroutine into a loop: whenever the body halts with
`true` the machine jumps back to the body's start on the body's own output
tapes, and when it halts with `false` the loop halts. The loop counter
therefore lives on the tapes, not in the state space — which is what makes an
*input-dependent* number of rounds expressible at all, since the state space is
finite and fixed. -/
def TypedMachine.repeatUntilFalse (body : TypedMachine tapes S₁) :
TypedMachine tapes S₁ where
start := body.start
transition := fun state symbols =>
match body.result state with
| some true => (body.start, fun i => (symbols i, HeadMove.stay))
| some false => (state, fun i => (symbols i, HeadMove.stay))
| none => body.transition state symbols
result := fun state =>
match body.result state with
| some false => some false
| _ => none
/-- Before the body halts, the loop mirrors it step for step. -/
theorem TypedMachine.repeatUntilFalse_iterate_fresh
(body : TypedMachine tapes S₁) (c : TypedConfiguration tapes S₁) :
∀ k : Nat,
(∀ j, j < k → body.result ((body.step^[j]) c).state = none) →
((body.repeatUntilFalse.step^[k]) c) = (body.step^[k]) c := by
intro k
induction k with
| zero => intro _; rfl
| succ k ih =>
intro hfresh
have hprev : ∀ j, j < k → body.result ((body.step^[j]) c).state = none :=
fun j hj => hfresh j (Nat.lt_succ_of_lt hj)
rw [Function.iterate_succ_apply', Function.iterate_succ_apply', ih hprev]
have hnone : body.result ((body.step^[k]) c).state = none :=
hfresh k (Nat.lt_succ_self k)
simp [TypedMachine.step, TypedMachine.repeatUntilFalse, hnone]
/-- One full round: the body runs to a `true` verdict and control returns to the
body's start with the body's output tapes in place. -/
theorem TypedMachine.repeatUntilFalse_round
(body : TypedMachine tapes S₁) (c : TypedConfiguration tapes S₁) (a : Nat)
(h : HaltsExactly body c a true) :
(body.repeatUntilFalse.step^[a + 1]) c =
⟨body.start, ((body.step^[a]) c).tape⟩ := by
rw [Function.iterate_succ_apply', body.repeatUntilFalse_iterate_fresh c a h.fresh]
simp [TypedMachine.step, TypedMachine.repeatUntilFalse, h.halts,
Tape.write_head_self, Tape.move]
/-- The loop exits exactly when the body reports `false`. -/
theorem TypedMachine.repeatUntilFalse_exit
(body : TypedMachine tapes S₁) (c : TypedConfiguration tapes S₁) (a : Nat)
(h : HaltsExactly body c a false) :
body.repeatUntilFalse.result
((body.repeatUntilFalse.step^[a]) c).state = some false := by
rw [body.repeatUntilFalse_iterate_fresh c a h.fresh]
simp [TypedMachine.repeatUntilFalse, h.halts]
/-- Total cost of `n` rounds whose bodies cost `cost 0, cost 1, …`, each round
paying one extra step for the jump back to the body's start. -/
def loopCost (cost : Nat → Nat) : Nat → Nat
| 0 => 0
| n + 1 => loopCost cost n + (cost n + 1)
/-- **Second keystone.** `rounds` iterations of the loop, with per-round costs
and per-round tape states supplied by the caller. This is the theorem a
scheduler uses to make polynomially many verifier calls: instantiate `config`
with the tape contents before each call and `cost` with each call's running
time. -/
theorem TypedMachine.repeatUntilFalse_rounds
(body : TypedMachine tapes S₁)
(config : Nat → TypedConfiguration tapes S₁) (cost : Nat → Nat)
(rounds : Nat)
(hround : ∀ i, i < rounds →
HaltsExactly body (config i) (cost i) true ∧
config (i + 1) =
⟨body.start, ((body.step^[cost i]) (config i)).tape⟩) :
(body.repeatUntilFalse.step^[loopCost cost rounds]) (config 0) =
config rounds := by
induction rounds with
| zero => rfl
| succ rounds ih =>
have hprev : ∀ i, i < rounds →
HaltsExactly body (config i) (cost i) true ∧
config (i + 1) =
⟨body.start, ((body.step^[cost i]) (config i)).tape⟩ :=
fun i hi => hround i (Nat.lt_succ_of_lt hi)
obtain ⟨hhalt, hnext⟩ := hround rounds (Nat.lt_succ_self rounds)
rw [loopCost, Nat.add_comm (loopCost cost rounds) (cost rounds + 1),
Function.iterate_add_apply, ih hprev,
body.repeatUntilFalse_round (config rounds) (cost rounds) hhalt,
hnext]
/-! ## Composing specifications
`HaltsExactly.andThen` is what makes the algebra usable: it turns two subroutine
specs into a spec for their composite, so a chain of subroutines is verified by
chaining specs rather than by unfolding `run`. -/
/-- The configuration in which `M` begins on the given tapes. -/
def TypedMachine.startCfg (M : TypedMachine tapes S₁) (tape : Fin tapes → Tape) :
TypedConfiguration tapes S₁ :=
⟨M.start, tape⟩
theorem TypedMachine.andThen_result_inLeft
(M₁ : TypedMachine tapes S₁) (M₂ : Bool → TypedMachine tapes S₂)
(c : TypedConfiguration tapes S₁) :
(M₁.andThen M₂).result
(TypedConfiguration.inLeft (S₂ := S₂) c).state = none := rfl
/-- **Specs compose.** `M₁` halts at `a` with `b`; `M₂ b`, started on `M₁`'s
output tapes, halts at `k` with `v`; hence the composite halts at `a + 1 + k`
with `v`. -/
theorem HaltsExactly.andThen
{M₁ : TypedMachine tapes S₁} {M₂ : Bool → TypedMachine tapes S₂}
{c : TypedConfiguration tapes S₁} {a : Nat} {b : Bool} {k : Nat} {v : Bool}
(h₁ : HaltsExactly M₁ c a b)
(h₂ : HaltsExactly (M₂ b) ((M₂ b).startCfg ((M₁.step^[a]) c).tape) k v) :
HaltsExactly (M₁.andThen M₂) (TypedConfiguration.inLeft c) (a + 1 + k) v := by
constructor
· rw [M₁.andThen_iterate M₂ c a b h₁.halts h₁.fresh k]
exact h₂.halts
· intro j hj
rcases Nat.lt_or_ge j (a + 1) with hsmall | hbig
· have hfresh : ∀ i, i < j → M₁.result ((M₁.step^[i]) c).state = none :=
fun i hi => h₁.fresh i (by omega)
rw [M₁.andThen_iterate_left M₂ c j hfresh]
exact M₁.andThen_result_inLeft M₂ _
· obtain ⟨m, hm⟩ := Nat.exists_eq_add_of_le hbig
have hmk : m < k := by omega
rw [hm, M₁.andThen_iterate M₂ c a b h₁.halts h₁.fresh m]
exact h₂.fresh m hmk
/-! ## Primitives
Three machines. With `andThen` (sequencing, and — since its continuation is a
function of the previous verdict — branching) and `repeatUntilFalse` (looping),
they form a complete structured-programming language over the mission's model.
Everything above this line is generic; everything below is the entire stock of
raw tape reasoning the layer needs. -/
/-- The tapes after applying one local action. -/
def applyAction (tape : Fin tapes → Tape)
(action : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove)) :
Fin tapes → Tape :=
fun i =>
Tape.move (Tape.write (tape i) (action (fun j => (tape j).head) i).1)
(action (fun j => (tape j).head) i).2
/-- Perform one local action on every tape, then report `true` so that a
continuation can pick up. -/
def TypedMachine.act
(action : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove)) :
TypedMachine tapes Bool where
start := false
transition := fun _ symbols => (true, action symbols)
result := fun s => if s then some true else none
theorem TypedMachine.act_spec
(action : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove))
(tape : Fin tapes → Tape) :
HaltsExactly (TypedMachine.act action)
((TypedMachine.act action).startCfg tape) 1 true := by
constructor
· simp [TypedMachine.act, TypedMachine.startCfg, TypedMachine.step]
· intro j hj
have hj0 : j = 0 := by omega
subst hj0
simp [TypedMachine.act, TypedMachine.startCfg]
theorem TypedMachine.act_tape
(action : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove))
(tape : Fin tapes → Tape) :
(((TypedMachine.act action).step^[1])
((TypedMachine.act action).startCfg tape)).tape =
applyAction tape action := by
funext i
simp [TypedMachine.act, TypedMachine.startCfg, TypedMachine.step, applyAction]
/-- Read the symbols under the heads and report a Boolean, leaving the tapes
alone. Composed with `andThen` this is `if … then … else …`. -/
def TypedMachine.test (predicate : (Fin tapes → TapeSymbol) → Bool) :
TypedMachine tapes (Option Bool) where
start := none
transition := fun _ symbols =>
(some (predicate symbols), fun i => (symbols i, HeadMove.stay))
result := fun s => s
theorem TypedMachine.test_spec
(predicate : (Fin tapes → TapeSymbol) → Bool) (tape : Fin tapes → Tape) :
HaltsExactly (TypedMachine.test predicate)
((TypedMachine.test predicate).startCfg tape) 1
(predicate (fun i => (tape i).head)) := by
constructor
· simp [TypedMachine.test, TypedMachine.startCfg, TypedMachine.step]
· intro j hj
have hj0 : j = 0 := by omega
subst hj0
simp [TypedMachine.test, TypedMachine.startCfg]
theorem TypedMachine.test_tape
(predicate : (Fin tapes → TapeSymbol) → Bool) (tape : Fin tapes → Tape) :
(((TypedMachine.test predicate).step^[1])
((TypedMachine.test predicate).startCfg tape)).tape = tape := by
funext i
simp [TypedMachine.test, TypedMachine.startCfg, TypedMachine.step,
Tape.write_head_self, Tape.move]
/-- Halt immediately with a fixed verdict. -/
def TypedMachine.halt (b : Bool) : TypedMachine tapes Unit where
start := ()
transition := fun _ symbols => ((), fun i => (symbols i, HeadMove.stay))
result := fun _ => some b
theorem TypedMachine.halt_spec (b : Bool) (c : TypedConfiguration tapes Unit) :
HaltsExactly (TypedMachine.halt b) c 0 b := by
constructor
· simp [TypedMachine.halt]
· intro j hj; omega
/-! ## Derived control flow
These are the two shapes a scheduler is written in. Note that no proof below
mentions `step`, `run`, or a tape: the algebra alone carries them. -/
/-- Straight-line code: two actions in sequence, three steps, tapes composed.
A worked example of chaining specs with `HaltsExactly.andThen`. -/
theorem TypedMachine.act_act_spec
(f g : (Fin tapes → TapeSymbol) → (Fin tapes → TapeSymbol × HeadMove))
(tape : Fin tapes → Tape) :
HaltsExactly
((TypedMachine.act f).andThen (fun _ => TypedMachine.act g))
(TypedConfiguration.inLeft ((TypedMachine.act f).startCfg tape))
(1 + 1 + 1) true := by
have h₂ :
HaltsExactly (TypedMachine.act g)
((TypedMachine.act g).startCfg
(((TypedMachine.act f).step^[1])
((TypedMachine.act f).startCfg tape)).tape) 1 true := by
rw [TypedMachine.act_tape]
exact TypedMachine.act_spec g (applyAction tape f)
exact HaltsExactly.andThen (TypedMachine.act_spec f tape) h₂
/-- `repeat body until cond fails` — the loop a scheduler runs once per verifier
call. The round count lives on the tapes, so it may depend on the input. -/
def TypedMachine.doWhile (body : TypedMachine tapes S₁)
(cond : (Fin tapes → TapeSymbol) → Bool) :
TypedMachine tapes ((S₁ ⊕ Bool × Option Bool)) :=
(body.andThen (fun _ => TypedMachine.test cond)).repeatUntilFalse
/-- One round of `doWhile`: the body's cost plus two, and the loop continues
exactly when `cond` holds of the body's output tapes. -/
theorem TypedMachine.doWhile_round_spec
(body : TypedMachine tapes S₁) (cond : (Fin tapes → TapeSymbol) → Bool)
(tape : Fin tapes → Tape) (a : Nat) (v : Bool)
(hbody : HaltsExactly body (body.startCfg tape) a v) :
HaltsExactly (body.andThen (fun _ => TypedMachine.test cond))
(TypedConfiguration.inLeft (body.startCfg tape)) (a + 1 + 1)
(cond (fun i => (((body.step^[a]) (body.startCfg tape)).tape i).head)) :=
HaltsExactly.andThen hbody (TypedMachine.test_spec cond _)
/-- The round machine leaves exactly the body's output tapes: the test is
non-destructive, so tape reasoning stays local to the body. -/
theorem TypedMachine.doWhile_round_tape
(body : TypedMachine tapes S₁) (cond : (Fin tapes → TapeSymbol) → Bool)
(tape : Fin tapes → Tape) (a : Nat) (b : Bool)
(hhalt : body.result ((body.step^[a]) (body.startCfg tape)).state = some b)
(hfresh : ∀ j, j < a →
body.result ((body.step^[j]) (body.startCfg tape)).state = none) :
(((body.andThen (fun _ => TypedMachine.test cond)).step^[a + 1 + 1])
(TypedConfiguration.inLeft (body.startCfg tape))).tape =
((body.step^[a]) (body.startCfg tape)).tape := by
rw [body.andThen_iterate (fun _ => TypedMachine.test cond)
(body.startCfg tape) a b hhalt hfresh 1]
exact TypedMachine.test_tape cond _
/-! ## Generic loop specifications
`repeatUntilFalse_rounds` locates the machine at round boundaries; to feed a
loop into `HaltsExactly.andThen` one also needs that it does not halt in
between. These three lemmas close that gap once, generically. -/
variable {S : Type}
/-- Strictly before the body halts, the loop has not halted either. -/
theorem TypedMachine.repeatUntilFalse_pre_fresh
(body : TypedMachine tapes S) (c : TypedConfiguration tapes S)
(a : Nat) (v : Bool) (h : HaltsExactly body c a v) :
∀ t, t < a →
body.repeatUntilFalse.result
((body.repeatUntilFalse.step^[t]) c).state = none := by
intro t ht
rw [body.repeatUntilFalse_iterate_fresh c t (fun j hj => h.fresh j (by omega))]
simp [TypedMachine.repeatUntilFalse, h.fresh t ht]
/-- A round that ends in `true` does not halt the loop: it restarts it. -/
theorem TypedMachine.repeatUntilFalse_round_fresh
(body : TypedMachine tapes S) (c : TypedConfiguration tapes S)
(a : Nat) (h : HaltsExactly body c a true) :
∀ t, t < a + 1 →
body.repeatUntilFalse.result
((body.repeatUntilFalse.step^[t]) c).state = none := by
intro t ht
rcases Nat.lt_or_ge t a with hlt | hge
· exact body.repeatUntilFalse_pre_fresh c a true h t hlt
· have hta : t = a := by omega
subst hta
rw [body.repeatUntilFalse_iterate_fresh c t h.fresh]
simp [TypedMachine.repeatUntilFalse, h.halts]
theorem TypedMachine.repeatUntilFalse_rounds_fresh
(body : TypedMachine tapes S)
(config : Nat → TypedConfiguration tapes S) (cost : Nat → Nat) (rounds : Nat)
(hround : ∀ i, i < rounds →
HaltsExactly body (config i) (cost i) true ∧
config (i + 1) = ⟨body.start, ((body.step^[cost i]) (config i)).tape⟩) :
∀ j, j < loopCost cost rounds →
body.repeatUntilFalse.result
((body.repeatUntilFalse.step^[j]) (config 0)).state = none := by
induction rounds with
| zero => intro j hj; simp [loopCost] at hj
| succ rounds ih =>
intro j hj
rcases Nat.lt_or_ge j (loopCost cost rounds) with hlt | hge
· exact ih (fun i hi => hround i (by omega)) j hlt
· obtain ⟨t, ht⟩ := Nat.exists_eq_add_of_le hge
have htlt : t < cost rounds + 1 := by
rw [loopCost] at hj; omega
rw [ht, Nat.add_comm, Function.iterate_add_apply,
body.repeatUntilFalse_rounds config cost rounds
(fun i hi => hround i (by omega))]
exact body.repeatUntilFalse_round_fresh (config rounds) (cost rounds)
(hround rounds (by omega)).1 t htlt
/-- **The loop as a subroutine.** Given per-round specs and a final round that
reports `false`, the whole loop is a `HaltsExactly` subroutine of cost
`loopCost cost rounds + a` — and therefore composes with `andThen`. -/
theorem TypedMachine.repeatUntilFalse_spec
(body : TypedMachine tapes S)
(config : Nat → TypedConfiguration tapes S) (cost : Nat → Nat)
(rounds : Nat) (a : Nat)
(hround : ∀ i, i < rounds →
HaltsExactly body (config i) (cost i) true ∧
config (i + 1) = ⟨body.start, ((body.step^[cost i]) (config i)).tape⟩)
(hexit : HaltsExactly body (config rounds) a false) :
HaltsExactly body.repeatUntilFalse (config 0)
(loopCost cost rounds + a) false := by
have hrun := body.repeatUntilFalse_rounds config cost rounds hround
constructor
· rw [Nat.add_comm, Function.iterate_add_apply, hrun]
exact body.repeatUntilFalse_exit (config rounds) a hexit
· intro j hj
rcases Nat.lt_or_ge j (loopCost cost rounds) with hlt | hge
· exact body.repeatUntilFalse_rounds_fresh config cost rounds hround j hlt
· obtain ⟨t, ht⟩ := Nat.exists_eq_add_of_le hge
have htlt : t < a := by omega
rw [ht, Nat.add_comm, Function.iterate_add_apply, hrun]
exact body.repeatUntilFalse_pre_fresh (config rounds) a false hexit t htlt
theorem loopCost_const (c : Nat) :
∀ n : Nat, loopCost (fun _ => c) n = n * (c + 1) := by
intro n
induction n with
| zero => simp [loopCost]
| succ n ih => rw [loopCost, ih, Nat.succ_mul]
end SipserGacsLautemann