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
    There is a fundamental tension between treating logical k... — Carmelics
    Home/Skepticism
    HistoryEditSee Inverse

    There is a fundamental tension between treating logical knowledge as a priori and the computational intractability of deciding logical validity.

    SkepticismTruth & Knowledge
    ?Rate how convincing each reason is below to see the overall strength.
    2 reasons for
    1 reason against

    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.

    Reasons For

    2 perspectives
    Reason for 1 of 2
    ?
    • 1.Kant's notion of a priori knowledge requires independence from experience, not computational accessibility or feasibility for finite minds.
      ?

      Think about whether this reason is strong or weak

    • 2.Frege and early logicists grounded logical truth in objective conceptual relations, not in agents' capacity to verify those truths algorithmically.
      ?

      Think about whether this reason is strong or weak

    • 3.If a priori status required computational tractability, mathematical truths like Fermat's Last Theorem would lose their a priori character before proof, which is absurd.
      ?

      Think about whether this reason is strong or weak

    Reason for 2 of 2
    ?
    • 1.Chalmers' epistemic two-dimensionalism distinguishes ideal rational reflection from cognitively bounded reflection, making a priori truth an idealized notion.
      ?

      Think about whether this reason is strong or weak

    • 2.Cognitive limitations of finite agents, as Harman argues in 'Change in View', are constraints on belief revision, not on the modal status of the truths themselves.
      ?

      Think about whether this reason is strong or weak

    • 3.Therefore, computational intractability reveals a gap between idealized logical omniscience and real epistemic agents, confirming rather than dissolving the tension the claim identifies.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    1 perspective
    Reason against
    ?
    • 1.Knowledge of logical validities is a paradigm case of a priori knowledge.
      ?

      Think about whether this reason is strong or weak

    • 2.If logical knowledge is a priori, normal epistemic agents should be credited with knowledge of the logically valid sentences of systems such as propositional and first-order logic that underlie everyday reasoning.
      ?

      Think about whether this reason is strong or weak

    • 3.Deciding whether a formula is a validity of even the weakest familiar logical systems is computationally intractable.
      ?

      Think about whether this reason is strong or weak

    Topics

    SkepticismTruth & Knowledge

    Key Terms

    knowledge(Distinguished from mere true belief, which may be the product of indoctrination and need not exercise deliberative capacities.)
    Justified true belief — true belief that has been arrived at through the exercise of deliberative capacities, including comparison of and deliberation among alternatives.

    Notable Defenders

    A.P. SistlacontemporarySistla and Clarke 1985
    Adam MortoncontemporaryMorton 2004; 2012
    Adam MortoncontemporaryMorton 2004; 2012
    Adam MortoncontemporaryMorton (2004; 2012)
    Adam MortoncontemporaryMorton 2004; 2012
    Alan CobhamcontemporaryCobham 1965
    Alan CobhamcontemporaryCobham 1965
    Alan CobhamcontemporaryCobham 1965
    Alan CobhamcontemporaryCobham (1965)
    Alan CobhamcontemporaryCobham 1965 — algebraic characterization of FP via limited recursion on notation
    Alan CobhamcontemporaryCobham-Edmonds Thesis
    Alan CobhamcontemporaryCobham (1965)
    Alan CobhamcontemporaryCobham-Edmonds Thesis
    Alan CobhamcontemporaryCobham-Edmonds Thesis
    Alan TuringcontemporaryTuring 1937
    Alasdair UrquhartcontemporaryUrquhart 1984
    Alexander RazborovcontemporaryRazborov and Rudich 1994
    Alexander Yessenin-Volpincontemporary
    Alexander Yessenin-VolpincontemporaryYessenin-Volpin 1961; 1970
    Alexander Yessenin-VolpincontemporaryYessenin-Volpin (1970)
    Alonzo Churchcontemporary
    Amos TverskycontemporaryTversky and Kahneman 1974
    Amos TverskycontemporaryTversky and Kahneman 1974
    Amos TverskycontemporaryTversky and Kahneman (1974)
    Amos TverskycontemporaryTversky and Kahneman 1974
    Anne Sjerp TroelstracontemporaryTroelstra and Schwichtenberg 2000
    Ariel RubinsteincontemporaryRubinstein 1998
    Ariel RubinsteincontemporaryRubinstein 1998
    Ariel RubinsteincontemporaryRubinstein (1998)
    Ariel RubinsteincontemporaryRubinstein 1998
    Armin HakencontemporaryHaken (1985)
    ArtemovcontemporaryArtemov and Kuznets 2014
    Bellantoni and CookcontemporaryBellantoni and Cook (1992)
    Bernard ChazellecontemporaryChazelle and Monier (1983)
    Brookshear et al.contemporaryBrookshear et al. 2006
    BusscontemporaryBuss 1987
    BusscontemporaryBuss (1987, 2012)
    Charles LeisersoncontemporaryCormen, Leiserson, and Rivest (2005)
    ChazellecontemporaryChazelle and Monier (1983)
    ChazellecontemporaryChazelle and Monier (1983)
    ChazellecontemporaryChazelle and Monier (1983)
    CherniakcontemporaryCherniak 1981; 1984; 1986
    Christopher CherniakcontemporaryCherniak 1981; 1984; 1986
    Christopher CherniakcontemporaryCherniak (1981; 1984; 1986)
    Christopher CherniakcontemporaryCherniak 1981; 1984; 1986
    Christos PapadimitrioucontemporaryPapadimitriou 1994
    Christos PapadimitrioucontemporaryPapadimitriou 1994
    Clemens LautemanncontemporaryLautemann 1983
    Clemens LautemanncontemporaryLautemann 1983
    CobhamcontemporaryCobham-Edmonds Thesis
    CobhamcontemporaryDefinition of the class F as a characterization of feasible computability
    CookcontemporaryCook 1971
    CookcontemporaryCook 1972
    CookcontemporaryCook 2006
    Daniel KahnemancontemporaryKahneman 2003; Tversky and Kahneman 1974
    Daniel KahnemancontemporaryKahneman 2003; Tversky and Kahneman 1974
    Daniel KahnemancontemporaryKahneman (2003)
    Daniel KahnemancontemporaryKahneman 2003; Tversky and Kahneman 1974
    Daniel LeivantcontemporaryLeivant 1994
    Daniel LeivantcontemporaryLeivant 1994
    Daniel LeivantcontemporaryLeivant 1994
    Daniel LeivantcontemporaryLeivant 1994
    David DeutschcontemporaryDeutsch 1985
    David DeutschcontemporaryDeutsch 1985
    David DeutschcontemporaryDeutsch (1985)
    David van Dantzigcontemporaryvan Dantzig (1955)
    Dexter KozencontemporaryKozen and Parikh 1981
    Domenico ZambellacontemporaryZambella 1996
    Domenico ZambellacontemporaryZambella 1996
    Domenico ZambellacontemporaryZambella 1996
    Domenico ZambellacontemporaryZambella 1996
    Dummettcontemporary[52]
    E. Allen EmersoncontemporaryEmerson and Jutla 1988
    EdmondscontemporaryCobham-Edmonds Thesis
    Edmund ClarkecontemporarySistla and Clarke 1985; Clarke et al. 1986
    Emde BoascontemporaryEmde Boas (1990)
    Emde BoascontemporaryEmde Boas (1990)
    EmersoncontemporaryEmerson and Jutla 1988
    EmersoncontemporaryEmerson and Jutla 1988
    Emil PostcontemporaryPost 1947
    Fagincontemporary
    FischercontemporaryFischer and Ladner 1979
    FortnowcontemporaryFortnow 2009; Fortnow 2013
    Gandycontemporary
    Gerd GigerenzercontemporaryGigerenzer and Selten 2002
    Gerd GigerenzercontemporaryGigerenzer and Selten 2002
    Gerd GigerenzercontemporaryGigerenzer and Selten (2002)
    Gerd GigerenzercontemporaryGigerenzer and Selten 2002
    Gilbert HarmancontemporaryHarman 1986
    Gilbert HarmancontemporaryHarman 1986
    Gilbert HarmancontemporaryHarman (1986)
    Gilbert HarmancontemporaryHarman 1986
    GreenlawcontemporaryGreenlaw, Hoover, and Ruzzo (1995)
    GreenlawcontemporaryGreenlaw, Hoover, and Ruzzo 1995
    GrovercontemporaryGrover 1996
    H.E. RosecontemporaryRose 1984
    HakencontemporaryHaken 1985
    HakencontemporaryHaken (result on exponential lower bound for resolution proofs of PHP_n)
    HakencontemporaryHaken (1985)
    HalperncontemporaryHalpern and Moses 1992
    Hao WangcontemporaryWang (1958)
    Harry LewiscontemporaryLewis 1980
    Hartley RogerscontemporaryRogers 1987
    Hartley RogerscontemporaryRogers 1987
    Hartley RogerscontemporaryRogers 1987
    Hartley RogerscontemporaryRogers 1987
    HartmaniscontemporaryHartmanis and Stearns 1965
    Hector LevesquecontemporaryLevesque 1984
    Hector LevesquecontemporaryLevesque 1984
    Heinz-Dieter EbbinghauscontemporaryEbbinghaus and Flum 1999 — reference text on descriptive complexity and finite model theory
    Heinz-Dieter EbbinghauscontemporaryEbbinghaus and Flum 1999
    Heinz-Dieter EbbinghauscontemporaryEbbinghaus and Flum 1999
    Helmut SchwichtenbergcontemporaryTroelstra and Schwichtenberg 2000
    Herbert SimoncontemporarySimon 1957; Simon 1972
    Herbert SimoncontemporarySimon 1957; Simon 1972
    Herbert SimoncontemporarySimon 1957; 1972
    Homer and SelmancontemporaryHomer and Selman 2011
    HoovercontemporaryGreenlaw, Hoover, and Ruzzo (1995)
    HoovercontemporaryGreenlaw, Hoover, and Ruzzo 1995
    J.H. BennettcontemporaryBennett 1962
    J.H. BennettcontemporaryBennett 1962
    Jaakko HintikkacontemporaryHintikka 1962
    Jaakko HintikkacontemporaryHintikka 1962
    Jaakko HintikkacontemporaryHintikka 1962
    Jack EdmondscontemporaryEdmonds 1965a; Edmonds 1965b
    Jack EdmondscontemporaryEdmonds (1965a)
    Jack EdmondscontemporaryCobham-Edmonds Thesis
    Jack EdmondscontemporaryEdmonds (1965a)
    Jack EdmondscontemporaryCobham-Edmonds Thesis
    Jack EdmondscontemporaryCobham-Edmonds Thesis
    James H. BennettcontemporaryBennett 1962
    James H. BennettcontemporaryBennett 1962
    Jan Von PlatocontemporaryNegri and Von Plato 2001
    John GillcontemporaryBaker, Gill, and Solovay (1975)
    John GillcontemporaryBaker, Gill, and Solovay (1975)
    John GillcontemporaryBaker, Gill, and Solovay 1975
    John GillcontemporaryBaker, Gill, and Solovay (1975)
    Joseph HalperncontemporaryFagin and Halpern 1988
    Joseph HalperncontemporaryFagin and Halpern 1988
    Joseph HalperncontemporaryHalpern and Moses 1992
    Joseph HalperncontemporaryFagin and Halpern 1988
    Joseph HalperncontemporaryHalpern and Moses 1992
    Juris HartmaniscontemporaryHartmanis and Stearns 1965
    Juris HartmaniscontemporaryHartmanis and Stearns (1965)
    Juris HartmaniscontemporaryHartmanis and Stearns 1965
    Juris HartmaniscontemporaryHartmanis and Stearns (1965), 'On the Computational Complexity of Algorithms'
    Jörg FlumcontemporaryEbbinghaus and Flum 1999; Chen and Flum 2010
    Jörg FlumcontemporaryEbbinghaus and Flum 1999; Chen and Flum 2010
    Jörg FlumcontemporaryEbbinghaus and Flum 1999; Chen and Flum 2010
    KanovichcontemporaryKanovich 1994
    Kapovich et al.contemporaryKapovich et al. 2003
    Kapovich et al.contemporaryKapovich et al. 2003
    Ketan MulmuleycontemporaryMulmuley and Sohoni (2001)
    Ketan MulmuleycontemporaryMulmuley and Sohoni (2001)
    Ketan MulmuleycontemporaryMulmuley and Sohoni 2001
    Ketan MulmuleycontemporaryMulmuley and Sohoni 2001
    KuznetscontemporaryArtemov and Kuznets 2014
    KuznetscontemporaryKuznets 2000
    L. SlotcontemporarySlot and Emde Boas 1988
    LadnercontemporaryLadner 1977
    Lance FortnowcontemporaryFortnow (2009)
    Lance FortnowcontemporaryFortnow 2009; Fortnow 2013
    Lance FortnowcontemporaryFortnow (2009)
    Lance FortnowcontemporaryFortnow 2009
    Lance FortnowcontemporaryFortnow 2009
    Lance FortnowcontemporaryFortnow 2009; Fortnow 2013
    Larry StockmeyercontemporaryStockmeyer 1977
    Larry StockmeyercontemporaryStockmeyer 1977 — characterized the levels of the Polynomial Hierarchy and PH via second-order logics
    Larry StockmeyercontemporaryStockmeyer 1977
    Larry StockmeyercontemporaryStockmeyer 1977 — characterizations of the Polynomial Hierarchy levels and PH via second-order logics
    LautemanncontemporaryLautemann (1983) — proof that BPP is contained in Sigma^P_2
    LeivantcontemporaryLeivant (1994)
    Leonid LevincontemporaryLevin (1973)
    LevesquecontemporaryLevesque 1984
    LichtensteincontemporaryLichtenstein and Sipser (1980)
    Lov GrovercontemporaryGrover 1996
    Lov GrovercontemporaryGrover 1996
    MarxcontemporaryMarx 2007 — described a method for encoding finite structures as finite strings
    Michael DummettcontemporaryDummett (1975)
    Michael DummettcontemporaryDummett observed that two different forms of the classical sorites paradox intervene to show that (i)–(iii) are inconsistent
    Michael Dummettcontemporary
    Michael DummettcontemporaryDummett (1975)
    Michael FischercontemporaryFischer and Ladner 1979
    Michael SipsercontemporarySipser 1992
    Michael SipsercontemporarySipser 1992
    Mikhail KanovichcontemporaryKanovich 1994
    Milind SohonicontemporaryMulmuley and Sohoni 2001
    MoniercontemporaryChazelle and Monier (1983)
    MoniercontemporaryChazelle and Monier (1983)
    MoniercontemporaryChazelle and Monier (1983)
    Moshe VardicontemporaryVardi 1982
    Moshe VardicontemporaryVardi 1982
    Moshe VardicontemporaryVardi 1982 — independently proved P is captured by FO(LFP)
    Moshe VardicontemporaryVardi 1982
    Moshe VardicontemporaryVardi 1982 — independently proved P is captured by FO(LFP) over ordered structures
    Neil ImmermancontemporaryImmerman 1982, 1987, 1999
    Neil ImmermancontemporaryImmerman (1999)
    Neil ImmermancontemporaryImmerman 1982 (P captured by FO(LFP)); Immerman 1987 (NL captured by FO(TC), PSPACE by SO(TC)); Immerman 1999
    Neil ImmermancontemporaryImmerman 1982, 1987, 1999
    Neil ImmermancontemporaryImmerman 1982, 1987, 1999 — characterizations of P, NL, PSPACE, EXP
    Oded GoldreichcontemporaryGoldreich 2010
    PapadimitrioucontemporaryPapadimitriou (1994)
    Parikhcontemporary[51]
    Patrick LincolncontemporaryLincoln et al. 1992; Lincoln 1995
    Paul VitányicontemporaryVitányi (1986)
    Peter ShorcontemporaryShor 1999
    Peter ShorcontemporaryShor 1999
    Peter van Emde Boascontemporaryvan Emde Boas 1990
    Peter van Emde BoascontemporaryEmde Boas (1990)
    Peter van Emde BoascontemporarySlot and Emde Boas (1988); Emde Boas (1990)
    Peter van Emde BoascontemporaryEmde Boas 1990
    Raymond GreenlawcontemporaryGreenlaw, Hoover, and Ruzzo 1995
    Richard DeMillocontemporaryDeMillo and Lipton (1980)
    Richard DeMillocontemporaryDeMillo and Lipton (1980)
    Richard DeMillocontemporaryDeMillo and Lipton 1980
    Richard DeMillocontemporaryDeMillo and Lipton 1980
    Richard FeynmancontemporaryFeynman (1982)
    Richard KarpcontemporaryKarp 1972
    Richard KarpcontemporaryKarp 1972
    Richard KarpcontemporaryKarp (1972) — showed 21 problems to be NP-complete via polynomial-time reductions, including the chain SAT ≤_P 3-SAT ≤_P INDEPENDENT SET ≤_P VERTEX COVER ≤_P HAMILTONIAN PATH ≤_P TSP
    Richard KarpcontemporaryKarp (1972) — original demonstration of TSP completeness via the reduction chain
    Richard KarpcontemporaryKarp 1972
    Richard KarpcontemporaryKarp 1972
    Richard LadnercontemporaryLadner 1977
    Richard LadnercontemporaryLadner 1977
    Richard LiptoncontemporaryDeMillo and Lipton (1980)
    Richard LiptoncontemporaryDeMillo and Lipton (1980)
    Richard LiptoncontemporaryDeMillo and Lipton 1980
    Richard LiptoncontemporaryDeMillo and Lipton 1980
    Richard ReckhowcontemporaryCook and Reckhow (1979)
    Richard StatmancontemporaryStatman 1979
    Richard StearnscontemporaryHartmanis and Stearns 1965
    Richard StearnscontemporaryHartmanis and Stearns (1965)
    Richard StearnscontemporaryHartmanis and Stearns 1965
    Richard StearnscontemporaryHartmanis and Stearns (1965), 'On the Computational Complexity of Algorithms'
    Robert M. SolovaycontemporaryBaker, Gill, and Solovay (1975)
    Robert MilnikelcontemporaryMilnikel 2007
    Robert SolovaycontemporaryBaker, Gill, and Solovay (1975)
    Robert SolovaycontemporaryBaker, Gill, and Solovay (1975)
    Robert SolovaycontemporaryBaker, Gill, and Solovay 1975
    Robert StalnakercontemporaryStalnaker 1991; 1999
    Robert StalnakercontemporaryStalnaker 1991; 1999
    Robert StalnakercontemporaryStalnaker 1991; 1999
    Robin GandycontemporaryGandy (1980)
    RogerscontemporaryRogers 1987
    RogerscontemporaryRogers 1987
    Rohit ParikhcontemporaryParikh 1971
    Rohit ParikhcontemporaryKozen and Parikh 1981
    Rohit ParikhcontemporaryParikh 1971
    Rohit ParikhcontemporaryParikh 1971
    Rohit ParikhcontemporaryParikh 1971
    Rohit ParikhcontemporaryParikh 1971
    Roman KuznetscontemporaryArtemov and Kuznets 2014
    Roman KuznetscontemporaryKuznets 2000
    Roman KuznetscontemporaryArtemov and Kuznets 2014
    Ronald FagincontemporaryFagin 1974
    Ronald FagincontemporaryFagin et al. 1995; Fagin and Halpern 1988
    Ronald FagincontemporaryFagin and Halpern 1988
    Ronald FagincontemporaryFagin et al. 1995
    Ronald FagincontemporaryFagin 1974 — proved NP is captured by SO∃
    Ronald FagincontemporaryFagin 1974
    Ronald FagincontemporaryFagin et al. 1995; Fagin and Halpern 1988
    Ronald FagincontemporaryFagin 1974 — proved NP is captured by SO∃
    Ronald FagincontemporaryFagin et al. 1995
    Ronald RivestcontemporaryCormen, Leiserson, and Rivest (2005)
    RuzzocontemporaryGreenlaw, Hoover, and Ruzzo (1995)
    RuzzocontemporaryGreenlaw, Hoover, and Ruzzo 1995
    Samuel BusscontemporaryBuss 1986
    Samuel BusscontemporaryBuss 1987
    Samuel BusscontemporaryBuss 1986
    Samuel BusscontemporaryBuss (1987); Buss (2012)
    Samuel BusscontemporaryBuss 1986
    Samuel BusscontemporaryBuss 1986
    Samuel BusscontemporaryBuss 1986
    Samuel BusscontemporaryBuss 1999
    Sara NegricontemporaryNegri and Von Plato 2001
    SchorrcontemporarySchorr (1983)
    SchorrcontemporarySchorr (1983)
    SchorrcontemporarySchorr (1983)
    Scott AaronsoncontemporaryAaronson (2003)
    Scott AaronsoncontemporaryAaronson (2003)
    Scott AaronsoncontemporaryAaronson 2003
    Scott AaronsoncontemporaryAaronson 2003
    SegerlindcontemporarySegerlind (2007)
    SegerlindcontemporarySegerlind 2007
    Sergei ArtemovcontemporaryArtemov and Kuznets 2014
    Sergei ArtemovcontemporaryArtemov and Kuznets 2014
    Shai Ben-DavidcontemporaryBen-David and Halevi 1992
    Shai HalevicontemporaryBen-David and Halevi 1992
    ShorcontemporaryShor 1999
    Siegcontemporary
    SipsercontemporarySipser 1992
    SipsercontemporaryLichtenstein and Sipser (1980)
    SistlacontemporarySistla and Clarke 1985
    SistlacontemporarySistla and Clarke 1985
    StatmancontemporaryStatman 1979
    StearnscontemporaryHartmanis and Stearns 1965
    Stephen BellantonicontemporaryBellantoni and Cook 1992
    Stephen BellantonicontemporaryBellantoni and Cook 1992
    Stephen BellantonicontemporaryBellantoni and Cook 1992
    Stephen BellantonicontemporaryBellantoni and Cook 1992
    Stephen CookcontemporaryCook 1971; Cook 1972
    Stephen CookcontemporaryBellantoni and Cook 1992
    Stephen CookcontemporaryCook 1971
    Stephen CookcontemporaryCook 1971
    Stephen CookcontemporaryBellantoni and Cook 1992; Cook and Kolokolova 2001; Cook and Nguyen 2010
    Stephen CookcontemporaryCook 2006
    Stephen CookcontemporaryCook and Reckhow (1979)
    Stephen CookcontemporaryCook and Reckhow (1973)
    Stephen CookcontemporaryBellantoni and Cook 1992; Cook and Kolokolova 2001; Cook and Nguyen 2010
    Stephen CookcontemporaryCook 1971
    Stephen CookcontemporaryCook 1972
    Stephen CookcontemporaryCook and Reckhow (1973)
    Stephen CookcontemporaryCook (1971)
    Stephen CookcontemporaryCook and Kolokolova 2001; Cook and Nguyen 2010
    Stephen CookcontemporaryCook 1971
    Stephen CookcontemporaryCook 2006
    Stephen CookcontemporaryCook 1971
    Steven RudichcontemporaryRazborov and Rudich 1994
    Theodore BakercontemporaryBaker, Gill, and Solovay (1975)
    Theodore BakercontemporaryBaker, Gill, and Solovay (1975)
    Theodore BakercontemporaryBaker, Gill, and Solovay 1975
    Theodore BakercontemporaryBaker, Gill, and Solovay (1975)
    Thomas CormencontemporaryCormen, Leiserson, and Rivest (2005)
    UrquhartcontemporaryUrquhart 1984
    UrquhartcontemporaryUrquhart 1984
    VardicontemporaryVardi 1982
    Veikko RantalacontemporaryRantala 1982
    Veikko RantalacontemporaryRantala 1982
    Veikko RantalacontemporaryRantala 1982
    VitányicontemporaryVitányi (1986)
    VitányicontemporaryVitányi (1986)
    VitányicontemporaryVitányi (1986)
    Wilfried SiegcontemporarySieg (2009)
    Wolfgang LenzencontemporaryLenzen 1978
    Wolfgang LenzencontemporaryLenzen 1978
    Wolfgang LenzencontemporaryLenzen 1978
    Yessenin-VolpincontemporaryYessenin-Volpin (1961; 1970)
    Yiannis MoschovakiscontemporaryMoschovakis 1974
    Yiannis MoschovakiscontemporaryMoschovakis 1974 — foundational work on least fixed-point theory underlying FO(LFP)
    Yiannis MoschovakiscontemporaryMoschovakis 1974
    Yijia ChencontemporaryChen and Flum 2010
    Yoram MosescontemporaryHalpern and Moses 1992
    Yoram MosescontemporaryHalpern and Moses 1992
    Yuri ManincontemporaryManin (1980)
    Yuri MoschovakiscontemporaryMoschovakis 1974 — foundational work on least fixed point theory underlying FO(LFP)
    van Emde Boascontemporaryvan Emde Boas 1990
    van Emde Boascontemporaryvan Emde Boas (1990)
    van Emde Boascontemporaryvan Emde Boas (1990)
    AckermannmodernAckermann 1928
    Alan CobhammodernCobham (1965)
    Alan CobhammodernCobham 1965
    Alan CobhammodernCobham 1965
    Alan CobhammodernCobham-Edmonds thesis (characterization of feasible computation as polynomial-time)
    Alan CobhammodernCobham-Edmonds Thesis
    Alan TuringmodernTuring (1937)
    Alan TuringmodernTuring, A. (1937). On Computable Numbers, with an Application to the Entscheidungsproblem.
    Alan Turingmodern
    Alan TuringmodernTuring (1937)
    Alonzo ChurchmodernChurch 1936a
    Alonzo ChurchmodernChurch (1936a, 1936b)
    Alonzo ChurchmodernChurch 1936a
    Alonzo Churchmodern
    Alonzo ChurchmodernChurch (1936a); Church (1936b)
    BernaysmodernBernays and Schöfinkel 1928
    ChurchmodernChurch 1936a
    ChurchmodernAnalysis of effective computability (Church's thesis)
    David van Dantzigmodernvan Dantzig (1955)
    Donald KnuthmodernKnuth (1973)
    Emil PostmodernPost (1947)
    GödelmodernGödel 1932
    Hartley RogersmodernRogers 1987 — referenced for the Arithmetic Hierarchy in computability theory
    Herbert SimonmodernSimon (1957; 1972)
    Jack EdmondsmodernEdmonds (1965a); Edmonds (1965b)
    Jack EdmondsmodernEdmonds 1965a; Edmonds 1965b
    Jack EdmondsmodernCobham-Edmonds thesis (characterization of feasible computation as polynomial-time)
    Jack EdmondsmodernCobham-Edmonds Thesis
    Kurt GödelmodernGödel (1956), letter to von Neumann, p. 612
    Kurt GödelmodernGödel 1932; Gödel 1986a
    Kurt GödelmodernGödel 1956, letter to John von Neumann, p. 612
    Kurt GödelmodernGödel (1986b)
    Kurt GödelmodernGödel 1956, letter to von Neumann, p. 612
    Kurt GödelmodernGödel 1932; Gödel 1986a
    Kurt GödelmodernGödel's suggestion regarding consequences of P = NP for mathematical provability (referenced in passage)
    Kurt GödelmodernGödel (1986b)
    Kurt GödelmodernGödel 1956, letter to John von Neumann, p. 612
    Leopold LöwenheimmodernLöwenheim 1967
    LöwenheimmodernLöwenheim 1967
    Moses SchönfinkelmodernBernays and Schöfinkel 1928
    Paul BernaysmodernBernays and Schöfinkel 1928
    Paul BernaysmodernBernays (1935)
    Richard BellmanmodernBellman (1962)
    Stephen Cole KleenemodernKleene (1936)
    Stephen KleenemodernKleene (1936)
    TuringmodernAnalysis of effective computability (Turing's thesis)
    Wilhelm AckermannmodernAckermann 1928

    Connections

    1 topic

    Modality & Possibility1 linked

    Related

    Chalmers' epistemic two-dimensionalism distinguishes ideal rational reflection f...Cognitive limitations of finite agents, as Harman argues in 'Change in View', ar...Deciding whether a formula is a validity of even the weakest familiar logical sy...Frege and early logicists grounded logical truth in objective conceptual relatio...

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    Nonetheless, Parikh showed that for appropriate choices of \(\tau\), any proof of a contradiction in \(\mathsf{PA}^F\) must itself be very long. For instance, if we consider the super-exponential function \(2 \Uparrow 0 = 1\) and \(2 \Uparrow (x+1) = 2^{2 \Uparrow x}\) and let \(\tau\) be the primitive recursive term \(2 \Uparrow 2^k\), it is a consequence of Parikh’s result that any proof of a contradiction in \(\mathsf{PA}^F\) must be on the order of \(2^k\) steps long. e. non-vague) property
    Extraction notes

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

    Details

    +6 moreShow less
    If a priori status required computational tractability, mathematical truths like...If logical knowledge is a priori, normal epistemic agents should be credited wit...Kant's notion of a priori knowledge requires independence from experience, not c...Knowledge of logical validities is a paradigm case of a priori knowledge.Therefore, computational intractability reveals a gap between idealized logical ...This intractability is incompatible with the idealization that agents have compl...

    Similar

    There is a fundamental tension between treating logical knowledge as a...99%Knowledge of logical validities is a paradigm case of a priori knowled...85%Logical knowledge—knowledge that certain statements are logical validi...83%Logical knowledge is a paradigm case of a priori knowledge, implying a...81%
    Type
    claim
    Perspectives
    3 (2 for, 1 against)
    Edits
    1 edit