Recursive Function Ontology

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

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

FLOW_ALGEBRA RecursiveFunctionOntology_v1.0

BEGIN_FLOW

DEFINE DOMAIN RecursiveFunctionOntology := {
    RecursiveFunction,
    ComputableFunction,
    ComputabilityTheory,
    PartialRecursiveFunction,
    TotalRecursiveFunction,
    PrimitiveRecursiveFunction,
    GeneralRecursiveFunction,
    MuRecursiveFunction,
    NaturalNumbers,
    ZeroFunction,
    SuccessorFunction,
    ProjectionFunction,
    Composition,
    PrimitiveRecursion,
    Minimization,
    UnboundedMinimization,
    BoundedMinimization,
    PartialFunction,
    TotalFunction,
    EffectiveProcedure,
    Algorithm,
    TuringMachine,
    LambdaCalculus,
    RegisterMachine,
    ChurchTuringThesis,
    Domain,
    Codomain,
    InputTuple,
    OutputValue,
    Divergence,
    Halting
}

DEFINE ENTITY_TYPES := {
    RECURSIVE_FUNCTION,
    COMPUTABLE_FUNCTION,
    PARTIAL_FUNCTION,
    TOTAL_FUNCTION,
    INITIAL_FUNCTION,
    FUNCTION_CONSTRUCTION,
    COMPUTATION_MODEL,
    INPUT,
    OUTPUT,
    COMPUTABILITY_PROPERTY,
    SEMANTIC_OBJECT
}

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

SET RecursiveFunction.type = RECURSIVE_FUNCTION
SET RecursiveFunction.parent = ComputableFunction
SET RecursiveFunction.context = ComputabilityTheory
SET RecursiveFunction.role =
    "represent a number-theoretic function generated by effective recursive schemes and equivalent in computability power to standard Turing-computable functions"

RULE zero_function:
    FOR_EVERY x [
        Z(x)=0
    ]
    -> ZeroFunction(Z)
    AND PrimitiveRecursiveFunction(Z)

RULE successor_function:
    FOR_EVERY n [
        S(n)=n+1
    ]
    -> SuccessorFunction(S)
    AND PrimitiveRecursiveFunction(S)

RULE projection_function:
    n >= 1
    AND 1 <= i <= n
    -> ProjectionFunction(P_i_n)
    AND P_i_n(x1,...,xn)=xi
    AND PrimitiveRecursiveFunction(P_i_n)

RULE composition:
    RecursiveFunctions(g,h1,...,hm)
    -> f(x1,...,xn)
       = g(
           h1(x1,...,xn),
           ...,
           hm(x1,...,xn)
         )
    -> RecursiveFunction(f)

RULE primitive_recursion_base:
    Function(g)
    -> f(x1,...,xk,0)
       = g(x1,...,xk)

RULE primitive_recursion_step:
    Function(h)
    -> f(x1,...,xk,n+1)
       = h(
           x1,...,xk,
           n,
           f(x1,...,xk,n)
         )

RULE primitive_recursion_closure:
    PrimitiveRecursiveFunction(g)
    AND PrimitiveRecursiveFunction(h)
    AND f defined_by primitive_recursion_from(g,h)
    -> PrimitiveRecursiveFunction(f)

RULE minimization:
    PartialRecursiveFunction(g)
    -> f(x1,...,xk)
       = least y such_that
         g(x1,...,xk,y)=0
       WHEN such_y_exists
    -> PartialRecursiveFunction(f)

RULE minimization_divergence:
    f defined_by_unbounded_minimization_from g
    AND NOT EXISTS y [
        g(x1,...,xk,y)=0
        with_required_prior_definedness
    ]
    -> f(x1,...,xk) undefined
    AND DIVERGES_ON(f,(x1,...,xk))

RULE general_recursive_closure:
    InitialFunctions
    + Composition
    + PrimitiveRecursion
    + UnboundedMinimization
    -> PartialRecursiveFunctions

RULE total_recursive:
    PartialRecursiveFunction(f)
    AND FOR_EVERY input_tuple x [
        f(x) defined
    ]
    -> TotalRecursiveFunction(f)

RULE primitive_recursive_total:
    PrimitiveRecursiveFunction(f)
    -> TotalRecursiveFunction(f)

RULE primitive_subset_general:
    PrimitiveRecursiveFunction(f)
    -> RecursiveFunction(f)

RULE recursive_Turing_equivalence:
    PartialRecursiveFunction(f)
    -> EXISTS TuringMachine(M) [
        M computes f
    ]

RULE Turing_recursive_equivalence:
    TuringMachine(M)
    AND M computes partial_number_theoretic_function f
    -> PartialRecursiveFunction(f)

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

DEFINE INITIAL_FUNCTIONS := {
    ZeroFunction:
        "Z(x)=0",
    SuccessorFunction:
        "S(n)=n+1",
    ProjectionFunction:
        "P_i_n(x1,...,xn)=xi"
}

