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 space hierarchy theorem's proof relies on a diagonali... — Carmelics
    Home
    HistoryEditSee Inverse

    Part of a larger discussion

    Challenges→SPACE(s1(n)) is a proper subset of SPACE(s2(n)) when s2(n) grows sufficiently faster than s1(n)

    The space hierarchy theorem's proof relies on a diagonalization argument that presupposes a universal TM can simulate any TM with bounded overhead.

    ?Rate how convincing each reason is below to see the overall strength.
    1 reason for
    1 reason against

    Reasons For

    1 perspective
    Reason for
    ?
    • 1.Universal TMs can simulate any TM; this is Church-Turing thesis, foundational to computability theory.
      ?

      Think about whether this reason is strong or weak

    • 2.The overhead is bounded by a constant factor plus logarithmic terms; proven constructively in standard references.
      ?

      Think about whether this reason is strong or weak

    • 3.Diagonalization requires this simulation property to construct a TM exceeding any resource bound, making the argument valid.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    1 perspective
    Reason against
    ?
    • 1.The 'bounded overhead' claim conflates worst-case and average-case complexity; overhead varies by TM structure.
      ?

      Think about whether this reason is strong or weak

    • 2.Space hierarchy's proof doesn't strictly require bounded simulation—relative separation suffices without tight overhead bounds.
      ?

      Think about whether this reason is strong or weak

    • 3.Presupposing bounded overhead risks circularity: we assume what space hierarchy aims to establish about resource separability.
      ?

      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.

    Connections

    2 topics

    All sources support it1 linkedProof of definition segments1 linked

    Related

    Diagonalization requires this simulation property to construct a TM exceeding an...Presupposing bounded overhead risks circularity: we assume what space hierarchy ...SPACE(s1(n)) is a proper subset of SPACE(s2(n)) when s2(n) grows sufficiently fa...Space hierarchy's proof doesn't strictly require bounded simulation—relative sep...
    +3 moreShow less
    The 'bounded overhead' claim conflates worst-case and average-case complexity; o...The overhead is bounded by a constant factor plus logarithmic terms; proven cons...Universal TMs can simulate any TM; this is Church-Turing thesis, foundational to...

    Details

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