Mathematical Algorithm Ontology

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

1. ENTITY DECLARATION
entity MathematicalAlgorithm : ComputationalMathematicalEntity
  fields:
    identifier: URI
    problem: ComputationalProblem
    input_domain: Set
    output_domain: Set
    precondition: Predicate
    postcondition: Predicate
    state_space: Set
    initialisation: State -> State
    transition: State -> State
    termination_condition: State -> Boolean
    result_extractor: State -> Output
    correctness_claim: Proposition?
    complexity_bound: ComplexityBound?
    numerical_tolerance: RealNonnegative?
    implementation: Program?
    provenance: SourceReference

2. TYPED ENTITIES
ComputationalProblem; ProblemInstance; Algorithm; Input; Output; State;
Operation; Instruction; Loop; Invariant; TerminationCondition;
Precondition; Postcondition; ProofCertificate; ComplexityBound;
ExactAlgorithm; ApproximationAlgorithm; DeterministicAlgorithm;
RandomisedAlgorithm; IterativeAlgorithm; RecursiveAlgorithm.

3. FORMAL SEMANTICS
Given input x in D and a state s0 = initialise(x), an algorithm generates
s_(k+1) = T(s_k) while not halt(s_k).
If halt(s_N), output y = extract(s_N).
Partial correctness: {P} A {Q} means if A terminates from a state satisfying P,
its final state satisfies Q.
Total correctness: partial correctness AND termination for every admissible input.
For a deterministic total algorithm, A : D -> R is a function.
For randomised algorithms, output may be a random variable conditional on input.

4. INVARIANTS AND AXIOMS
A1 TYPE_SAFETY: every operation receives inputs of its declared type.
A2 PRECONDITION: execution requires P(x) or returns a defined precondition failure.
A3 TRANSITION: each nonterminal step follows an admissible transition rule.
A4 LOOP_INVARIANT: I(s0) and I(s) AND not halt(s) imply I(T(s)).
A5 POSTCONDITION: halt(s) AND invariant(s) imply Q(x,extract(s)) when proven.
A6 TERMINATION: a well-founded ranking measure decreases on every nonterminal step when such a proof is supplied.
A7 CORRECTNESS_STATUS: tested, asserted and formally proved are distinct statuses.
A8 APPROXIMATION: an approximate answer is not relabelled exact without a proof.

5. RELATIONSHIPS
MathematicalAlgorithm --SOLVES--> ComputationalProblem
MathematicalAlgorithm --ACCEPTS--> Input
MathematicalAlgorithm --PRODUCES--> Output
MathematicalAlgorithm --USES--> MathematicalOperation
MathematicalAlgorithm --HAS_PRECONDITION--> Predicate
MathematicalAlgorithm --HAS_POSTCONDITION--> Predicate
MathematicalAlgorithm --MAINTAINS--> Invariant
MathematicalAlgorithm --TERMINATES_WHEN--> TerminationCondition
MathematicalAlgorithm --HAS_COMPLEXITY--> ComplexityBound
MathematicalAlgorithm --VERIFIED_BY--> ProofCertificate
IterativeAlgorithm --SPECIALISES--> MathematicalAlgorithm
RecursiveAlgorithm --SPECIALISES--> MathematicalAlgorithm
ApproximationAlgorithm --SPECIALISES--> MathematicalAlgorithm

6. EXECUTABLE INFERENCE FLOWS (PSEUDOCODE)
flow CHECK_TYPES(A,x):
  require x in A.input_domain
  check all transitions are type-preserving
  return PASS or FAIL

flow VERIFY_PARTIAL_CORRECTNESS(A,P,Q,I):
  require P => I(initialise(x))
  require forall s: I(s) and not halt(s) => I(T(s))
  require forall s: I(s) and halt(s) => Q(x,extract(s))
  return PROVED only if all obligations are discharged

flow VERIFY_TERMINATION(A,rank):
  require rank maps reachable nonterminal states to a well-founded order
  require forall reachable nonterminal s: rank(T(s)) < rank(s)
  return PROVED only if both obligations are discharged

flow CLASSIFY_RESULT(A,proofs):
  if proofs.partial_correctness and proofs.termination: return TOTAL_CORRECTNESS_PROVED
  if proofs.partial_correctness: return PARTIAL_CORRECTNESS_PROVED
  return UNVERIFIED

flow CHECK_APPROXIMATION(A,x,y,epsilon):
  require epsilon >= 0
  require a defined metric d on outputs
  require reference solution y_star or certified error bound
  accept only if d(y,y_star) <= epsilon or certified_bound <= epsilon

7. COMPUTATIONAL COMPLEXITY
Time T_A(n): operation count under an explicitly defined cost model.
Space S_A(n): peak additional storage under an explicitly defined cost model.
O(g(n)): eventual upper bound; Omega(g(n)): eventual lower bound;
Theta(g(n)): matching asymptotic upper and lower bounds.
Worst-case, average-case and expected complexity are separate measures.
A claimed bound requires assumptions on input size and computational model.

8. EXAMPLE: EUCLIDEAN GCD
input: nonnegative integers a,b, not both zero
while b != 0:
  (a,b) = (b,a mod b)
output: a
invariant: gcd(a,b) remains unchanged
termination: nonnegative second operand strictly decreases while positive
postcondition: result = gcd(original_a,original_b)
complexity: O(log(max(original_a,original_b))) arithmetic steps in the standard unit-cost model

9. SEMANTIC DISTINCTIONS
Algorithm != implementation: an abstract procedure differs from its program.
Algorithm != heuristic: a heuristic need not guarantee correctness or optimality.
Correctness != empirical success: tests cannot establish universal validity alone.
Termination != convergence: a sequence may converge without a finite stopping point.
Exact solution != approximate solution: preserve precision and certification metadata.
Deterministic != randomised: probabilistic outputs require probability semantics.

10. VALIDATION
V1 All required identifiers and types resolve.
V2 Preconditions and postconditions are explicit.
V3 Loop invariants and termination claims are accompanied by proof obligations.
V4 Complexity claims state their cost model and input-size measure.
V5 Numerical errors and tolerance conventions are defined when relevant.
V6 Contradictory correctness claims are flagged.
V7 Source provenance and revision history are retained.

11. CONFIDENCE AND SEMANTIC EQUIVALENCE
CONFIDENCE: {level: proposed, evidence: mathematical_definition,
             source_page_verified: false, proof_status: per_claim}
SEMANTIC_EQUIVALENCE:
  'mathematical procedure' ~= 'mathematical algorithm' only where finite,
  effective, unambiguous operational steps and input/output semantics match.
  'computer program' != 'algorithm' (implementation versus abstraction).

12. FLOW HASH AND UPDATE MODEL
FLOW_HASH := SHA256(canonical_UTF8(ontology_payload_excluding_FLOW_HASH))
Canonicalisation requires stable field order, Unicode NFC and LF line endings.
Hash value must be computed on the final published payload; no hash is fabricated here.
UPDATE_MODEL:
  preserve identifier; increment version on semantic changes;
  record changed axioms, affected relationships and proof invalidations;
  recompute FLOW_HASH after publication changes.

13. AI CONSUMPTION
AI_CONSUMPTION:
  purpose: typed mathematical retrieval, reasoning and verification support
  input: ontology entities, problem constraints, proof obligations, provenance
  output: candidate algorithm, preconditions, claims, validation results
  safeguards:
    - distinguish proven from unverified statements
    - avoid inventing complexity or correctness certificates
    - require type checks before composing algorithms
    - expose unresolved obligations and approximation errors
    - maintain traceability to definitions and source material

END FLOW ALGEBRA