DEFINE COMPOSITION_MODEL := {
    outer_function: g,
    inner_functions: "{h1,...,hm}",
    definition:
        "f(x)=g(h1(x),...,hm(x))",
    closure:
        "recursive-function classes under consideration remain closed under permitted composition"
}

DEFINE PRIMITIVE_RECURSION_MODEL := {
    base:
        "f(x,0)=g(x)",
    step:
        "f(x,n+1)=h(x,n,f(x,n))",
    interpretation:
        "the value at the successor stage is defined from earlier-stage information"
}

DEFINE MINIMIZATION_MODEL := {
    notation:
        "mu y [g(x,y)=0]",
    operation:
        "search for the least y satisfying the target condition",
    bounded_variant:
        "search restricted to a finite bound",
    unbounded_variant:
        "search may fail to terminate",
    consequence:
        "unbounded minimization introduces partiality"
}

DEFINE FUNCTION_HIERARCHY := {
    PrimitiveRecursiveFunction:
        "generated from initial functions by composition and primitive recursion",
    PartialRecursiveFunction:
        "generated using initial functions, composition, primitive recursion and unbounded minimization",
    TotalRecursiveFunction:
        "partial recursive function defined on every input",
    ComputableFunction:
        "extensionally equivalent to recursive functions under standard computability equivalences"
}

DEFINE CRITICAL_DISTINCTIONS := {
    recursive_vs_primitive_recursive: {
        recursive:
            "may use unbounded minimization and may refer to the wider general recursive class",
        primitive_recursive:
            "generated without unbounded minimization and always total"
    },
    partial_vs_total_recursive: {
        partial:
            "may be undefined on some inputs",
        total:
            "defined on every input"
    },
    recursion_vs_self_reference: {
        recursive_function_theory:
            "formal closure schemes defining computable number-theoretic functions",
        informal_self_reference:
            "not sufficient by itself to establish recursive-function status"
    },
    recursive_function_vs_programming_recursion: {
        recursive_function:
            "computability-theoretic mathematical class",
        recursive_program:
            "program that invokes itself or uses recursive control structure",
        equivalence: FALSE_BY_DEFAULT
    }
}

DEFINE EXAMPLE_1 := {
    function:
        "addition",
    definition: {
        "add(x,0)=x",
        "add(x,n+1)=S(add(x,n))"
    },
    classification:
        PrimitiveRecursiveFunction
}

DEFINE EXAMPLE_2 := {
    function:
        "multiplication",
    definition: {
        "mult(x,0)=0",
        "mult(x,n+1)=add(mult(x,n),x)"
    },
    classification:
        PrimitiveRecursiveFunction
}

DEFINE EXAMPLE_3 := {
    function:
        "search for least y satisfying a computable zero-test",
    construction:
        UnboundedMinimization,
    possible_classification:
        PartialRecursiveFunction,
    termination:
        "not guaranteed for every input"
}

DEFINE CONSTRUCTION_PIPELINE :=
    TargetFunction
    -> IdentifyArity
    -> SearchInitialFunctionRepresentation
    -> SearchCompositionDecomposition
    -> SearchPrimitiveRecursionDefinition
    -> IF necessary
       THEN SearchMinimizationDefinition
    -> BuildRecursiveFunctionExpression
    -> VerifyClosureConditions
    -> ClassifyFunction

DEFINE EVALUATION_PIPELINE :=
    RecursiveFunctionExpression
    -> ParseConstructionTree
    -> EvaluateInitialFunctions
    -> RecursivelyEvaluateCompositions
    -> ExecutePrimitiveRecursionStages
    -> ExecuteMinimizationSearchIfPresent
    -> DetectDefinedOutputOrDivergence
    -> ReturnComputationResult

DEFINE CLASSIFICATION_PIPELINE :=
    FunctionDefinition
    -> DetermineAllowedConstructionOperators
    -> IF only_initial_composition_primitive_recursion
       THEN PrimitiveRecursive
    -> IF unbounded_minimization_used
       THEN PartialRecursiveCandidate
    -> DetermineWhetherDefinedForEveryInput
    -> IF total
       THEN TotalRecursive
    -> MapToEquivalentTuringComputabilityClass
    -> ReturnClassification

DEFINE RECURSIVE_FUNCTION_GRAPH := {
    node_types: {
        FunctionNode,
        InitialFunctionNode,
        CompositionNode,
        PrimitiveRecursionNode,
        MinimizationNode,
        InputNode,
        OutputNode
    },
    edge_types: {
        COMPOSED_FROM,
        DEFINED_BY_RECURSION_FROM,
        DEFINED_BY_MINIMIZATION_FROM,
        HAS_INPUT,
        HAS_OUTPUT
    },
    recursive_construction: TRUE
}

