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
    Many-one reducibility implies Turing reducibility (A ≤_m ... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Modality & Possibility
    HistoryEditSee Inverse

    Many-one reducibility implies Turing reducibility (A ≤_m B implies A ≤_T B)

    Modality & Possibility
    ?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.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

    Reasons Against

    2 perspectives
    Reason against 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 against 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

    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

    Modality & PossibilityTruth & Knowledge

    Connections

    2 topics

    All sources support it1 linkedProof of definition segments1 linked

    Related

    If f(x) is a many-one reduction of A to B, then a Turing machine can compute f(n...In constructive and intuitionistic frameworks (following Brouwer and Bishop), th...Many-one reductions preserve the intensional structure of membership queries, wh...The collapse of ≤_m and ≤_T would entail that every Turing-complete set is also ...
    +3 moreShow less
    The supporting argument assumes the Turing machine can uniformly compute f and c...

    Similar

    Many-one reducibility implies Turing reducibility93%NP is closed under polynomial time many-one reducibility, meaning if Y...81%The structure of reducibility among these problems yields at least one...80%Polynomial-time reducibility (≤_P) is transitive80%

    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

    Therefore the implication is strictly one-directional, and conflating the two re...
    This procedure constitutes a valid Turing reduction of A to B
    Type
    claim
    Perspectives
    3 (1 for, 2 against)
    Edits
    1 edit