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
    Home/Original/inverse
    See Original
    Inverse View

    It is not the case that Many-one reducibility implies Turing reducibility (A ≤_m B implies A ≤_T B)

    ?Set your confidence on the premises below to see your aggregate.

    Reasons For

    2 perspectives
    Reason for 1 of 2
    ?
    • 1.Many-one reductions preserve the intensional structure of membership queries, while Turing reductions permit adaptive, multi-query oracle access that many-one functions cannot simulate.
      ?

      Think about whether this reason is strong or weak

    • 2.The collapse of ≤_m and ≤_T would entail that every Turing-complete set is also many-one complete, yet Post's construction of simple sets demonstrates Turing-complete sets lacking many-one completeness.
      ?

      Think about whether this reason is strong or weak

    • 3.Therefore the implication is strictly one-directional, and conflating the two reducibilities obscures the finer degree-theoretic distinctions Post's program was designed to expose.
      ?

      Think about whether this reason is strong or weak

    Reason for 2 of 2
    ?
    • 1.The supporting argument assumes the Turing machine can uniformly compute f and consult the oracle in a single non-adaptive query, but this presupposes computability of f that may itself require oracle assistance in relativized settings.
      ?

      Think about whether this reason is strong or weak

    • 2.In constructive and intuitionistic frameworks (following Brouwer and Bishop), the existence of a computable f does not automatically yield an effective procedure without additional choice principles that are not constructively neutral.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    1 perspective
    Reason against
    ?
    • 1.If f(x) is a many-one reduction of A to B, then a Turing machine can compute f(n) and then use B as an oracle to check if f(n) ∈ B, outputting 1 if true and 0 if false
      ?

      Think about whether this reason is strong or weak

    • 2.This procedure constitutes a valid Turing reduction of A to B
      ?

      Think about whether this reason is strong or weak

    Next step

    Based on where you are in your exploration

    Strongest counterpoint
    Explore the most compelling reason on the other side.
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42