Undecidability Ontology

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

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

FLOW_ALGEBRA UndecidabilityOntology_v1.0

BEGIN_FLOW

DEFINE DOMAIN UndecidabilityOntology := {
    Undecidability,
    ComputabilityTheory,
    DecisionProblem,
    UndecidableProblem,
    DecidableProblem,
    SemiDecidableProblem,
    RecognisableProblem,
    UnrecognisableProblem,
    Language,
    Algorithm,
    Decider,
    Recogniser,
    TuringMachine,
    Halting,
    Divergence,
    Reduction,
    ManyOneReduction,
    TuringReduction,
    MappingReduction,
    HaltingProblem,
    AcceptanceProblem,
    Diagonalisation,
    SelfReference,
    Contradiction,
    RiceTheorem,
    PostCorrespondenceProblem,
    Entscheidungsproblem,
    ComputableFunction,
    TotalComputableFunction,
    Oracle,
    RelativeComputability,
    UndecidabilityProof
}

DEFINE ENTITY_TYPES := {
    UNDECIDABILITY_PROPERTY,
    DECISION_PROBLEM,
    LANGUAGE,
    ALGORITHM,
    DECIDER,
    RECOGNISER,
    MACHINE,
    REDUCTION,
    COMPUTABLE_FUNCTION,
    THEOREM,
    PROOF,
    ORACLE,
    SEMANTIC_OBJECT
}

DEFINE RELATION_TYPES := {
    DECIDES,
    RECOGNISES,
    ACCEPTS,
    REJECTS,
    HALTS_ON,
    DIVERGES_ON,
    REDUCES_TO,
    MANY_ONE_REDUCES_TO,
    TURING_REDUCES_TO,
    COMPUTES,
    SIMULATES,
    CONTRADICTS,
    WITNESSES,
    QUERIES,
    IS_INSTANCE_OF,
    IS_SUBTYPE_OF,
    DEPENDS_ON
}

SET Undecidability.type = UNDECIDABILITY_PROPERTY
SET Undecidability.context = ComputabilityTheory
SET Undecidability.role =
    "classify decision problems for which no algorithm can correctly decide every valid input while halting on all inputs"

RULE undecidable_definition:
    DecisionProblem(P)
    AND NOT EXISTS Algorithm(A) [
        FOR_EVERY input x MEMBER_OF InstanceDomain(P) [
            HALTS_ON(A,x)
            AND output(A,x)=CorrectDecision(P,x)
        ]
    ]
    -> UndecidableProblem(P)

RULE decidable_exclusion:
    UndecidableProblem(P)
    -> NOT DecidableProblem(P)

RULE unrecognisable_implies_undecidable:
    UnrecognisableProblem(P)
    -> UndecidableProblem(P)

RULE recognisable_may_be_undecidable:
    RecognisableProblem(P)
    AND NOT RecognisableProblem(Complement(P))
    -> UndecidableProblem(P)

RULE halting_problem_definition:
    HaltingProblem(HALT)
    -> HALT = {
        encode(M,w)
        | HALTS_ON(M,w)
    }

RULE halting_problem_undecidable:
    -> UndecidableProblem(HaltingProblem)

RULE diagonal_halting_argument:
    Assume Decider(H) for HaltingProblem
    -> ConstructMachine(D) such_that {
        D(x):
            IF H(x,x)=HALTS
            THEN loop_forever
            ELSE halt
    }
    -> Evaluate D on encode(D)
    -> Contradiction
    -> RejectExistenceOf(H)

RULE many_one_reduction:
    DecisionProblem(A)
    AND DecisionProblem(B)
    AND EXISTS TotalComputableFunction(f) [
        FOR_EVERY x [
            A(x)=TRUE
            IFF
            B(f(x))=TRUE
        ]
    ]
    -> MANY_ONE_REDUCES_TO(A,B)

RULE undecidability_transfer:
    UndecidableProblem(A)
    AND MANY_ONE_REDUCES_TO(A,B)
    -> UndecidableProblem(B)

RULE decidability_backward:
    MANY_ONE_REDUCES_TO(A,B)
    AND DecidableProblem(B)
    -> DecidableProblem(A)

RULE reduction_direction_guard:
    Goal=prove_undecidable(B)
    AND KnownUndecidable(A)
    -> REQUIRED_DIRECTION:
       A REDUCES_TO B

RULE turing_reduction:
    DecisionProblem(A)
    AND DecisionProblem(B)
    AND OracleAlgorithm(O^B) decides A
    -> TURING_REDUCES_TO(A,B)

RULE Rice_theorem:
    Property(P)
    AND P is_nontrivial
    AND P is_semantic_property_of_partial_computable_function
    -> UndecidableProblem(
        {
            encode(M)
            | function_computed_by(M) has_property P
        }
    )

RULE semantic_property_nontrivial:
    EXISTS machine M1 with property P
    AND EXISTS machine M2 without property P
    -> Nontrivial(P)

