Exit-firing specifications, readAct, and the halting adapters
Definitionsgl_fires_exactlyFiresExactly, readAct, and the halting adapters — the common currency for subroutine specifications.
Two specification formats had grown up side by side. HaltsExactly speaks about a machine's result, while andThenState composes on an exit predicate over states. The sweeps of a tape simulation are loops used as the first component of andThenState, so they need exit-firing specifications rather than halting ones, and the two formats meet at every subroutine boundary.
FiresExactly p f c t is the unification: the predicate is first true at exactly time along the orbit of from . HaltsExactly embeds into it via the halting predicate, and FiresExactly.andThenState_halts composes an exit-firing spec for a subroutine with a halting spec for its continuation.
readAct. Applying a simulated machine's transition requires reading the symbols under all heads, acting on them, and remembering what was read — in one step. The existing primitives do not suffice: act acts but forgets, and test remembers a single bit but cannot act. readAct does all three, recording a value computed from the head symbols while applying the induced tape actions, and exits by Option.isSome so that andThenState carries the recorded value into the continuation.
The bridge out. DecidesInPolynomialTime consumes acceptsWithin and rejectsWithin at a bound, whereas the composition machinery produces halting at an exact time. Since halting states absorb, an exact halt at yields the same verdict at every ; HaltsExactly.toMachine_acceptsWithin and its rejecting mirror package this together with the relabelling into the mission's Fin-indexed Machine, so a construction verified through the algebra lands directly in the mission's own class.
import Definitions.Def_sgl_two_track
/-!
# `FiresExactly`, `readAct`, and the halting adapters
Module A of the merge_empty plan (`DESIGN_merge_empty_v2.md`).
Two spec formats coexist in the development: `HaltsExactly` speaks about a
machine's `result`, while `andThenState` composes on an **exit predicate over
states**. The sweeps of the simulation will be loops used as the first
component of `andThenState`, so they need exit-firing specifications, not
halting ones. `FiresExactly` is the common currency: a predicate on
configurations, first true at exactly time `t`. Everything downstream is
stated in this form; `HaltsExactly` embeds into it.
The module also supplies `readAct` — the primitive that *reads* the symbols
under the heads, *acts* on them, and *remembers* what it read. `act` acts but
forgets; `test` remembers one bit but cannot act; applying a simulated
machine's transition needs all three at once.
Finally, the bridge out: a `HaltsExactly` at exact time `t` yields
`acceptsWithin`/`rejectsWithin` at any bound `T ≥ t`, which is what
`DecidesInPolynomialTime` actually consumes.
-/
namespace SipserGacsLautemann
variable {tapes : Nat}
/-! ## The firing specification -/
/-- `pred` is first true at exactly time `t` along the orbit of `step` from
`c`. -/
structure FiresExactly {α : Type*} (pred : α → Bool) (step : α → α)
(c : α) (t : Nat) : Prop where
fires : pred ((step^[t]) c) = true
fresh : ∀ j, j < t → pred ((step^[j]) c) = false
/-- The halting predicate of a machine, as a Boolean on configurations. -/
def haltPred {S : Type} (machine : TypedMachine tapes S) :
TypedConfiguration tapes S → Bool :=
fun c => (machine.result c.state).isSome
/-- `HaltsExactly` is a `FiresExactly` for the halting predicate. -/
theorem HaltsExactly.toFires {S : Type} {machine : TypedMachine tapes S}
{c : TypedConfiguration tapes S} {t : Nat} {v : Bool}
(h : HaltsExactly machine c t v) :
FiresExactly (haltPred machine) machine.step c t := by
constructor
· simp [haltPred, h.halts]
· intro j hj
simp [haltPred, h.fresh j hj]
/-- An exit-firing spec for `M₁` composes with a halting spec for the
continuation — `HaltsExactly.andThenState` in `FiresExactly` clothing. -/
theorem FiresExactly.andThenState_halts {S₁ S₂ : Type}
{M₁ : TypedMachine tapes S₁} {exit : S₁ → Bool}
{M₂ : S₁ → TypedMachine tapes S₂}
{c : TypedConfiguration tapes S₁} {a k : Nat} {v : Bool}
(hf : FiresExactly (fun cfg => exit cfg.state) M₁.step c a)
(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 :=
HaltsExactly.andThenState hf.fires hf.fresh h₂
/-! ## `readAct`: read, act, remember -/
/-- One step that reads the symbols under all heads, applies the induced
actions, and records a value computed from what it read. Never halts on its
own; composed via `andThenState` with exit `Option.isSome`. -/
def TypedMachine.readAct {S : Type}
(program :
(Fin tapes → TapeSymbol) → S × (Fin tapes → TapeSymbol × HeadMove)) :
TypedMachine tapes (Option S) where
start := none
transition := fun state symbols =>
match state with
| none => (some (program symbols).1, (program symbols).2)
| some s => (some s, fun i => (symbols i, HeadMove.stay))
result := fun _ => none
/-- After its single step, `readAct` records the value computed from the head
symbols and its tapes are the applied action. -/
theorem TypedMachine.readAct_run_one {S : Type}
(program :
(Fin tapes → TapeSymbol) → S × (Fin tapes → TapeSymbol × HeadMove))
(tape : Fin tapes → Tape) :
((TypedMachine.readAct program).step^[1])
((TypedMachine.readAct program).startCfg tape) =
⟨some (program (fun i => (tape i).head)).1,
applyAction tape (fun symbols => (program symbols).2)⟩ := by
rw [Function.iterate_one]
rfl
/-- `readAct`'s exit predicate fires at exactly time `1`. -/
theorem TypedMachine.readAct_fires {S : Type}
(program :
(Fin tapes → TapeSymbol) → S × (Fin tapes → TapeSymbol × HeadMove))
(tape : Fin tapes → Tape) :
FiresExactly (fun c => c.state.isSome)
(TypedMachine.readAct program).step
((TypedMachine.readAct program).startCfg tape) 1 := by
constructor
· rw [TypedMachine.readAct_run_one]
rfl
· intro j hj
have hj0 : j = 0 := by omega
subst hj0
rfl
/-! ## Out of `HaltsExactly`, into the time-bounded world -/
theorem TypedMachine.startCfg_ofBits {S : Type} (machine : TypedMachine tapes S)
(input : Fin tapes → List Bool) :
machine.startCfg (fun i => Tape.ofBits (input i)) =
machine.initialConfiguration input := rfl
/-- A machine that halts exactly at `t` still reports the same verdict at any
later bound: halting states absorb. -/
theorem HaltsExactly.result_run_of_le {S : Type} {machine : TypedMachine tapes S}
{input : Fin tapes → List Bool} {t : Nat} {v : Bool}
(h : HaltsExactly machine (machine.initialConfiguration input) t v)
{T : Nat} (hle : t ≤ T) :
machine.result ((machine.run input T).state) = some v := by
obtain ⟨e, rfl⟩ := Nat.exists_eq_add_of_le hle
have ht : machine.result ((machine.run input t).state) = some v := by
rw [TypedMachine.run_eq_iterate_step]
exact h.halts
rw [machine.run_add_eq_of_result_run_eq_some input t e ht]
exact ht
/-- The accepting half of the `DecidesInPolynomialTime` interface, from an
exact halting spec. -/
theorem HaltsExactly.toMachine_acceptsWithin {S : Type} [Fintype S]
{machine : TypedMachine tapes S} {input : Fin tapes → List Bool} {t : Nat}
(h : HaltsExactly machine (machine.initialConfiguration input) t true)
{T : Nat} (hle : t ≤ T) :
machine.toMachine.acceptsWithin input T := by
rw [TypedMachine.toMachine_acceptsWithin_iff]
exact h.result_run_of_le hle
/-- The rejecting half. -/
theorem HaltsExactly.toMachine_rejectsWithin {S : Type} [Fintype S]
{machine : TypedMachine tapes S} {input : Fin tapes → List Bool} {t : Nat}
(h : HaltsExactly machine (machine.initialConfiguration input) t false)
{T : Nat} (hle : t ≤ T) :
machine.toMachine.rejectsWithin input T := by
rw [TypedMachine.toMachine_rejectsWithin_iff]
exact h.result_run_of_le hle
end SipserGacsLautemann