Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A sequential-composition algebra for the mission machine model

Definition
sgl_machine_algebra

by Henry Yuen · Jul 25, 2026 · Mathlib c5ea003 (Lean v4.30.0)

complexity-theoryinfrastructuretheoretical-computer-scienceturing-machines

A sequential-composition algebra for the mission's multitape machine model.

The mission's DecidesInPolynomialTime obliges one to exhibit an explicit machine and count its steps. The existing development supplies almost every hard ingredient — a multi-track tape encoding, a verified single verifier call, the polynomial time-bound algebra — but no way to run one machine and then another. Consequently a scheduler that must issue polynomially many verifier calls cannot be assembled from the single-call result, and every construction is a monolithic hand-built machine with bespoke run lemmas.

This module supplies the missing structure.

Subroutine specifications. HaltsExactly M c t v records that MMM, started in configuration ccc, runs for exactly ttt steps and then reports verdict vvv. Every combinator consumes and produces such specifications, so machines are verified by chaining specifications rather than by unfolding run.

Sequencing. TypedMachine.andThen M₁ M₂ runs M1M_1M1​ and, the instant it halts with answer bbb, hands its tapes to M2(b)M_2(b)M2​(b). The point is that M1M_1M1​'s verdict becomes control flow rather than termination — the "return from subroutine" the raw model lacks. The keystone theorem states that after a+1+ka + 1 + ka+1+k steps the composite is exactly M2(b)M_2(b)M2​(b) after kkk steps on M1M_1M1​'s output tapes:

(M1⊳M2)a+1+k(ιLc)  =  ιR(b,  (M2b)k⟨start, tapes(M1ac)⟩).\big(M_1 \rhd M_2\big)^{a+1+k}(\iota_L c) \;=\; \iota_R\big(b,\; (M_2 b)^{k}\langle \mathrm{start},\, \mathrm{tapes}(M_1^a c)\rangle\big).(M1​⊳M2​)a+1+k(ιL​c)=ιR​(b,(M2​b)k⟨start,tapes(M1a​c)⟩).

Step counts add and tapes thread through. Since the continuation is a function of the previous verdict, andThen also supplies branching. Composition costs nothing in the state space: state types are finite and input-independent, and are relabelled into an initial segment of the naturals only at the very 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, the state space being finite and fixed. With per-round costs supplied by the caller, repeatUntilFalse_rounds computes the state after any number of rounds at total cost ∑i(ci+1)\sum_i (c_i + 1)∑i​(ci​+1). This is the theorem that turns one verifier call into polynomially many.

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 where raw tape reasoning occurs.

Derived control flow. doWhile and the worked two-instruction chain act_act_spec illustrate the intended style: their proofs mention neither step nor run nor any tape, the algebra alone carrying them.

Definition code
import Definitions.Def_sgl_move_left_prefix_reaches
import Mathlib.Data.Fintype.Sum
import Mathlib.Data.Fintype.Prod

/-!
# A sequential-composition 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 _

end SipserGacsLautemann
Source
Standard structured-programming decomposition of Turing-machine constructions (sequencing, branching, bounded iteration), specialized to the multitape model of Def_sipser_gacs_lautemann; the same device by which mechanized complexity developments avoid programming Turing machines directly.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me