RULE finite_observation_guard:
    Program(M)
    AND Input(w)
    AND observed_running_for_finite_time
    -> DO_NOT_INFER divergence

RULE undecidability_not_unsolvability_instance:
    UndecidableProblem(P)
    -> DOES_NOT_MEAN
       every_individual_instance_is_impossible_to_answer

DEFINE UNDECIDABILITY_MODEL := {
    problem:
        DecisionProblem,
    requirement_for_decidability:
        "one total algorithm must correctly decide every valid instance",
    undecidable:
        "no such total correct algorithm exists"
}

DEFINE REDUCTION_PROOF_MODEL := {
    target:
        "prove B undecidable",
    source:
        "known undecidable problem A",
    required_relation:
        "A REDUCES_TO B",
    proof_pattern: {
        "assume B has a decider",
        "use the reduction to decide A",
        "contradict known undecidability of A",
        "conclude B is undecidable"
    }
}

DEFINE DIAGONALISATION_MODEL := {
    components: {
        assumed_total_decider,
        encoded_programs,
        self_application,
        behaviour_reversal,
        contradiction
    },
    purpose:
        "show that the assumed universal decision procedure cannot exist"
}

DEFINE RICE_THEOREM_MODEL := {
    scope:
        "nontrivial semantic properties of partial computable functions represented by programs or machines",
    excluded_properties:
        "purely syntactic properties of program text",
    conclusion:
        "the corresponding machine-index decision problem is undecidable"
}

DEFINE CRITICAL_DISTINCTIONS := {
    undecidable_vs_unrecognisable: {
        undecidable:
            "no total decider exists",
        unrecognisable:
            "no recogniser exists",
        implication:
            "unrecognisable implies undecidable, but not conversely"
    },
    undecidable_vs_difficult: {
        undecidable:
            "no algorithm solves all instances with guaranteed termination and correctness",
        difficult:
            "algorithm may exist but require substantial resources",
        equivalence: FALSE
    },
    problem_vs_instance: {
        undecidable_problem:
            "global statement about absence of a universal decider",
        individual_instance:
            "may still be answerable by direct analysis"
    },
    nonhalting_vs_not_yet_halted: {
        nonhalting:
            "infinite computation",
        finite_observation:
            "insufficient by itself to prove nonhalting"
    }
}

DEFINE EXAMPLE_1 := {
    problem:
        HaltingProblem,
    input:
        "encode(M,w)",
    question:
        "does M halt on w?",
    classification:
        UndecidableProblem
}

DEFINE EXAMPLE_2 := {
    source_problem:
        HaltingProblem,
    target_problem:
        "B",
    relation:
        "HaltingProblem MANY_ONE_REDUCES_TO B",
    consequence:
        "B is undecidable"
}

DEFINE EXAMPLE_3 := {
    property:
        "the function computed by machine M is identically zero",
    classification:
        "nontrivial semantic property",
    theorem:
        RiceTheorem,
    conclusion:
        "the corresponding machine-index problem is undecidable"
}

DEFINE UNDECIDABILITY_ANALYSIS_PIPELINE :=
    TargetDecisionProblem
    -> ConfirmDecisionProblemForm
    -> SearchForKnownDecisionAlgorithm
    -> IF total_correct_decider_found
       THEN Decidable
    -> ELSE IdentifyApplicableUndecidabilityMethod
    -> ChooseReductionDiagonalisationOrRiceTheorem
    -> ConstructFormalArgument
    -> VerifyAllConditions
    -> ReturnUndecidabilityResult

DEFINE REDUCTION_PIPELINE :=
    KnownUndecidableProblem(A)
    -> TargetProblem(B)
    -> ConstructComputableTransformation(f)
    -> ProveYesInstancePreservation
    -> ProveNoInstancePreservation
    -> Establish A MANY_ONE_REDUCES_TO B
    -> AssumeDeciderForB
    -> ConstructDeciderForA
    -> DeriveContradiction
    -> ConcludeUndecidable(B)

DEFINE DIAGONAL_PIPELINE :=
    CandidateUniversalDecider
    -> EncodeProgramsAsData
    -> ConstructSelfReferentialMachine
    -> ReversePredictedBehaviour
    -> ApplyMachineToOwnEncoding
    -> DeriveContradiction
    -> RejectCandidateDecider

DEFINE RICE_PIPELINE :=
    MachineProperty(P)
    -> DetermineWhetherPropertyIsSemantic
    -> DetermineWhetherPropertyIsNontrivial
    -> IF both_conditions_true
       THEN ApplyRiceTheorem
    -> ReturnUndecidabilityClassification

