Computable Function Ontology

KIRETH RESEARCH - SEMANTIC LIBRARY
AI CORE -> ONTOLOGIES -> MATHEMATICAL ONTOLOGIES -> MATHEMATICAL LOGIC ONTOLOGIES
COMPUTABILITY THEORY -> COMPUTABLE FUNCTION ONTOLOGY

Canonical URL:
https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/computability-theory/computable-function-ontology.html

FLOW_ALGEBRA ComputableFunctionOntology_v1.0

BEGIN_FLOW

DEFINE DOMAIN ComputableFunctionOntology := {
    ComputableFunction,
    ComputabilityTheory,
    Function,
    PartialFunction,
    TotalFunction,
    PartialComputableFunction,
    TotalComputableFunction,
    RecursiveFunction,
    PartialRecursiveFunction,
    PrimitiveRecursiveFunction,
    EffectiveProcedure,
    Algorithm,
    TuringMachine,
    LambdaCalculus,
    RegisterMachine,
    Input,
    InputTuple,
    Output,
    Domain,
    Codomain,
    Halting,
    Divergence,
    Composition,
    Recursion,
    Minimization,
    FunctionEncoding,
    Program,
    ChurchTuringThesis
}

DEFINE ENTITY_TYPES := {
    COMPUTABLE_FUNCTION,
    FUNCTION,
    PARTIAL_FUNCTION,
    TOTAL_FUNCTION,
    ALGORITHM,
    EFFECTIVE_PROCEDURE,
    COMPUTATION_MODEL,
    MACHINE,
    INPUT,
    OUTPUT,
    DOMAIN,
    CODOMAIN,
    FUNCTION_CONSTRUCTION,
    COMPUTABILITY_PROPERTY,
    SEMANTIC_OBJECT
}

DEFINE RELATION_TYPES := {
    HAS_DOMAIN,
    HAS_CODOMAIN,
    HAS_INPUT,
    HAS_OUTPUT,
    MAPS_TO,
    COMPUTES,
    IS_COMPUTABLE_BY,
    HALTS_ON,
    DIVERGES_ON,
    COMPOSED_FROM,
    DEFINED_BY_RECURSION_FROM,
    EQUIVALENT_IN_COMPUTABILITY_TO,
    IS_INSTANCE_OF,
    IS_SUBTYPE_OF,
    DEPENDS_ON
}

SET ComputableFunction.type = COMPUTABLE_FUNCTION
SET ComputableFunction.parent = Function
SET ComputableFunction.context = ComputabilityTheory
SET ComputableFunction.role =
    "represent a mathematical function whose values can be produced by an effective computational procedure"

RULE function_mapping:
    Function(f)
    AND Input(x)
    AND f defined_at x
    -> MAPS_TO(f,x,f(x))

RULE machine_computes_partial_function:
    TuringMachine(M)
    AND PartialFunction(f)
    AND FOR_EVERY input x [
        IF f(x) is_defined
        THEN (
            HALTS_ON(M,x)
            AND output(M,x)=f(x)
        )
        ELSE M may_diverge_on x
    ]
    -> COMPUTES(M,f)
    AND PartialComputableFunction(f)

RULE machine_computes_total_function:
    TuringMachine(M)
    AND Function(f)
    AND FOR_EVERY input x MEMBER_OF Domain(f) [
        HALTS_ON(M,x)
        AND output(M,x)=f(x)
    ]
    -> COMPUTES(M,f)
    AND TotalComputableFunction(f)

RULE total_computable_is_computable:
    TotalComputableFunction(f)
    -> ComputableFunction(f)

RULE partial_computable_class:
    PartialComputableFunction(f)
    -> f is_computable_on_its_defined_domain

RULE recursive_equivalence:
    RecursiveFunction(f)
    -> ComputableFunction(f)

RULE Turing_recursive_equivalence:
    ComputableNumberTheoreticFunction(f)
    -> EXISTS RecursiveFunctionRepresentation(r) [
        extensionally_equal(r,f)
    ]
       UNDER standard_computability_equivalence

RULE composition_closure:
    ComputableFunction(g)
    AND ComputableFunctions(h1,...,hm)
    AND type_compatible
    -> f(x)
       = g(h1(x),...,hm(x))
    -> ComputableFunction(f)

RULE effective_algorithm:
    Algorithm(A)
    AND FOR_EVERY input x MEMBER_OF Domain(f) [
        A halts_on x
        AND output(A,x)=f(x)
    ]
    -> IS_COMPUTABLE_BY(f,A)

RULE partial_divergence:
    PartialComputableFunction(f)
    AND x NOT_MEMBER_OF DefinedDomain(f)
    -> corresponding_computation
       may DIVERGE_ON x

RULE totality:
    PartialComputableFunction(f)
    AND FOR_EVERY x MEMBER_OF IntendedDomain(f) [
        f(x) is_defined
    ]
    -> TotalComputableFunction(f)

