Computational Theory Ontology

AI SEARCH

FLOW ALGEBRA — COMPUTATIONAL THEORY ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/foundations-of-computing/computational-theory-ontology.html

FLOW COMPUTATIONAL_THEORY_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Foundations of Computing"
    ONTOLOGY = "Computational Theory Ontology"
    PURPOSE = "Formalise the mathematical and logical foundations of computation, including automata, formal languages, computability, decidability, complexity and algorithmic reasoning."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    COMPUTATION
    COMPUTATIONAL_MODEL
    ABSTRACT_MACHINE
    TURING_MACHINE
    AUTOMATON
    FINITE_AUTOMATON
    DETERMINISTIC_AUTOMATON
    NONDETERMINISTIC_AUTOMATON
    PUSHDOWN_AUTOMATON
    LINEAR_BOUNDED_AUTOMATON
    STATE
    INITIAL_STATE
    ACCEPTING_STATE
    TRANSITION
    TRANSITION_FUNCTION
    SYMBOL
    ALPHABET
    STRING
    WORD
    LANGUAGE
    FORMAL_LANGUAGE
    GRAMMAR
    PRODUCTION_RULE
    REGULAR_LANGUAGE
    CONTEXT_FREE_LANGUAGE
    CONTEXT_SENSITIVE_LANGUAGE
    RECURSIVELY_ENUMERABLE_LANGUAGE
    PROBLEM
    PROBLEM_INSTANCE
    DECISION_PROBLEM
    FUNCTION_PROBLEM
    COMPUTABLE_FUNCTION
    PARTIAL_FUNCTION
    ALGORITHM
    PROCEDURE
    INPUT
    OUTPUT
    HALTING_STATE
    DECIDABILITY
    RECOGNISABILITY
    REDUCTION
    MAPPING_REDUCTION
    ORACLE
    COMPLEXITY
    TIME_COMPLEXITY
    SPACE_COMPLEXITY
    COMPLEXITY_CLASS
    P_CLASS
    NP_CLASS
    NP_HARD
    NP_COMPLETE
    EXPONENTIAL_TIME
    PROOF
    THEOREM
    LEMMA
    COUNTEREXAMPLE
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    CONTAINS
    HAS_STATE
    HAS_INITIAL_STATE
    HAS_ACCEPTING_STATE
    HAS_TRANSITION
    TRANSITIONS_TO
    READS_SYMBOL
    WRITES_SYMBOL
    MOVES_TO
    ACCEPTS
    REJECTS
    RECOGNISES
    DECIDES
    GENERATES
    DERIVES
    COMPUTES
    HALTS_ON
    DOES_NOT_HALT_ON
    MAPS_INPUT_TO_OUTPUT
    REDUCES_TO
    EQUIVALENT_TO
    SIMULATES
    HAS_LANGUAGE
    HAS_GRAMMAR
    HAS_COMPLEXITY
    BELONGS_TO_CLASS
    BOUNDED_BY
    PROVES
    DISPROVES
    IMPLIES
    DEPENDS_ON
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    FORMAL_PROBLEM_DEFINITIONS
    MACHINE_DEFINITIONS
    STATE_SETS
    TRANSITION_FUNCTIONS
    ALPHABETS
    INPUT_STRINGS
    FORMAL_LANGUAGES
    GRAMMARS
    ALGORITHMS
    COMPUTABLE_FUNCTIONS
    REDUCTIONS
    RESOURCE_BOUNDS
    COMPLEXITY_DEFINITIONS
    FORMAL_PROOFS
    COUNTEREXAMPLES
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_SYMBOLS
    NORMALISE_FORMAL_NOTATION
    NORMALISE_MACHINE_DEFINITIONS
    NORMALISE_LANGUAGE_DEFINITIONS
    NORMALISE_GRAMMAR_RULES
    NORMALISE_COMPLEXITY_NOTATION
    NORMALISE_REDUCTION_DIRECTION
    RESOLVE_EQUIVALENT_FORMALISMS
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_FORMAL_DEFINITIONS
    PRESERVE_PROVENANCE
  }

  PROCESS ABSTRACT_COMPUTATION {
    INPUT
      -> INITIAL_MACHINE_STATE
      -> APPLY_TRANSITION_RULE
      -> NEXT_MACHINE_STATE
      -> HALTING_CHECK
      -> ACCEPT_REJECT_OR_CONTINUE
  }

  PROCESS AUTOMATA_REASONING {
    AUTOMATON + INPUT_STRING
      -> INITIAL_STATE

    INITIAL_STATE
      -> TRANSITION_SEQUENCE

    TRANSITION_SEQUENCE
      -> FINAL_STATE_OR_NONTERMINATION

    FINAL_STATE_OR_NONTERMINATION
      -> ACCEPTANCE_RESULT
  }

  PROCESS FORMAL_LANGUAGE_REASONING {
    ALPHABET + FORMATION_RULES
      -> STRINGS

    GRAMMAR
      -> DERIVATION

    DERIVATION
      -> GENERATED_STRING

    GENERATED_STRINGS
      -> LANGUAGE

    AUTOMATON + LANGUAGE
      -> RECOGNITION_RELATION
  }

  PROCESS COMPUTABILITY_REASONING {
    PROBLEM
      -> FORMALISE_AS_LANGUAGE_OR_FUNCTION

    FORMALISED_PROBLEM
      -> CANDIDATE_COMPUTATIONAL_MODEL

    CANDIDATE_COMPUTATIONAL_MODEL
      -> HALTING_ANALYSIS
      -> CORRECTNESS_ANALYSIS

    HALTING_ANALYSIS + CORRECTNESS_ANALYSIS
      -> COMPUTABILITY_CLASSIFICATION
  }

  PROCESS DECIDABILITY_REASONING {
    DECISION_PROBLEM
      -> DECIDER_SEARCH_OR_PROOF

    DECIDER_SEARCH_OR_PROOF
      -> DECIDER_FOUND
      OR -> REDUCTION_FROM_UNDECIDABLE_PROBLEM
      OR -> UNRESOLVED

    DECIDER_FOUND
      -> DECIDABLE

    VALID_UNDECIDABILITY_REDUCTION
      -> UNDECIDABLE
  }

  PROCESS REDUCTION_REASONING {
    PROBLEM_A
      -> TRANSFORMATION_FUNCTION

    TRANSFORMATION_FUNCTION
      -> INSTANCE_OF_PROBLEM_B

    SOLUTION_TO_B
      -> INTERPRETATION_FOR_A

    VALID_TRANSFORMATION + VALID_INTERPRETATION
      -> A REDUCES_TO B
  }

  PROCESS COMPLEXITY_REASONING {
    ALGORITHM + INPUT_SIZE
      -> OPERATION_OR_RESOURCE_COUNT

    OPERATION_OR_RESOURCE_COUNT
      -> ASYMPTOTIC_BOUND

    ASYMPTOTIC_BOUND
      -> TIME_OR_SPACE_COMPLEXITY

    TIME_OR_SPACE_COMPLEXITY
      -> COMPLEXITY_CLASS_RELATION
  }

  PROCESS PROOF_REASONING {
    PREMISES + AXIOMS + DEFINITIONS
      -> INFERENCE_STEPS

    INFERENCE_STEPS
      -> CONCLUSION

    CONCLUSION
      -> PROOF_VALIDATION

    PROOF_VALIDATION
      -> PROVED_OR_INVALID
  }

  RULES {
    IF MACHINE_ACCEPTS_STRING
    THEN REQUIRE {
      MACHINE_DEFINITION
      INPUT_STRING
      VALID_COMPUTATION_PATH
      ACCEPTING_STATE
    }

    IF MACHINE_DECIDES_LANGUAGE
    THEN REQUIRE {
      ACCEPTS_ALL_MEMBERS
      REJECTS_ALL_NONMEMBERS
      HALTS_ON_ALL_INPUTS
    }

    IF MACHINE_RECOGNISES_LANGUAGE
    THEN DO_NOT_REQUIRE_HALTING_ON_NONMEMBERS

    IF PROBLEM_A REDUCES_TO PROBLEM_B
    THEN PRESERVE_REDUCTION_DIRECTION

    IF UNDECIDABLE_PROBLEM_A REDUCES_TO PROBLEM_B
    VIA_VALID_REDUCTION
    THEN B_IS_AT_LEAST_AS_HARD_UNDER_REDUCTION_CONTEXT

    IF COMPLEXITY_IS_STATED
    THEN REQUIRE {
      INPUT_SIZE_MEASURE
      COMPUTATIONAL_MODEL
      RESOURCE_TYPE
      BOUND_TYPE
    }

    IF TWO_MACHINES_ACCEPT_SAME_TESTED_STRINGS
    THEN DO_NOT_ASSERT_LANGUAGE_EQUIVALENCE_WITHOUT_PROOF

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND FORMAL_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        DEFINITION_COMPLETENESS,
        FORMAL_PROOF_VALIDITY,
        MACHINE_SPECIFICATION,
        REDUCTION_VALIDITY,
        COMPLEXITY_MODEL_CLARITY,
        COUNTEREXAMPLE_CHECKING,
        CONSISTENCY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF FORMAL_PROOF_IS_VALID
    THEN INCREASE CONFIDENCE_SCORE

    IF CLAIM_IS_SUPPORTED_ONLY_BY_FINITE_TESTING
    THEN LIMIT_GENERALISATION_CONFIDENCE

    IF REDUCTION_DIRECTION_IS_AMBIGUOUS
    THEN REDUCE CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        FORMAL_DEFINITION,
        MACHINE_MODEL,
        LANGUAGE_OR_FUNCTION,
        RESOURCE_CONTEXT
      )

    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B)
    THEN A SEMANTICALLY_EQUIVALENT_TO B

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    RECOGNISABLE != NECESSARILY_DECIDABLE
    COMPUTABLE != NECESSARILY_EFFICIENT
    DECIDABILITY != TRACTABILITY
    ACCEPTANCE != HALTING_ON_ALL_INPUTS
    FINITE_TESTING != FORMAL_PROOF
    REDUCTION_DIRECTION_MUST_NOT_BE_REVERSED
    LANGUAGE_EQUIVALENCE_REQUIRES_GENERAL_ARGUMENT
    COMPLEXITY_DEPENDS_ON_INPUT_SIZE_AND_MODEL
    UPPER_BOUND != TIGHT_BOUND
    WORST_CASE != AVERAGE_CASE
    NONDETERMINISM != RANDOMNESS
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_MACHINE_DEFINITIONS
    CHECK_STATE_SETS
    CHECK_TRANSITION_FUNCTIONS
    CHECK_LANGUAGE_DEFINITIONS
    CHECK_GRAMMAR_RULES
    CHECK_ACCEPTANCE_CONDITIONS
    CHECK_HALTING_CONDITIONS
    CHECK_REDUCTION_DIRECTION
    CHECK_REDUCTION_VALIDITY
    CHECK_COMPLEXITY_CONTEXT
    CHECK_PROOF_STRUCTURE
    CHECK_COUNTEREXAMPLES
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_THEORY_ENTITIES
    MACHINE_RELATIONS
    STATE_TRANSITION_GRAPHS
    LANGUAGE_RELATIONS
    GRAMMAR_RELATIONS
    ACCEPTANCE_RESULTS
    COMPUTABILITY_CLASSIFICATIONS
    DECIDABILITY_RESULTS
    REDUCTION_RELATIONS
    COMPLEXITY_RELATIONS
    PROOF_RELATIONS
    COUNTEREXAMPLE_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON NEW_FORMAL_RESULT {
      NORMALISE
      ENTITY_RESOLUTION
      UPDATE_THEOREM_RELATIONS
      UPDATE_REDUCTIONS
      UPDATE_COMPLEXITY_RELATIONS
      RECOMPUTE_DEPENDENT_INFERENCES
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON NEW_PROOF_OR_COUNTEREXAMPLE {
      LINK_EVIDENCE
      REASSESS_CLAIMS
      REASSESS_EQUIVALENCE
      REASSESS_CLASSIFICATIONS
      UPDATE_CONFIDENCE
      RECORD_PROVENANCE
    }

    ON ONTOLOGY_REVISION {
      REMAP_TERMS
      CHECK_SEMANTIC_EQUIVALENCE
      IDENTIFY_DEPRECATED_TERMS
      MIGRATE_RELATIONSHIPS
      PRESERVE_PRIOR_VERSION_REFERENCES
    }
  }

  FLOW_HASH {
    HASH_INPUT =
      CANONICALISE(
        ENTITY_TYPES,
        RELATIONSHIPS,
        RULES,
        CONFIDENCE,
        SEMANTIC_EQUIVALENCE,
        REASONING_CONSTRAINTS,
        UPDATE_MODEL
      )

    FLOW_HASH = SHA256(HASH_INPUT)
  }

  AI_CONSUMPTION {
    INDEX {
      ONTOLOGY
      ENTITY_TYPES
      RELATIONSHIPS
      RULES
      OUTPUTS
    }

    RETRIEVE {
      BY_MACHINE
      BY_AUTOMATON
      BY_LANGUAGE
      BY_GRAMMAR
      BY_PROBLEM
      BY_FUNCTION
      BY_DECIDABILITY
      BY_REDUCTION
      BY_COMPLEXITY
      BY_PROOF
      BY_CONFIDENCE
    }

    REASON {
      APPLY_FORMAL_RULES
      TRACE_MACHINE_COMPUTATION
      TRACE_LANGUAGE_DERIVATION
      ANALYSE_ACCEPTANCE
      ANALYSE_HALTING
      ANALYSE_COMPUTABILITY
      ANALYSE_DECIDABILITY
      TRACE_REDUCTIONS
      ANALYSE_COMPLEXITY
      VALIDATE_PROOFS
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_RECOGNISABILITY_FROM_DECIDABILITY
      DISTINGUISH_COMPUTABILITY_FROM_COMPLEXITY
      PRESERVE_REDUCTION_DIRECTION
      PRESERVE_COMPUTATIONAL_MODEL_CONTEXT
      DISTINGUISH_TESTING_FROM_PROOF
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_THEORETICAL_INFERENCE
    }
  }

  TERMINAL {
    RESULT =
      VALIDATED(
        SEMANTICALLY_NORMALISED(
          EVIDENCE_LINKED(
            CONFIDENCE_AWARE(
              COMPUTATIONAL_THEORY_KNOWLEDGE
            )
          )
        )
      )
  }
}

END FLOW