The lengths of proofs: Kreisel’s conjecture and Gödel’s speed-up theorem

0422281 - MÚ 2014 RIV US eng J - Článek v odborném periodiku
Cavagnetto, Stefano
The lengths of proofs: Kreisel’s conjecture and Gödel’s speed-up theorem.
Journal of Mathematical Sciences. Roč. 158, č. 5 (2009), s. 689-707. ISSN 1072-3374
Grant CEP: GA AV ČR IAA1019401
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: Kreisel Georg * Gödel
Kód oboru RIV: BA - Obecná matematika
http://link.springer.com/article/10.1007/s10958-009-9408-0

We collect and compare several results that have been obtained so far in the attempts to prove a statement conjectured by Kreisel about the lengths of proofs. We also survey several results regarding a speed-up theorem announced by Gödel in an abstract published in 1936, Finally, we connect this to Kreisel’s conjecture.
Trvalý link: http://hdl.handle.net/11104/0228471