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
    The RAM machine model does not provide an asymptotically ... — Carmelics
    Home/Modality & Possibility
    HistoryEditSee Inverse

    The RAM machine model does not provide an asymptotically superior model of feasible computation compared to the Turing machine model.

    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.Although a RAM machine can access any register in a single step while a Turing machine moves one cell at a time, suggesting RAM is more efficient,
      ?

      Think about whether this reason is strong or weak

    • 2.A RAM machine can be simulated by a Turing machine with only polynomial time overhead (O(t(n)^3)) and constant space overhead.
      ?

      Think about whether this reason is strong or weak

    • 3.Polynomial overhead in simulation is acceptable under the feasibility framework, so the two models are equivalent for the purpose of classifying feasible problems.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The polynomial simulation bound (O(t(n)^3)) is not practically negligible: a cubic overhead can transform tractable problems into intractable ones for real inputs.
      ?

      Think about whether this reason is strong or weak

    • 2.The feasibility thesis equates 'polynomial time' with tractability, but this conflation (criticized by Parberry, Gurevich) smuggles in an empirical claim as a definitional truth.
      ?

      Think about whether this reason is strong or weak

    • 3.If the equivalence of RAM and TM depends on accepting polynomial overhead as costless, the argument is circular: it presupposes the very feasibility thesis it is meant to ground.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.RAM machines with uniform cost measure capture the actual complexity of arithmetic operations on bounded integers in a way Turing machines structurally cannot replicate without distortion.
      ?

      Think about whether this reason is strong or weak

    • 2.Hartmanis and Simon demonstrated that certain number-theoretic algorithms are genuinely more efficient on RAM models, suggesting the asymptotic equivalence masks model-relative complexity differences.
      ?

      Think about whether this reason is strong or weak

    • 3.A model of computation that systematically misrepresents the cost structure of arithmetic operations cannot be asymptotically equivalent in any epistemically robust sense.
      ?

      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

    Related

    A RAM machine can be simulated by a Turing machine with only polynomial time ove...A model of computation that systematically misrepresents the cost structure of a...Although a RAM machine can access any register in a single step while a Turing m...Hartmanis and Simon demonstrated that certain number-theoretic algorithms are ge...
    +5 moreShow less
    If the equivalence of RAM and TM depends on accepting polynomial overhead as cos...Polynomial overhead in simulation is acceptable under the feasibility framework,...RAM machines with uniform cost measure capture the actual complexity of arithmet...The feasibility thesis equates 'polynomial time' with tractability, but this con...The polynomial simulation bound (O(t(n)^3)) is not practically negligible: a cub...

    Similar

    A PRAM machine is not a reasonable model of computation87%PRAM machines are not considered a reasonable model of computation87%Non-deterministic Turing machines cannot serve as a practical model of...81%The standard Turing machine model corresponds to a special case of the...81%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    e. that of effective computability. It is also natural to ask whether the concept of feasible computability described in Section 1 itself admits a mathematical analysis similar to Church’s Thesis. We saw above that \(\sc{FACTORIZATION}\) is an example of a problem of antecedent mathematical and practical interest for which more efficient algorithms have historically been sought. The task of efficiently solving combinatorial problems of the sort exemplified by \(\sc{TSP}\), \(\sc{INTEGER}\
    Extraction notes

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

    Details

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