Iteration Ontology

FLOW ALGEBRA
ITERATION ONTOLOGY
Kireth Semantic Library — Computational Mathematical Entities
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/computational-mathematical-entities/iteration-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Status: Proposed mathematical formalisation; source page wording not independently verified.
Version: 1.0
Date: 2026-10-14

1. ONTOLOGY IDENTITY
ontology_id: kireth:computational-mathematical-entities:iteration
entity_type: Iteration
parent: ComputationalMathematicalEntity
related: IterativeMethod, Algorithm, State, UpdateRule, ConvergenceCriterion, ApproximateSolution, FixedPoint

2. DEFINITIONS
Iteration: one application of a specified update rule to a current computational state.
IterativeProcess: a sequence of states generated by repeated application of an update rule.
IterationIndex: non-negative integer k identifying a state or update.
State: typed value x_k in a state space X.
UpdateRule: map F_k:X -> X (or a partial map with explicit domain), producing x_(k+1)=F_k(x_k).
TerminationCondition: predicate evaluated on a specified state and execution context.

3. TYPED ENTITIES
StateSpace<X>
InitialState<X>
IterationIndex<N0>
UpdateRule<X,X>
IterationStep<X>
StateSequence<Sequence<X>>
Residual<NonNegativeReal>
ErrorEstimate<NonNegativeReal>
Tolerance<NonNegativeReal>
IterationBudget<NonNegativeInteger>
TerminationStatus<Running|Converged|BudgetExceeded|InvalidState|Stagnated|Diverged>

4. CORE FLOW ALGEBRA
flow IterationProcess<X>:
  input: x0:X, update:(X,N0)->X, stop:(X,N0)->Boolean, max_steps:N0
  require: x0 in domain(update at k=0) when max_steps > 0
  state: x := x0; k := 0
  while k < max_steps and not stop(x,k):
    require: (x,k) in domain(update)
    next := update(x,k)
    require: next in X
    x := next
    k := k + 1
  output: (x,k,stop(x,k) ? ConvergedCriterionMet : BudgetExceeded)
  note: criterion met does not alone establish mathematical convergence

Recurrence: x_(k+1) = F_k(x_k), k >= 0.
Stationary rule: F_k = F for every k.
Fixed point: x* = F(x*).
Residual example: r_k = ||F(x_k)-x_k||, where norm and domain are defined.
Step difference: d_k = ||x_(k+1)-x_k||.

5. RELATIONSHIPS
Iteration --applies--> UpdateRule
Iteration --reads--> CurrentState
Iteration --produces--> NextState
Iteration --hasIndex--> IterationIndex
IterativeProcess --contains--> Iteration
IterativeProcess --generates--> StateSequence
TerminationCondition --evaluates--> State
ConvergenceCriterion --assesses--> StateSequence
IterationBudget --limits--> IterativeProcess

6. MATHEMATICAL INVARIANTS
I1: k is an integer and 0 <= k <= max_steps.
I2: Every generated x_k belongs to the declared state space X.
I3: A valid transition respects the update rule's domain and codomain.
I4: A loop invariant P is preserved if P(x0) and P(x)->P(F_k(x)) for every applicable step.
I5: Deterministic update and fixed initial state imply a unique generated sequence, assuming defined execution.
I6: A small residual or step difference does not by itself prove proximity to a true solution.

7. CONVERGENCE AND TERMINATION
Convergence: x_k -> x* under a specified topology or metric.
Sufficient example: if X is a complete metric space and F:X->X is a contraction, then stationary iteration x_(k+1)=F(x_k) converges to the unique fixed point.
Stopping criteria may combine absolute tolerance, relative tolerance, residual bounds, stagnation detection and iteration budget.
Finite termination and asymptotic convergence are distinct properties.

8. EXECUTABLE INFERENCE RULES
R1: IF x_(k+1)=F_k(x_k) AND all type/domain checks pass THEN classify transition as ValidIterationStep.
R2: IF x*=F(x*) THEN classify x* as FixedPointOf(F).
R3: IF a proven convergence theorem's hypotheses hold THEN infer its stated convergence conclusion, recording the theorem and assumptions.
R4: IF stop(x_k,k)=true THEN mark CriterionMet; do not infer ExactSolution without a separate proof.
R5: IF k=max_steps AND stop=false THEN mark BudgetExceeded.
R6: IF an update violates a type, domain or invariant THEN mark InvalidState and stop.

9. SEMANTIC DISTINCTIONS
Iteration != Recursion: iteration uses repeated steps; recursion defines computation via self-reference, though implementations can be equivalent.
Iteration != Convergence: a sequence can oscillate or diverge.
Iteration != Optimisation: updates need not optimise an objective.
Iteration != Approximation: some iterations are exact symbolic transformations.
StoppingCriterion != ConvergenceProof.
FixedPoint != UniqueFixedPoint unless uniqueness is established.

10. VALIDATION
validate_state_types: required
validate_update_domain: required
validate_iteration_index: k >= 0
validate_budget: max_steps >= 0
validate_invariants: each step
validate_numeric_finiteness: when numeric model requires finite values
validate_termination_status: required
validate_proof_claims: convergence and correctness claims require explicit assumptions/evidence

11. CONFIDENCE AND PROVENANCE
CONFIDENCE:
  mathematical_definition: high (standard mathematical definitions)
  source_page_alignment: unverified
  theorem_application: conditional on hypotheses
PROVENANCE:
  source_url: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/computational-mathematical-entities/iteration-ontology.html
  formalisation_status: proposed

12. SEMANTIC_EQUIVALENCE
IterationStep ~= UpdateStep [when one application of update is meant]
IterativeProcess ~= RepeatedUpdateProcess [context-dependent]
Iteration != LoopBody [loop body may contain multiple update steps]

13. FLOW_HASH
FLOW_HASH:
  algorithm: SHA-256
  canonicalisation: UTF-8; Unicode NFC; LF newlines; stable field ordering; exclude FLOW_HASH digest field
  digest: compute on deployment; not precomputed

14. UPDATE_MODEL
UPDATE_MODEL:
  version: 1.0
  update_policy: revise on mathematical correction or ontology schema change
  compatibility: preserve stable entity identifiers where possible

15. AI_CONSUMPTION
AI_CONSUMPTION:
  parse_mode: typed_flow_algebra
  infer_only_with_proven_assumptions: true
  distinguish_empirical_stop_from_proven_convergence: true
  expose_provenance_and_confidence: true
  reject_invalid_transitions: true
  avoid_unjustified_exactness_claims: true

END FLOW ALGEBRA