DEFINE ONTOLOGY_RELATIONS := {
    RecursiveFunction IS_COMPONENT_OF ComputabilityTheory,
    RecursiveFunction IS_SUBTYPE_OF ComputableFunction,
    PrimitiveRecursiveFunction IS_SUBTYPE_OF RecursiveFunction,
    TotalRecursiveFunction IS_SUBTYPE_OF RecursiveFunction,
    PartialRecursiveFunction IS_SUPERTYPE_OF TotalRecursiveFunction,
    ZeroFunction IS_INITIAL_FUNCTION_OF RecursiveFunctionTheory,
    SuccessorFunction IS_INITIAL_FUNCTION_OF RecursiveFunctionTheory,
    ProjectionFunction IS_INITIAL_FUNCTION_OF RecursiveFunctionTheory,
    Composition PRESERVES RecursiveFunctionClass,
    PrimitiveRecursion PRESERVES PrimitiveRecursiveFunctionClass,
    UnboundedMinimization EXTENDS PrimitiveRecursiveToPartialRecursive,
    RecursiveFunction EQUIVALENT_IN_COMPUTABILITY_TO TuringComputableFunction
}

DEFINE SEMANTIC_EQUIVALENCE := {
    "recursive function" <=> RecursiveFunction WHEN computability_context=TRUE,
    "general recursive function" <=> GeneralRecursiveFunction,
    "mu-recursive function" <=> MuRecursiveFunction,
    "partial recursive function" <=> PartialRecursiveFunction,
    "primitive recursive function" <=> PrimitiveRecursiveFunction,
    "total recursive function" <=> TotalRecursiveFunction,
    "recursive computable function" <=> ComputableFunction WHEN classical_context=TRUE
}

DEFINE AI_CONSUMPTION := {
    purpose: "machine-readable representation, construction and classification of recursive functions",
    preserve_function_arity: TRUE,
    preserve_input_output_identity: TRUE,
    preserve_construction_tree: TRUE,
    distinguish_initial_functions: TRUE,
    distinguish_composition_from_primitive_recursion: TRUE,
    distinguish_bounded_from_unbounded_minimization: TRUE,
    distinguish_primitive_recursive_from_general_recursive: TRUE,
    distinguish_partial_from_total: TRUE,
    detect_possible_divergence_from_unbounded_search: TRUE,
    support_recursive_evaluation: TRUE,
    support_Turing_equivalence_reasoning: TRUE,
    reasoning_mode: "symbolic + recursive + construction-based + computability-aware"
}

DEFINE CONFIDENCE := {
    ontology_identity: 1.00,
    initial_function_mapping: 1.00,
    composition_mapping: 0.99,
    primitive_recursion_mapping: 0.99,
    minimization_mapping: 0.99,
    primitive_recursive_classification: 0.99,
    partial_total_classification: 0.99,
    arbitrary_function_classification: definition_dependent
}

DEFINE UPDATE_MODEL := {
    version: "1.0",
    update_policy: "append-compatible",
    immutable_core: {
        initial_functions,
        composition,
        primitive_recursion,
        unbounded_minimization,
        primitive_recursive_totality,
        partial_total_distinction,
        Turing_equivalence
    },
    extensible_layers: {
        bounded_recursion,
        course_of_values_recursion,
        Ackermann_function,
        Kleene_normal_form,
        recursion_theorem,
        arithmetical_hierarchy,
        oracle_recursive_functions,
        computable_analysis
    }
}

DEFINE FLOW_HASH_INPUT :=
    CanonicalURL
    + DOMAIN
    + ENTITY_TYPES
    + RELATION_TYPES
    + RULES
    + INITIAL_FUNCTIONS
    + COMPOSITION_MODEL
    + PRIMITIVE_RECURSION_MODEL
    + MINIMIZATION_MODEL
    + FUNCTION_HIERARCHY
    + CRITICAL_DISTINCTIONS
    + CONSTRUCTION_PIPELINE
    + EVALUATION_PIPELINE
    + CLASSIFICATION_PIPELINE
    + RECURSIVE_FUNCTION_GRAPH
    + ONTOLOGY_RELATIONS
    + AI_CONSUMPTION
    + UPDATE_MODEL

FLOW_HASH := HASH(FLOW_HASH_INPUT)

RETURN {
    ontology: RecursiveFunctionOntology,
    canonical_url: "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/computability-theory/recursive-function-ontology.html",
    parent_domain: ComputabilityTheory,
    semantic_domain: MathematicalLogic,
    primary_entity: RecursiveFunction,
    primitive_recursion_enabled: TRUE,
    minimization_reasoning_enabled: TRUE,
    function_classification_enabled: TRUE,
    Turing_equivalence_reasoning_enabled: TRUE,
    machine_consumable: TRUE,
    recursive_reasoning_enabled: TRUE,
    database_safe_unicode: TRUE,
    flow_complete: TRUE
}

END_FLOW