Skip to content
Carmelics
TopicsThinkersChangesContributorsLoading account…

    Carmelics

    A reasoning platform. Break down any belief into clear reasons, explore both sides, and weigh the evidence honestly.

    Navigate

    • Topics
    • Search
    • Recent Changes
    • Contribute
    • How It Works
    • Glossary
    • Thinkers
    • Contributors
    • About
    • Statistics
    • Terms
    • Privacy

    Database

    Statements
    —
    Perspectives
    —
    Topics
    —

    Press ? for keyboard shortcuts

    LoyalLoyalJusticeJustice
    Made withinDC&Austin
    The Halting Problem is not effectively decidable — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Truth & Knowledge
    HistoryEditSee Inverse

    The Halting Problem is not effectively decidable

    Proof of definition segmentsTruth & Knowledge
    ?Rate how convincing each reason is below to see the overall strength.
    1 reason for
    0 reasons against

    Reasons For

    1 perspective
    Reason for
    ?
    • 1.The characteristic function of the Halting Problem can be proven to be non-recursive
      ?

      Think about whether this reason is strong or weak

    • 2.Any problem whose characteristic function is non-recursive is not effectively decidable
      ?

      Think about whether this reason is strong or weak

    Sign in or register to share your perspective on this statement.

    Topics

    Truth & KnowledgeProof of definition segments

    Connections

    1 topic

    Next step

    Based on where you are in your exploration

    Browse more in Truth & Knowledge
    Related propositions within the same area of thought.
    Modality & Possibility
    1 linked

    Related

    Any problem whose characteristic function is non-recursive is not effectively de...The characteristic function of the Halting Problem can be proven to be non-recur...

    Similar

    If FACTORIZATION is not in P, it is not feasibly decidable.92%FACTORIZATION is not currently known to be feasibly decidable92%If FACTORIZATION is not in P and NP ≠ coNP, then there exist natural m...84%Propositional logic is decidable.83%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    CT can be understood to assign a precise epistemological significance to Church and Turing’s negative answer to the Entscheidungsproblem. For if it is acknowledged that \(\mathcal{F}_{\mathfrak{R}}\) (and hence also \(\mathcal{F}_{\Lambda}\) and \(\mathcal{F}_{\mathfrak{T}}\)) contain all effectively computable functions, it then follows that a problem \(X\) can be shown to be effectively undecidable – i.e. undecidable by any algorithm whatsoever, regardless of its efficiency – by showing that t
    Extraction notes

    Validity: Extracted via Max plan + API grounding/validity checks

    Details

    Type
    claim
    Perspectives
    1 (1 for, 0 against)
    Edits
    1 edit