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 #
The strict child relation generated by one visible query. Terminal states have no children.
Equations
Instances For
Every branch from state contains only finitely many visible queries.
Unlike ResolvesIn, different branches need not share a natural-number
bound.
Equations
- M.TerminatesFrom state = Acc M.QueryChild state
Instances For
Well-founded-program extraction #
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
Extract the well-founded program family represented from every input-selected initial state.
Equations
- M.toFreeM termination input = M.toFreeMFrom (M.init input) ⋯
Instances For
Extracted programs do not depend on the particular accessibility proof.
Extracted program families do not depend on the pointwise accessibility proof.
Exact well-founded semantics #
Extraction preserves the computation's exact state behavior. The proof uses the established M-type equality principle but performs no branchwise witness choice.
Input-level specialization of exact extraction.
A uniform query bound implies qualitative well-founded termination.
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.
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.
Initial-state specialization of
terminatesFrom_iff_wellFounded_behavior.
Exact quantitative characterization of an extracted qualitative
program. A qualitative proof alone need not supply any such k.
The extracted initial program family is implemented exactly.
A computation terminates from every entry state exactly when it qualitatively implements some well-founded free-program family.
Qualitative sequential composition #
A terminating second-phase state remains terminating when embedded in the right phase of sequential composition.
Sequential composition terminates in phase one when phase one terminates and the second computation terminates from every possible handoff value.
Input-level qualitative termination composes through sequential handoff.
Extraction from a right-phase state is exactly extraction from the second computation.
Extraction from a terminating phase-one state is literal free-monad bind of the two extracted phases.
Program-family extraction commutes exactly with sequential composition.