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
    Members of the first machine class should be considered r... — Carmelics
    Home/Proof of definition segments
    HistoryEditSee Inverse

    Members of the first machine class should be considered reasonable models of computation for formulating the Cobham-Edmonds Thesis

    All sources support itProof of definition segments
    ?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 first machine class includes the basic Turing machine model and all models satisfying the Invariance Thesis with respect to it, such as multi-tape, multi-head, and RAM models
      ?

      Think about whether this reason is strong or weak

    • 2.Experience has borne out that first machine class members accurately represent the costs of concretely embodied computation
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The Invariance Thesis establishes polynomial equivalence in simulation overhead, but polynomial blowup can be practically significant for real-world computation.
      ?

      Think about whether this reason is strong or weak

    • 2.A model that requires n^6 steps to simulate another's n steps is technically 'reasonable' under the thesis yet computationally intractable in practice.
      ?

      Think about whether this reason is strong or weak

    • 3.The Cobham-Edmonds Thesis requires models that track feasible computation, not merely polynomial-time computation in the abstract mathematical sense.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Parallel computation models like PRAMs and circuit families satisfy the Invariance Thesis yet represent fundamentally different cost structures than sequential Turing machines.
      ?

      Think about whether this reason is strong or weak

    • 2.Hartmanis and Simon demonstrated that parallelism can yield exponential speedups, meaning first machine class membership fails to capture the true cost of physically realizable computation.
      ?

      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

    Proof of definition segmentsAll sources support it

    Connections

    1 topic

    Truth & Knowledge2 linked

    Related

    A model that requires n^6 steps to simulate another's n steps is technically 're...Experience has borne out that first machine class members accurately represent t...Hartmanis and Simon demonstrated that parallelism can yield exponential speedups...Parallel computation models like PRAMs and circuit families satisfy the Invarian...
    +3 moreShow less
    The Cobham-Edmonds Thesis requires models that track feasible computation, not m...The Invariance Thesis establishes polynomial equivalence in simulation overhead,...The first machine class includes the basic Turing machine model and all models s...

    Similar

    Members of the first machine class are reasonable models of computatio...99%Experience has borne out that members of the first machine class are r...91%The first machine class includes the basic Turing machine model and al...85%The class P is defined relative to the deterministic Turing machine mo...84%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    1 Deterministic and non-deterministic models of computation According to the Cobham-Edmonds Thesis the complexity class \(\textbf{P}\) describes the class of feasibily decidable problems. As we have just seen, this class is defined in terms of the reference model \(\mathfrak{T}\) in virtue of the assumption that it is a ‘reasonable’ model of computation. Several other models of computation are also studied in complexity theory not because they are presumed to be accurate representations of the c
    Extraction notes

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

    Details

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