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
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    K is Turing complete among the computably enumerable sets — Carmelics
    Home/Truth & Knowledge
    HistoryEditSee Inverse

    K is Turing complete among the computably enumerable sets

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

    Reasons For

    1 perspective
    Reason for
    ?
    • 1.K is many-one complete among the c.e. sets
      ?

      Think about whether this reason is strong or weak

    • 2.Many-one reducibility implies Turing reducibility
      ?

      Think about whether this reason is strong or weak

    • 3.Therefore any c.e. set is Turing reducible to K
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Many-one completeness establishes K as a ceiling for m-reducibility, but Turing reducibility permits oracle queries that m-reductions structurally forbid.
      ?

      Think about whether this reason is strong or weak

    • 2.The inference from m-completeness to T-completeness conflates degree-theoretic hierarchy levels: m-degrees are strictly finer than T-degrees, so completeness in one does not automatically transfer upward.
      ?

      Think about whether this reason is strong or weak

    • 3.Post's problem demonstrates that intermediate c.e. Turing degrees exist between 0 and 0', meaning T-completeness requires independent justification beyond m-completeness alone.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Turing completeness among c.e. sets requires that K can simulate any c.e. set's membership problem, but this presupposes a fixed model of computation whose universality is not logically necessary.
      ?

      Think about whether this reason is strong or weak

    • 2.Kreisel and Sacks showed that relativized computability contexts admit c.e. sets whose Turing degree structure diverges from the unrelativized case, undermining the generality of K's completeness claim.
      ?

      Think about whether this reason is strong or weak

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

    Next step

    Based on where you are in your exploration

    Strongest counterpoint
    Explore the most compelling reason on the other side.

    Topics

    Truth & KnowledgeProof of definition segments

    Connections

    2 topics

    All sources support it1 linkedModality & Possibility1 linked

    Related

    K is many-one complete among the c.e. setsKreisel and Sacks showed that relativized computability contexts admit c.e. sets...Many-one completeness establishes K as a ceiling for m-reducibility, but Turing ...Many-one reducibility implies Turing reducibility
    +4 moreShow less
    Post's problem demonstrates that intermediate c.e. Turing degrees exist between ...The inference from m-completeness to T-completeness conflates degree-theoretic h...Therefore any c.e. set is Turing reducible to KTuring completeness among c.e. sets requires that K can simulate any c.e. set's ...

    Similar

    K is many-one complete among the c.e. sets79%A logic whose validities are recursively enumerable satisfies abstract...78%A computable set is one decidable by an algorithm that always terminat...78%A consequence of the completeness theorem is that, if formulas of L ar...77%

    Source

    AI-extracted1/3 agreementValid
    SEP: recursive-functions
    View source passageHide passage
    It is easy to see that \(A \leq_m B\) implies \(A \leq_T B\). (For if \(f(x)\) is a \(m\)-reduction of \(A\) to \(B\), then consider the program which first computes \(f(n)\) and then, using \(B\) an as oracle, checks if \(f(n) \in B\), outputting 1 if so and 0 if not.) It thus follows that \(K\) is also Turing complete—i.e., it embodies the maximum “degree of unsolvability” among the the c.e. sets when this notion is understood in terms of Turing reducibility as well as many-one reducibility.
    Extraction notes

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

    Details

    Type
    claim
    Perspectives
    3 (1 for, 2 against)
    Edits
    1 edit