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
    Reasonable models of computation can simulate each other ... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Modality & Possibility
    HistoryEditSee Inverse

    Reasonable models of computation can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space (Invariance Thesis).

    All sources support itModality & Possibility
    ?Rate how convincing each reason is below to see the overall strength.
    2 reasons for
    2 reasons against

    Next step

    Based on where you are in your exploration

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

    Sign in or register to share your perspective on this statement.

    Reasons For

    2 perspectives
    Reason for 1 of 2
    ?
    • 1.A RAM machine can simulate a Turing machine with time overhead O(t(n)^3) and space overhead O(s(n)).
      ?

      Think about whether this reason is strong or weak

    • 2.Efficient simulations between a wide class of computation models—including Turing machine variants with multiple heads, tapes, and auxiliary storage—have been found.
      ?

      Think about whether this reason is strong or weak

    • 3.Showing that model M1 simulates model M2 yields explicit time and space overhead functions extractable from the simulation construction.
      ?

      Think about whether this reason is strong or weak

    Reason for 2 of 2
    ?
    • 1.Demonstrating that two computational models compute the same class of functions requires constructing a simulation where each basic step of one model is simulated by one or more steps of the other.
      ?

      Think about whether this reason is strong or weak

    • 2.From the definition of a simulation between models, time and space overhead functions can be extracted such that computations in one model can be reproduced in another within those overhead bounds.
      ?

      Think about whether this reason is strong or weak

    • 3.Efficient simulations between models such as RAM machines and Turing machines have been concretely found, with overhead bounds of O(t(n)^3) in time and O(s(n)) in space (Slot and Emde Boas 1988).
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The Invariance Thesis is a stipulative definition of 'reasonable model,' not an empirically discovered invariant, making it circular.
      ?

      Think about whether this reason is strong or weak

    • 2.Models like quantum computers or analog machines with real-valued states are excluded by fiat, not by principled argument.
      ?

      Think about whether this reason is strong or weak

    • 3.Bernstein and Vazirani (1997) showed quantum computers solve certain problems with exponential speedup, violating polynomial simulation bounds.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.The O(t(n)^3) simulation overhead between RAM machines and Turing machines conflates physical resource costs with abstract step counts.
      ?

      Think about whether this reason is strong or weak

    • 2.Slot and van Emde Boas (1988) themselves noted that space measures are not robustly invariant across models, undermining the thesis's universality.
      ?

      Think about whether this reason is strong or weak

    Topics

    Modality & PossibilityAll sources support it

    Connections

    2 topics

    Truth & Knowledge5 linkedCausation1 linked

    Related

    A RAM machine can simulate a Turing machine with time overhead O(t(n)^3) and spa...Bernstein and Vazirani (1997) showed quantum computers solve certain problems wi...Demonstrating that two computational models compute the same class of functions ...Efficient simulations between a wide class of computation models—including Turin...
    +7 moreShow less
    Efficient simulations between models such as RAM machines and Turing machines ha...From the definition of a simulation between models, time and space overhead func...

    Similar

    The Invariance Thesis holds that reasonable models can simulate each o...87%From the definition of a simulation between models, time and space ove...87%Efficient simulations between models such as RAM machines and Turing m...83%A RAM machine can be simulated by a Turing machine with only polynomia...83%

    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

    Models like quantum computers or analog machines with real-valued states are exc...
    Showing that model M1 simulates model M2 yields explicit time and space overhead...
    Slot and van Emde Boas (1988) themselves noted that space measures are not robus...
    The Invariance Thesis is a stipulative definition of 'reasonable model,' not an ...
    The O(t(n)^3) simulation overhead between RAM machines and Turing machines confl...
    Type
    claim
    Perspectives
    4 (2 for, 2 against)
    Edits
    1 edit