Gödel and computations: a 100th anniversary retrospective

ABSTRACT

I will start with a brief biographical sketch. Kurt Gödel was born in Brno (Brün in German) in April 28, 1906. At that time it was in the Czech Kingdom which was a part of Austro-Hungarian Monarchy. Not much later, in 1918, Brno was a city in the new formed Czechoslovakia. His family belonged to a large German-speaking population in Brno.

REFERENCES

• 1: Stephen A. Cook, Feasibly constructive proofs and the propositional calculus (Preliminary Version), Proceedings of seventh annual ACM symposium on Theory of computing, p.83-97, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803756]
• 2: H. Friedman, On the consistency, completeness and correctness problems, preprint, Ohio State Univ., 1979.
• 3: K. Gödel, Über die Vollständigkeit des Logikkalkül. Dissertation, Universität Wien, 1929.
• 4: K. Gödel, Über formal unentscheidbare Sätze der Principia mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik 38, 1931, 173--198.
• 5: K. Gödel, Über die Länge von Beweisen. Ergebnisse eines mathematischen Kolloquiums 7, 1936, 23--24.
• 6: K. Gödel, Collected works I.--V. Eds., Feferman, Dawson, Kleene, Moore, Solovay, van Heijenoort, Oxford Univ. Press, Clarendon Press, Oxford, 1986--2003.
• 7: S. Kleene, Origins of recursive function theory. Annals of the History of Computing 3, (1981), 52--67.
• 8: J. Krajíček, P. Pudlák, Propositional proof systems, the consistency of first order theories and the complexity of computations. JSL Vol.54, No.3, 1989, 1063--1079.
• 9: J. Krajíček, P. Pudlák, Quantified propositional calculi and fragments of bounded arithmetic. Zeitschrift fur Math. Logik 36, 1990, 29--46.
• 10: J. Malina, J. Novotný editors, Kurt Gödel. UNIVERSITAS MASARYKIANA FOUNDATION, 1996.
• 11: P. Pudlák, On the length of proofs of finitistic consistency statements in first order theories, in Logic Colloquium'84, eds. J. B. Paris, A. J. Wilkie and G. M. Wilmers, North-Holland, 1986, 165--196.
• 12: C. Smoryński, Logical Number Theory I, An Introduction. Springer-Verlag, 1991.
• 13: M. Yasugi, N. Passell, Memoirs of a Proof Theorist, Gödel and other Logicians. World Scientific, 2003.