On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics

DOI10.2307/2275906zbMath0805.03047OpenAlexW2091280099MaRDI QIDQ4314669

Samuel R. Buss

Publication date: 27 November 1994

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2275906

zbMATH Keywords

PRAself-referential sentenceslower bounds for proof lengthHilbert-style calculiproof speedup

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Second- and higher-order arithmetic and fragments (03F35) Complexity of proofs (03F20)

Related Items

The lengths of proofs: Kreisel's conjecture and Gödel's speed-up theorem, TRUTH AND SPEED-UP, Generalizing proofs in monadic languages (with a postscript by Georg Kreisel)., On sets, types, fixed points, and checkerboards, Naturalizing indispensability: a rejoinder to `The varieties of indispensability arguments', Deflationary truth and pathologies, Von Neumann, Gödel and Complexity Theory, GEOMETRIC SPIN HALL EFFECT FOR GAUSSIAN BEAM, Bounded arithmetic, proof complexity and two papers of Parikh, 2005 Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '05

Cites Work

• Sentences undecidable in formalized arithmetic. An exposition of the theory of Kurt Gödel