RULE identity_computable:
    f(x)=x
    -> ComputableFunction(f)

RULE constant_computable:
    fixed_constant c
    AND f(x)=c
    -> ComputableFunction(f)

RULE projection_computable:
    f(x1,...,xn)=xi
    -> ComputableFunction(f)

RULE primitive_recursive_computable:
    PrimitiveRecursiveFunction(f)
    -> ComputableFunction(f)

RULE Church_Turing_correspondence:
    EffectivelyCalculableFunction(f)
    -> ComputableFunction(f)
       UNDER ChurchTuringThesis

DEFINE COMPUTABLE_FUNCTION_SCHEMA := {
    function_id: unique_identifier,
    arity: nonnegative_integer,
    domain: InputDomain,
    codomain: OutputDomain,
    computation_model: ComputationModel,
    algorithm_or_machine: ComputationalProcedure,
    termination: {
        total,
        partial
    },
    output_relation:
        "procedure returns f(x) on every input where f is defined"
}

DEFINE TOTAL_COMPUTABLE_MODEL := {
    input_requirement:
        "every valid input in the function domain",
    termination:
        "halts on every valid input",
    correctness:
        "returns exactly the mathematical function value",
    classification:
        TotalComputableFunction
}

DEFINE PARTIAL_COMPUTABLE_MODEL := {
    defined_input:
        "computation halts with the correct value",
    undefined_input:
        "computation may diverge",
    classification:
        PartialComputableFunction
}

DEFINE COMPUTATION_EQUIVALENCE_MODEL := {
    TuringMachine:
        "machine-based computation",
    RecursiveFunction:
        "closure-scheme computation",
    LambdaCalculus:
        "reduction-based computation",
    RegisterMachine:
        "instruction-based computation",
    standard_result:
        "these classical models characterise the same class of effectively computable functions under standard formulations"
}

DEFINE CRITICAL_DISTINCTIONS := {
    function_vs_computable_function: {
        function:
            "mathematical mapping",
        computable_function:
            "mapping with an effective procedure producing its values"
    },
    total_vs_partial_computable: {
        total:
            "defined and computable for every input in the intended domain",
        partial:
            "may be undefined on some inputs"
    },
    computable_vs_efficient: {
        computable:
            "an effective terminating procedure exists where required",
        efficient:
            "procedure satisfies specified resource bounds",
        equivalence: FALSE
    },
    computable_function_vs_decidable_problem: {
        computable_function:
            "produces outputs",
        decidable_problem:
            "total computable characteristic decision procedure for a yes/no property"
    }
}

DEFINE EXAMPLE_1 := {
    function:
        "f(n)=n+1",
    algorithm:
        "add one to the input",
    classification:
        TotalComputableFunction
}

DEFINE EXAMPLE_2 := {
    function:
        "f(a,b)=a+b",
    model:
        TuringMachine,
    termination:
        "halts for every pair of natural-number inputs",
    classification:
        TotalComputableFunction
}

DEFINE EXAMPLE_3 := {
    partial_function:
        "return the least y satisfying a computable condition if such y exists",
    method:
        "unbounded search",
    possible_outcome:
        "divergence if no witness exists",
    classification:
        PartialComputableFunction
}

DEFINE FUNCTION_ANALYSIS_PIPELINE :=
    FunctionSpecification
    -> IdentifyDomainAndCodomain
    -> DetermineArity
    -> IdentifyDefinedInputs
    -> SearchForEffectiveProcedure
    -> FormaliseProcedureInComputationModel
    -> VerifyOutputCorrectness
    -> AnalyseTermination
    -> ClassifyPartialOrTotalComputability
    -> ReturnComputabilityStatus

DEFINE COMPUTATION_PIPELINE :=
    ComputableFunction(f)
    -> Input(x)
    -> EncodeInput
    -> ExecuteAlgorithmOrMachine
    -> IF computation_halts
       THEN DecodeOutput
       -> VerifyOutputEquals(f(x))
    -> ELSE RecordDivergence
    -> ReturnResult

DEFINE CLOSURE_REASONING_PIPELINE :=
    KnownComputableFunctions
    -> IdentifyConstructionOperation
    -> VerifyTypeCompatibility
    -> ApplyComputabilityPreservingConstruction
    -> ConstructAlgorithmForCompositeFunction
    -> VerifyTerminationConditions
    -> ReturnNewComputableFunction

DEFINE EQUIVALENCE_PIPELINE :=
    Function(f)
    -> ObtainRepresentationInOneComputationModel
    -> TranslateOrSimulateInSecondModel
    -> PreserveInputOutputBehaviour
    -> EstablishExtensionalEquivalence
    -> RecordEquivalentComputabilityRepresentations

