Computational Model Ontology

AI SEARCH

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

FLOW COMPUTATIONAL_MODEL_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Foundations of Computing"
    ONTOLOGY = "Computational Model Ontology"
    PURPOSE = "Formalise abstract and concrete models of computation, their states, transition rules, resources, inputs, outputs and semantic relationships."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    COMPUTATIONAL_MODEL
    ABSTRACT_MACHINE
    TURING_MACHINE
    FINITE_STATE_MACHINE
    AUTOMATON
    PUSHDOWN_AUTOMATON
    REGISTER_MACHINE
    RAM_MACHINE
    LAMBDA_CALCULUS
    RECURSIVE_FUNCTION_MODEL
    CIRCUIT_MODEL
    BOOLEAN_CIRCUIT
    CELLULAR_AUTOMATON
    PARALLEL_MODEL
    DISTRIBUTED_MODEL
    PROBABILISTIC_MODEL
    QUANTUM_COMPUTATIONAL_MODEL
    ANALOG_COMPUTATIONAL_MODEL
    HYBRID_COMPUTATIONAL_MODEL
    STATE
    INITIAL_STATE
    FINAL_STATE
    ACCEPTING_STATE
    CONFIGURATION
    TRANSITION
    TRANSITION_RULE
    TRANSITION_FUNCTION
    INPUT
    OUTPUT
    SYMBOL
    ALPHABET
    STRING
    MEMORY
    TAPE
    STACK
    REGISTER
    CELL
    PROCESSOR
    CHANNEL
    MESSAGE
    FUNCTION
    COMPUTABLE_FUNCTION
    PROGRAM
    ALGORITHM
    OPERATION
    INSTRUCTION
    RESOURCE
    TIME_RESOURCE
    SPACE_RESOURCE
    RANDOMNESS_RESOURCE
    COMPUTATIONAL_STEP
    EXECUTION_TRACE
    HALTING_CONDITION
    ACCEPTANCE_CONDITION
    SEMANTICS
    ENCODING
    SIMULATION
    EQUIVALENCE
    REDUCTION
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    CONTAINS
    HAS_STATE
    HAS_INITIAL_STATE
    HAS_FINAL_STATE
    HAS_ACCEPTING_STATE
    HAS_CONFIGURATION
    HAS_TRANSITION
    TRANSITIONS_TO
    HAS_TRANSITION_RULE
    READS
    WRITES
    MOVES
    PUSHES
    POPS
    SENDS
    RECEIVES
    COMPUTES
    EXECUTES
    ACCEPTS
    REJECTS
    HALTS_ON
    MAPS_INPUT_TO_OUTPUT
    USES_MEMORY
    USES_RESOURCE
    HAS_TIME_BOUND
    HAS_SPACE_BOUND
    REPRESENTS
    ENCODES
    SIMULATES
    EQUIVALENT_TO
    REDUCES_TO
    IMPLEMENTS
    DEFINES
    DEPENDS_ON
    PRECEDES
    FOLLOWS
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    MODEL_DEFINITIONS
    MACHINE_DEFINITIONS
    STATE_SETS
    TRANSITION_RULES
    INPUT_DOMAINS
    OUTPUT_DOMAINS
    MEMORY_MODELS
    RESOURCE_MODELS
    ENCODING_SCHEMES
    PROGRAMS
    ALGORITHMS
    FORMAL_SEMANTICS
    EXECUTION_TRACES
    SIMULATION_RELATIONS
    EQUIVALENCE_PROOFS
    REDUCTIONS
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_MODEL_IDENTIFIERS
    NORMALISE_FORMAL_NOTATION
    NORMALISE_STATE_REPRESENTATIONS
    NORMALISE_TRANSITION_RULES
    NORMALISE_INPUT_OUTPUT_DOMAINS
    NORMALISE_RESOURCE_MEASURES
    NORMALISE_ENCODING_SCHEMES
    RESOLVE_EQUIVALENT_MODEL_NAMES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_FORMAL_DEFINITIONS
    PRESERVE_PROVENANCE
  }

  PROCESS MODEL_EXECUTION {
    INPUT
      -> ENCODE_INPUT
      -> INITIAL_CONFIGURATION
      -> APPLY_TRANSITION_RULE
      -> NEXT_CONFIGURATION
      -> HALTING_OR_ACCEPTANCE_CHECK
      -> CONTINUE_OR_TERMINATE
      -> OUTPUT
  }

  PROCESS STATE_TRANSITION_REASONING {
    STATE(T1) + TRANSITION_RULE
      -> TRANSITION

    TRANSITION
      -> STATE(T2)

    STATE_SEQUENCE
      -> EXECUTION_TRACE

    EXECUTION_TRACE
      -> BEHAVIOUR
  }

  PROCESS FUNCTION_COMPUTATION {
    INPUT_VALUE + COMPUTATIONAL_MODEL
      -> COMPUTATION

    COMPUTATION
      -> HALTING_CHECK

    IF HALTS_WITH_OUTPUT
      -> OUTPUT_VALUE

    INPUT_VALUE -> OUTPUT_VALUE
      -> FUNCTION_MAPPING
  }

  PROCESS MODEL_SIMULATION {
    MODEL_A
      -> ENCODING_IN_MODEL_B

    ENCODING_IN_MODEL_B
      -> SIMULATION_STEPS

    SIMULATION_STEPS
      -> DECODED_RESULT

    DECODED_RESULT
      -> BEHAVIOURAL_CORRESPONDENCE_CHECK

    VALID_CORRESPONDENCE
      -> MODEL_B SIMULATES MODEL_A
  }

  PROCESS MODEL_EQUIVALENCE_REASONING {
    MODEL_A + MODEL_B
      -> COMPUTATIONAL_POWER_COMPARISON

    COMPUTATIONAL_POWER_COMPARISON
      -> BIDIRECTIONAL_SIMULATION_OR_PROOF

    BIDIRECTIONAL_SIMULATION_OR_PROOF
      -> EQUIVALENCE_CANDIDATE

    EQUIVALENCE_CANDIDATE
      -> FORMAL_VALIDATION
  }

  PROCESS RESOURCE_REASONING {
    MODEL + COMPUTATION + INPUT_SIZE
      -> RESOURCE_USAGE

    RESOURCE_USAGE
      -> TIME_USAGE
      -> SPACE_USAGE
      -> OTHER_RESOURCE_USAGE

    RESOURCE_USAGE
      -> RESOURCE_BOUND
  }

  PROCESS NONDETERMINISTIC_REASONING {
    CONFIGURATION
      -> POSSIBLE_TRANSITIONS

    POSSIBLE_TRANSITIONS
      -> COMPUTATION_BRANCHES

    COMPUTATION_BRANCHES
      -> ACCEPTANCE_EVALUATION

    EXISTS_ACCEPTING_BRANCH
      -> ACCEPT_UNDER_NONDETERMINISTIC_SEMANTICS
  }

  PROCESS PROBABILISTIC_REASONING {
    CONFIGURATION + PROBABILISTIC_TRANSITIONS
      -> DISTRIBUTION_OVER_NEXT_STATES

    STATE_DISTRIBUTIONS
      -> COMPUTATION_DISTRIBUTION

    COMPUTATION_DISTRIBUTION
      -> OUTPUT_PROBABILITY
  }

  RULES {
    IF ENTITY == COMPUTATIONAL_MODEL
    THEN REQUIRE {
      STATE_OR_CONFIGURATION_SPACE
      TRANSITION_OR_EVALUATION_RULES
      INPUT_REPRESENTATION
      OUTPUT_OR_ACCEPTANCE_SEMANTICS
    }

    IF MODEL_COMPUTES FUNCTION
    THEN REQUIRE {
      INPUT_DOMAIN
      OUTPUT_DOMAIN
      COMPUTATION_SEMANTICS
    }

    IF MODEL_A SIMULATES MODEL_B
    THEN REQUIRE {
      ENCODING
      SIMULATION_MAPPING
      RESULT_DECODING
      CORRESPONDENCE_ARGUMENT
    }

    IF MODELS_ARE_CLAIMED_EQUIVALENT
    THEN REQUIRE FORMAL_EQUIVALENCE_CRITERION

    IF TWO_MODELS_PRODUCE_SAME_RESULTS_ON_TEST_SET
    THEN DO_NOT_ASSERT_GENERAL_COMPUTATIONAL_EQUIVALENCE

    IF RESOURCE_BOUND_IS_STATED
    THEN REQUIRE {
      INPUT_SIZE_MEASURE
      RESOURCE_TYPE
      COMPUTATIONAL_MODEL
      BOUND_TYPE
    }

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND COMPUTATIONAL_MODEL_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        MODEL_DEFINITION_COMPLETENESS,
        TRANSITION_RULE_VALIDITY,
        SEMANTIC_CLARITY,
        SIMULATION_PROOF_VALIDITY,
        EQUIVALENCE_PROOF_VALIDITY,
        RESOURCE_MODEL_CLARITY,
        REPRODUCIBILITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF FORMAL_PROOF_SUPPORTS_MODEL_RELATION
    THEN INCREASE CONFIDENCE_SCORE

    IF CLAIM_IS_SUPPORTED_ONLY_BY_FINITE_EXPERIMENT
    THEN LIMIT_GENERALISATION_CONFIDENCE

    IF MODEL_SEMANTICS_ARE_AMBIGUOUS
    THEN REDUCE CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        FORMAL_MODEL_DEFINITION,
        STATE_SPACE,
        TRANSITION_SEMANTICS,
        INPUT_OUTPUT_SEMANTICS,
        RESOURCE_CONTEXT
      )

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

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    MODEL != IMPLEMENTATION
    STATE != CONFIGURATION_IN_ALL_MODELS
    SIMULATION != EQUIVALENCE
    EQUIVALENT_OUTPUT_ON_SAMPLES != MODEL_EQUIVALENCE
    COMPUTATIONAL_POWER != EFFICIENCY
    COMPUTABILITY != RESOURCE_COMPLEXITY
    NONDETERMINISM != RANDOMNESS
    PROBABILISTIC_TRANSITION != NONDETERMINISTIC_CHOICE
    ENCODING_AFFECTS_SIMULATION_RELATION
    RESOURCE_BOUNDS_REQUIRE_MODEL_CONTEXT
    HALTING_SEMANTICS_MUST_BE_EXPLICIT
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_MODEL_DEFINITIONS
    CHECK_STATE_SPACES
    CHECK_TRANSITION_RULES
    CHECK_INPUT_OUTPUT_DOMAINS
    CHECK_ACCEPTANCE_SEMANTICS
    CHECK_HALTING_SEMANTICS
    CHECK_MEMORY_MODEL
    CHECK_RESOURCE_MODEL
    CHECK_SIMULATION_RELATIONS
    CHECK_EQUIVALENCE_CLAIMS
    CHECK_REDUCTION_RELATIONS
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_COMPUTATIONAL_MODELS
    MODEL_CLASSIFICATIONS
    STATE_TRANSITION_RELATIONS
    EXECUTION_TRACES
    FUNCTION_COMPUTATION_RELATIONS
    SIMULATION_RELATIONS
    MODEL_EQUIVALENCE_RELATIONS
    RESOURCE_RELATIONS
    ACCEPTANCE_RESULTS
    HALTING_RESULTS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON NEW_MODEL_OR_FORMAL_RESULT {
      NORMALISE
      ENTITY_RESOLUTION
      UPDATE_MODEL_RELATIONS
      UPDATE_SIMULATION_RELATIONS
      UPDATE_EQUIVALENCE_RELATIONS
      RECOMPUTE_DEPENDENT_INFERENCES
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON NEW_PROOF_OR_COUNTEREXAMPLE {
      LINK_EVIDENCE
      REASSESS_SIMULATION_CLAIMS
      REASSESS_EQUIVALENCE_CLAIMS
      REASSESS_RESOURCE_CLAIMS
      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_MODEL
      BY_MACHINE
      BY_STATE
      BY_TRANSITION
      BY_FUNCTION
      BY_INPUT
      BY_OUTPUT
      BY_RESOURCE
      BY_SIMULATION
      BY_EQUIVALENCE
      BY_HALTING
      BY_CONFIDENCE
    }

    REASON {
      APPLY_FORMAL_RULES
      TRACE_MODEL_EXECUTION
      TRACE_STATE_TRANSITIONS
      ANALYSE_FUNCTION_COMPUTATION
      ANALYSE_SIMULATION
      ANALYSE_MODEL_EQUIVALENCE
      ANALYSE_RESOURCE_USAGE
      ANALYSE_HALTING_AND_ACCEPTANCE
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_MODEL_FROM_IMPLEMENTATION
      DISTINGUISH_SIMULATION_FROM_EQUIVALENCE
      DISTINGUISH_COMPUTATIONAL_POWER_FROM_EFFICIENCY
      PRESERVE_MODEL_AND_RESOURCE_CONTEXT
      DISTINGUISH_NONDETERMINISM_FROM_RANDOMNESS
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_MODEL_INFERENCE
    }
  }

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

END FLOW