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
    The justification for classifying specific problems as un... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Skepticism
    HistoryEditSee Inverse

    The justification for classifying specific problems as undecidable can be no stronger than the confidence placed in Church's Thesis.

    SkepticismTruth & 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.Undecidability proofs proceed by showing that the characteristic function of a problem is not recursive.
      ?

      Think about whether this reason is strong or weak

    • 2.The inference from 'not recursive' to 'not effectively decidable' depends entirely on Church's Thesis.
      ?

      Think about whether this reason is strong or weak

    • 3.Church's Thesis is an empirically supported thesis, not a proven mathematical theorem.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.Church's Thesis is not a mere empirical conjecture but is supported by the mutual reducibility of all known models of computation, constituting a form of mathematical convergence evidence distinct from physical induction.
      ?

      Think about whether this reason is strong or weak

    • 2.Gödel, Turing, and Church independently arrived at extensionally equivalent formalizations, and this invariance across disparate formalisms gives the thesis a quasi-definitional status rather than a contingent one.
      ?

      Think about whether this reason is strong or weak

    • 3.A claim whose negation would require positing an effective procedure that resists all known formal characterization bears a burden of proof that skeptical invocation of 'it's just a thesis' does not discharge.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Kreisel's analysis shows undecidability results like the halting problem can be established relative only to the formal system itself, without invoking Church's Thesis as a bridge principle to informal effectivity.
      ?

      Think about whether this reason is strong or weak

    • 2.The diagonal argument in Turing's halting problem proof yields a contradiction within the formal model alone, so the mathematical result stands independently of any claim about informal computation.
      ?

      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

    SkepticismTruth & Knowledge

    Related

    A claim whose negation would require positing an effective procedure that resist...Church's Thesis is an empirically supported thesis, not a proven mathematical th...Church's Thesis is not a mere empirical conjecture but is supported by the mutua...Gödel, Turing, and Church independently arrived at extensionally equivalent form...
    +4 moreShow less
    Kreisel's analysis shows undecidability results like the halting problem can be ...The diagonal argument in Turing's halting problem proof yields a contradiction w...The inference from 'not recursive' to 'not effectively decidable' depends entire...Undecidability proofs proceed by showing that the characteristic function of a p...

    Similar

    No decision can be assured as just because the ordeal of undecidabilit...82%Hilbert's general aim of solving every mathematical problem underpins ...79%The undetectability of a skeptical scenario does not by itself show th...79%K is undecidable79%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    , Immerman 1999). Like computational complexity theory, descriptive complexity theory also seeks to classify the complexity of infinite sets of combinatorial objects. However, the ‘complexity’ of a problem is now measured in terms of the logical resources which are required to define its instances relative to the class of all finite structures for an appropriate signature. 4 this approach often yields alternative characterizations of the same classes studied in computational complexity theory. g
    Extraction notes

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

    Details

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