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

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

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

    Reasons For

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

    Reasons Against

    1 perspective
    Reason against
    ?
    • 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

    Next step

    Based on where you are in your exploration

    Strongest counterpoint
    Explore the most compelling reason on the other side.