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
    Adding non-determinism to the deterministic Turing machin... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Modality & Possibility
    HistoryEditSee Inverse

    Adding non-determinism to the deterministic Turing machine model does not enlarge the class of decidable problems

    Modality & PossibilityTruth & 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.The class of problems decidable by non-deterministic Turing machines is exactly the recursive problems
      ?

      Think about whether this reason is strong or weak

    • 2.The class of problems decidable by deterministic Turing machines is also exactly the recursive problems
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The identification of 'decidability' with recursive enumerability presupposes Church-Turing Thesis, which remains a thesis, not a proven theorem.
      ?

      Think about whether this reason is strong or weak

    • 2.If hypercomputation models (Malament-Hogarth spacetimes, accelerating Turing machines) are physically realizable, non-determinism may access super-recursive classes unavailable to standard DTMs.
      ?

      Think about whether this reason is strong or weak

    • 3.Equating both models to 'recursive problems' inherits the thesis's assumption that no physically possible process exceeds Turing-computable functions.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.The proof of NTM-DTM decidability equivalence relies on simulation arguments that collapse non-deterministic branching into deterministic search, preserving halting but not computational meaning.
      ?

      Think about whether this reason is strong or weak

    • 2.Philosophical accounts of non-determinism rooted in quantum indeterminacy or modal realism (Lewis) treat branching as ontologically irreducible, not merely epistemically unexplored.
      ?

      Think about whether this reason is strong or weak

    • 3.If non-deterministic choice is genuinely ontological rather than epistemic, the simulation argument conflates decision-theoretic equivalence with metaphysical equivalence of computational process.
      ?

      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

    1 topic

    All sources support it1 linked

    Related

    Equating both models to 'recursive problems' inherits the thesis's assumption th...If hypercomputation models (Malament-Hogarth spacetimes, accelerating Turing mac...If non-deterministic choice is genuinely ontological rather than epistemic, the ...Philosophical accounts of non-determinism rooted in quantum indeterminacy or mod...
    +4 moreShow less
    The class of problems decidable by deterministic Turing machines is also exactly...The class of problems decidable by non-deterministic Turing machines is exactly ...The identification of 'decidability' with recursive enumerability presupposes Ch...The proof of NTM-DTM decidability equivalence relies on simulation arguments tha...

    Similar

    The class of problems decidable by non-deterministic Turing machines i...85%Every deterministic Turing machine is by definition a non-deterministi...84%The second machine class contains deterministic models that can effici...83%The class of problems decidable by deterministic Turing machines is al...83%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    As \(\phi \in \sc{SAT}\) just in case a satisfying valuation exists, this is a correct method for deciding \(\sc{SAT}\) relative to conventions (i)–(iii) from above. This means that \(\sc{SAT}\) can be solved in polynomial time relative to \(\mathfrak{N}\). This example also illustrates why adding non-determinism to the original deterministic model \(\mathfrak{T}\) does not enlarge the class of decidable problems. [12] It is evident that if \(N\) has time complexity \(f(n)\), then \(T_N\) must
    Extraction notes

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

    Details

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