DEFINE UNDECIDABILITY_GRAPH := {
    node_types: {
        ProblemNode,
        MachineNode,
        AlgorithmNode,
        ReductionNode,
        TheoremNode,
        ContradictionNode
    },
    edge_types: {
        REDUCES_TO,
        DECIDES,
        RECOGNISES,
        HALTS_ON,
        DIVERGES_ON,
        CONTRADICTS,
        WITNESSES
    },
    reduction_direction_sensitive: TRUE
}

DEFINE ONTOLOGY_RELATIONS := {
    Undecidability IS_COMPONENT_OF ComputabilityTheory,
    UndecidableProblem IS_SUBTYPE_OF DecisionProblem,
    HaltingProblem IS_INSTANCE_OF UndecidableProblem,
    UnrecognisableProblem IS_SUBTYPE_OF UndecidableProblem,
    ManyOneReduction IS_SUBTYPE_OF Reduction,
    TuringReduction IS_SUBTYPE_OF Reduction,
    Diagonalisation PROVES Undecidability,
    RiceTheorem PROVES UndecidabilityForSemanticMachineProperties,
    Reduction TRANSFERS UndecidabilityFromSourceToTarget,
    Oracle ENABLES RelativeComputability
}

DEFINE SEMANTIC_EQUIVALENCE := {
    "undecidability" <=> Undecidability,
    "undecidable problem" <=> UndecidableProblem,
    "algorithmically undecidable" <=> UndecidableProblem,
    "non-decidable" <=> UndecidableProblem,
    "halting problem" <=> HaltingProblem,
    "diagonal argument" <=> Diagonalisation WHEN computability_context=TRUE,
    "Rice's theorem" <=> RiceTheorem
}

DEFINE AI_CONSUMPTION := {
    purpose: "machine-readable representation and proof reasoning for undecidable decision problems",
    preserve_problem_identity: TRUE,
    preserve_decision_semantics: TRUE,
    preserve_reduction_direction: TRUE,
    preserve_reduction_type: TRUE,
    validate_reduction_computability: TRUE,
    validate_yes_no_preservation: TRUE,
    distinguish_undecidable_from_unrecognisable: TRUE,
    distinguish_undecidable_from_complex_or_intractable: TRUE,
    distinguish_global_problem_from_individual_instance: TRUE,
    prohibit_nonhalting_inference_from_finite_observation: TRUE,
    support_diagonalisation: TRUE,
    support_Rice_theorem_reasoning: TRUE,
    support_oracle_relative_reasoning: TRUE,
    reasoning_mode: "symbolic + reduction-based + contradiction-aware + meta-computational"
}

DEFINE CONFIDENCE := {
    ontology_identity: 1.00,
    undecidability_definition: 1.00,
    reduction_direction: 1.00,
    reduction_transfer: 1.00,
    halting_problem_mapping: 1.00,
    diagonalisation_mapping: 0.99,
    Rice_theorem_mapping: 0.99,
    arbitrary_problem_undecidability: proof_dependent
}

DEFINE UPDATE_MODEL := {
    version: "1.0",
    update_policy: "append-compatible",
    immutable_core: {
        no_total_correct_decider,
        halting_problem_undecidability,
        reduction_direction,
        undecidability_transfer,
        diagonalisation,
        undecidable_unrecognisable_distinction
    },
    extensible_layers: {
        Rice_theorem,
        Post_correspondence_problem,
        Entscheidungsproblem,
        tiling_problems,
        word_problems,
        oracle_undecidability,
        arithmetic_hierarchy,
        degrees_of_unsolvability
    }
}

DEFINE FLOW_HASH_INPUT :=
    CanonicalURL
    + DOMAIN
    + ENTITY_TYPES
    + RELATION_TYPES
    + RULES
    + UNDECIDABILITY_MODEL
    + REDUCTION_PROOF_MODEL
    + DIAGONALISATION_MODEL
    + RICE_THEOREM_MODEL
    + CRITICAL_DISTINCTIONS
    + UNDECIDABILITY_ANALYSIS_PIPELINE
    + REDUCTION_PIPELINE
    + DIAGONAL_PIPELINE
    + RICE_PIPELINE
    + UNDECIDABILITY_GRAPH
    + ONTOLOGY_RELATIONS
    + AI_CONSUMPTION
    + UPDATE_MODEL

FLOW_HASH := HASH(FLOW_HASH_INPUT)

RETURN {
    ontology: UndecidabilityOntology,
    canonical_url: "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/mathematical-logic-ontologies/computability-theory/undecidability-ontology.html",
    parent_domain: ComputabilityTheory,
    semantic_domain: MathematicalLogic,
    primary_entity: Undecidability,
    reduction_reasoning_enabled: TRUE,
    diagonalisation_reasoning_enabled: TRUE,
    Rice_theorem_reasoning_enabled: TRUE,
    relative_computability_enabled: TRUE,
    machine_consumable: TRUE,
    recursive_reasoning_enabled: TRUE,
    database_safe_unicode: TRUE,
    flow_complete: TRUE
}

END_FLOW