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
    Σ^B₁-definability is a syntactic criterion, but polynomia... — Carmelics
    Home
    HistoryEditSee Inverse

    Part of a larger discussion

    Challenges→A function f(x) is in FP if and only if it is definable by a Σ^B₁-formula relative to which it is provably total in V¹

    Σ^B₁-definability is a syntactic criterion, but polynomial-time computability is an extensional, machine-relative notion—Benacerraf's identification problem applies here.

    ?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.Σ^B₁-formulas are purely syntactic; their truth depends only on logical structure, independent of physical implementation.
      ?

      Think about whether this reason is strong or weak

    • 2.Polynomial-time computability varies across machine models (Turing machines, circuits, quantum); it lacks the invariance of syntax.
      ?

      Think about whether this reason is strong or weak

    • 3.Benacerraf showed syntactic and extensional criteria can diverge; identifying them requires bridging distinct ontological categories.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    1 perspective
    Reason against
    ?
    • 1.Both Σ^B₁-definability and polynomial-time computability are model-independent in practice; they're equivalent across standard formalizations.
      ?

      Think about whether this reason is strong or weak

    • 2.The distinction between 'syntactic' and 'extensional' is itself unclear—syntax is extensionally defined as well-formed symbol sequences.
      ?

      Think about whether this reason is strong or weak

    • 3.Benacerraf's problem concerns abstract objects' identity, not reducibility; computational/logical notions don't involve the same epistemic gaps.
      ?

      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

    Truth & Knowledge1 linkedModality & Possibility1 linked

    Related

    A function f(x) is in FP if and only if it is definable by a Σ^B₁-formula relati...Benacerraf showed syntactic and extensional criteria can diverge; identifying th...Benacerraf's problem concerns abstract objects' identity, not reducibility; comp...Both Σ^B₁-definability and polynomial-time computability are model-independent i...
    +3 moreShow less
    Polynomial-time computability varies across machine models (Turing machines, cir...The distinction between 'syntactic' and 'extensional' is itself unclear—syntax i...Σ^B₁-formulas are purely syntactic; their truth depends only on logical structur...

    Details

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