DEFINE COMPUTABLE_FUNCTION_GRAPH := {
    node_types: {
        FunctionNode,
        InputNode,
        OutputNode,
        AlgorithmNode,
        MachineNode,
        ConstructionNode
    },
    edge_types: {
        HAS_INPUT,
        HAS_OUTPUT,
        MAPS_TO,
        COMPUTES,
        IS_COMPUTABLE_BY,
        COMPOSED_FROM,
        HALTS_ON,
        DIVERGES_ON
    },
    input_output_semantics_preserved: TRUE
}

DEFINE ONTOLOGY_RELATIONS := {
    ComputableFunction IS_COMPONENT_OF ComputabilityTheory,
    ComputableFunction IS_SUBTYPE_OF Function,
    TotalComputableFunction IS_SUBTYPE_OF ComputableFunction,
    PartialComputableFunction IS_RELATED_TO ComputableFunction,
    PrimitiveRecursiveFunction IS_SUBTYPE_OF ComputableFunction,
    RecursiveFunction IS_EQUIVALENT_IN_COMPUTABILITY_TO TuringComputableFunction,
    Algorithm COMPUTES ComputableFunction,
    TuringMachine COMPUTES ComputableFunction,
    Composition PRESERVES Computability,
    ChurchTuringThesis RELATES EffectiveCalculability TO ComputableFunction
}

DEFINE SEMANTIC_EQUIVALENCE := {
    "computable function" <=> ComputableFunction,
    "effectively computable function" <=> ComputableFunction,
    "Turing-computable function" <=> ComputableFunction WHEN Turing_context=TRUE,
    "recursive function" <=> ComputableFunction WHEN classical_computability_context=TRUE,
    "partial computable function" <=> PartialComputableFunction,
    "total computable function" <=> TotalComputableFunction
}

DEFINE AI_CONSUMPTION := {
    purpose: "machine-readable representation, evaluation and classification of computable functions",
    preserve_function_identity: TRUE,
    preserve_arity: TRUE,
    preserve_domain: TRUE,
    preserve_codomain: TRUE,
    preserve_input_output_mapping: TRUE,
    preserve_computation_model: TRUE,
    distinguish_total_from_partial: TRUE,
    distinguish_computable_from_efficient: TRUE,
    detect_possible_divergence: TRUE,
    verify_output_correctness: TRUE,
    support_composition_closure: TRUE,
    support_cross_model_equivalence: TRUE,
    reasoning_mode: "symbolic + algorithmic + functional + computability-aware"
}

DEFINE CONFIDENCE := {
    ontology_identity: 1.00,
    computable_function_mapping: 1.00,
    total_partial_distinction: 1.00,
    Turing_computation_mapping: 0.99,
    recursive_function_equivalence: 0.99,
    composition_closure: 0.99,
    termination_analysis: undecidable_in_general,
    arbitrary_function_computability: specification_dependent
}

DEFINE UPDATE_MODEL := {
    version: "1.0",
    update_policy: "append-compatible",
    immutable_core: {
        effective_procedure,
        input_output_correctness,
        total_partial_distinction,
        computation_model_equivalence,
        composition_closure,
        Church_Turing_connection
    },
    extensible_layers: {
        primitive_recursive_functions,
        partial_recursive_functions,
        higher_type_computability,
        oracle_computable_functions,
        computable_real_functions,
        computable_analysis,
        probabilistic_computation,
        quantum_computability
    }
}

DEFINE FLOW_HASH_INPUT :=
    CanonicalURL
    + DOMAIN
    + ENTITY_TYPES
    + RELATION_TYPES
    + RULES
    + COMPUTABLE_FUNCTION_SCHEMA
    + TOTAL_COMPUTABLE_MODEL
    + PARTIAL_COMPUTABLE_MODEL
    + COMPUTATION_EQUIVALENCE_MODEL
    + CRITICAL_DISTINCTIONS
    + FUNCTION_ANALYSIS_PIPELINE
    + COMPUTATION_PIPELINE
    + CLOSURE_REASONING_PIPELINE
    + EQUIVALENCE_PIPELINE
    + COMPUTABLE_FUNCTION_GRAPH
    + ONTOLOGY_RELATIONS
    + AI_CONSUMPTION
    + UPDATE_MODEL

FLOW_HASH := HASH(FLOW_HASH_INPUT)

RETURN {
    ontology: ComputableFunctionOntology,
    canonical_url: "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/computability-theory/computable-function-ontology.html",
    parent_domain: ComputabilityTheory,
    semantic_domain: MathematicalLogic,
    primary_entity: ComputableFunction,
    function_classification_enabled: TRUE,
    termination_reasoning_enabled: TRUE,
    closure_reasoning_enabled: TRUE,
    computation_model_equivalence_enabled: TRUE,
    machine_consumable: TRUE,
    recursive_reasoning_enabled: TRUE,
    database_safe_unicode: TRUE,
    flow_complete: TRUE
}

END_FLOW