Documentation

PolyFun.PFunctor.Dynamical.DynComputation.Termination

Qualitative termination of returning dynamical computations #

This module separates branchwise well-founded termination from termination within a uniform natural-number query budget. Accessibility of the visible query-child relation is strong enough to extract a well-founded FreeM program, including for infinitely branching programs whose branch depths have no uniform bound.

Query accessibility #

def PFunctor.DynSystem.DynComputation.QueryChild {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (child parent : M.State) :

The strict child relation generated by one visible query. Terminal states have no children.

Equations
Instances For
    def PFunctor.DynSystem.DynComputation.TerminatesFrom {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (state : M.State) :

    Every branch from state contains only finitely many visible queries. Unlike ResolvesIn, different branches need not share a natural-number bound.

    Equations
    Instances For
      theorem PFunctor.DynSystem.DynComputation.queryChild_of_view {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (state : M.State) (position : p.A) (next : p.B position → M.State) (direction : p.B position) (hview : M.view state = Sum.inr ⟨position, next⟩) :
      M.QueryChild (next direction) state
      @[simp]
      theorem PFunctor.DynSystem.DynComputation.terminatesFrom_return {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (state : M.State) (value : β) (hview : M.view state = Sum.inl value) :
      theorem PFunctor.DynSystem.DynComputation.terminatesFrom_query_iff {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (state : M.State) (position : p.A) (next : p.B position → M.State) (hview : M.view state = Sum.inr ⟨position, next⟩) :
      M.TerminatesFrom state ↔ ∀ (direction : p.B position), M.TerminatesFrom (next direction)

      Well-founded-program extraction #

      def PFunctor.DynSystem.DynComputation.toFreeMFrom {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (_state : M.State) :
      M.TerminatesFrom _state → p.FreeM β

      Extract the well-founded free program represented below an accessible hidden state. Lean's computable accessibility recursor Acc.recC may eliminate into Type, so this construction does not choose branch witnesses.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        def PFunctor.DynSystem.DynComputation.toFreeM {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (termination : ∀ (input : α), M.TerminatesFrom (M.init input)) (input : α) :
        p.FreeM β

        Extract the well-founded program family represented from every input-selected initial state.

        Equations
        Instances For
          @[simp]
          theorem PFunctor.DynSystem.DynComputation.toFreeMFrom_return {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (state : M.State) (termination : M.TerminatesFrom state) (value : β) (hview : M.view state = Sum.inl value) :
          M.toFreeMFrom state termination = FreeM.pure value
          theorem PFunctor.DynSystem.DynComputation.toFreeMFrom_query {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (state : M.State) (termination : M.TerminatesFrom state) (position : p.A) (next : p.B position → M.State) (hview : M.view state = Sum.inr ⟨position, next⟩) :
          M.toFreeMFrom state termination = FreeM.liftBind position fun (direction : p.B position) => M.toFreeMFrom (next direction) ⋯
          theorem PFunctor.DynSystem.DynComputation.toFreeMFrom_proof_irrel {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (state : M.State) (h₁ h₂ : M.TerminatesFrom state) :
          M.toFreeMFrom state h₁ = M.toFreeMFrom state h₂

          Extracted programs do not depend on the particular accessibility proof.

          theorem PFunctor.DynSystem.DynComputation.toFreeM_proof_irrel {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (h₁ h₂ : ∀ (input : α), M.TerminatesFrom (M.init input)) :
          M.toFreeM h₁ = M.toFreeM h₂

          Extracted program families do not depend on the pointwise accessibility proof.

          Exact well-founded semantics #

          theorem PFunctor.DynSystem.DynComputation.behavior_eq_toResumption_toFreeMFrom {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (state : M.State) (termination : M.TerminatesFrom state) :
          M.toDynSystem.behavior state = (M.toFreeMFrom state termination).toResumption

          Extraction preserves the computation's exact state behavior. The proof uses the established M-type equality principle but performs no branchwise witness choice.

          theorem PFunctor.DynSystem.DynComputation.denote_eq_toResumption_toFreeM {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (termination : ∀ (input : α), M.TerminatesFrom (M.init input)) (input : α) :
          M.denote input = (M.toFreeM termination input).toResumption

          Input-level specialization of exact extraction.

          theorem PFunctor.DynSystem.DynComputation.ResolvesIn.terminatesFrom {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} {M : DynComputation p α β} {k : ℕ} {state : M.State} (h : M.ResolvesIn k state) :

          A uniform query bound implies qualitative well-founded termination.

          theorem PFunctor.DynSystem.DynComputation.TerminatesFrom.of_view_eq {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} {M : DynComputation p α β} {source target : M.State} (h : M.TerminatesFrom target) (hview : M.view source = M.view target) :

          A state with the same one-step view as a terminating state terminates. This is useful when a stateful construction changes only the hidden owner of an otherwise identical residual query.

          theorem PFunctor.DynSystem.DynComputation.terminatesFrom_of_behavior_eq_toResumption {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (program : p.FreeM β) (state : M.State) (hsem : M.toDynSystem.behavior state = program.toResumption) :

          A well-founded FreeM presentation proves accessibility of the state that realizes it. This direction is structural in the supplied FreeM; it does not assume or manufacture a uniform natural-number depth bound.

          Accessibility is exactly existence of a well-founded free-program presentation of the state's coinductive behavior.

          The hidden-state accessibility predicate is exactly well-foundedness of the state-free resumption semantics. This removes the presentation witness from terminatesFrom_iff_exists_behavior_eq_toResumption.

          theorem PFunctor.DynSystem.DynComputation.terminatesFrom_init_iff_wellFounded_denote {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) :
          (∀ (input : α), M.TerminatesFrom (M.init input)) ↔ ∀ (input : α), (M.denote input).WellFounded

          Initial-state specialization of terminatesFrom_iff_wellFounded_behavior.

          theorem PFunctor.DynSystem.DynComputation.resolvesIn_iff_isTotalRollBound_toFreeMFrom {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (k : ℕ) (state : M.State) (termination : M.TerminatesFrom state) :
          M.ResolvesIn k state ↔ (M.toFreeMFrom state termination).IsTotalRollBound k

          Exact quantitative characterization of an extracted qualitative program. A qualitative proof alone need not supply any such k.

          theorem PFunctor.DynSystem.DynComputation.implements_toFreeM {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) (termination : ∀ (input : α), M.TerminatesFrom (M.init input)) :
          M.Implements (M.toFreeM termination)

          The extracted initial program family is implemented exactly.

          theorem PFunctor.DynSystem.DynComputation.terminatesFrom_init_iff_exists_implements {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} (M : DynComputation p α β) :
          (∀ (input : α), M.TerminatesFrom (M.init input)) ↔ ∃ (program : α → p.FreeM β), M.Implements program

          A computation terminates from every entry state exactly when it qualitatively implements some well-founded free-program family.

          Qualitative sequential composition #

          theorem PFunctor.DynSystem.DynComputation.TerminatesFrom.seqComp_inr {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} {γ : Type uγ} {M₁ : DynComputation p α β} {M₂ : DynComputation p β γ} {state₂ : M₂.State} (h₂ : M₂.TerminatesFrom state₂) :
          (M₁.seqComp M₂).TerminatesFrom (Sum.inr state₂)

          A terminating second-phase state remains terminating when embedded in the right phase of sequential composition.

          theorem PFunctor.DynSystem.DynComputation.TerminatesFrom.seqComp_inl {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} {γ : Type uγ} {M₁ : DynComputation p α β} {M₂ : DynComputation p β γ} {state₁ : M₁.State} (h₁ : M₁.TerminatesFrom state₁) (h₂ : ∀ (value : β), M₂.TerminatesFrom (M₂.init value)) :
          (M₁.seqComp M₂).TerminatesFrom (Sum.inl state₁)

          Sequential composition terminates in phase one when phase one terminates and the second computation terminates from every possible handoff value.

          theorem PFunctor.DynSystem.DynComputation.TerminatesFrom.seqComp_init {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} {γ : Type uγ} {M₁ : DynComputation p α β} {M₂ : DynComputation p β γ} (h₁ : ∀ (input : α), M₁.TerminatesFrom (M₁.init input)) (h₂ : ∀ (value : β), M₂.TerminatesFrom (M₂.init value)) (input : α) :
          (M₁.seqComp M₂).TerminatesFrom ((M₁.seqComp M₂).init input)

          Input-level qualitative termination composes through sequential handoff.

          theorem PFunctor.DynSystem.DynComputation.toFreeMFrom_seqComp_inr {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} {γ : Type uγ} (M₁ : DynComputation p α β) (M₂ : DynComputation p β γ) (state₂ : M₂.State) (h₂ : M₂.TerminatesFrom state₂) :
          (M₁.seqComp M₂).toFreeMFrom (Sum.inr state₂) ⋯ = M₂.toFreeMFrom state₂ h₂

          Extraction from a right-phase state is exactly extraction from the second computation.

          theorem PFunctor.DynSystem.DynComputation.toFreeMFrom_seqComp_inl {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} {γ : Type uγ} (M₁ : DynComputation p α β) (M₂ : DynComputation p β γ) (state₁ : M₁.State) (h₁ : M₁.TerminatesFrom state₁) (h₂ : ∀ (value : β), M₂.TerminatesFrom (M₂.init value)) :
          (M₁.seqComp M₂).toFreeMFrom (Sum.inl state₁) ⋯ = (M₁.toFreeMFrom state₁ h₁).bind fun (value : β) => M₂.toFreeMFrom (M₂.init value) ⋯

          Extraction from a terminating phase-one state is literal free-monad bind of the two extracted phases.

          theorem PFunctor.DynSystem.DynComputation.toFreeM_seqComp {p : PFunctor.{uA, uB}} {α : Type uα} {β : Type uβ} {γ : Type uγ} (M₁ : DynComputation p α β) (M₂ : DynComputation p β γ) (h₁ : ∀ (input : α), M₁.TerminatesFrom (M₁.init input)) (h₂ : ∀ (value : β), M₂.TerminatesFrom (M₂.init value)) :
          (M₁.seqComp M₂).toFreeM ⋯ = fun (input : α) => (M₁.toFreeM h₁ input).bind (M₂.toFreeM h₂)

          Program-family extraction commutes exactly with sequential composition.