Page 160 - Textos de Matemática Vol. 40

148 Appendix
lectures he gave later on on this topic52. It is known that he left this line of research immediately after the discovery of G¨odel’s result53, but this does not mean that his work on the foundations of mathematics did not find its way into his pioneering work on computer models. It might even include the possibility of self-application in a computational model.
With respect to all four researchers we have no reason to assume that Hilbert discussed his alleged base of the paradoxes of 1905 with any of them directly. However, they all had access to the lecture notes of 1905 which were kept in the Lesezimmer (reading room) of the library in the Mathematical Insti- tuteinG¨ottingen.54 Havinginmindtheliteratureonmathematicallogicofthat time, it seems to be quite reasonable that one would consult these lecture notes in course of work in this area. Thus, it is not impossible that Scho¨nfinkel, Curry, Church and/or von Neumann came across Hilbert’s paragraph with the use of self-application and that it served as an inspiration for further work.
A.6 Undecidability results
Mathematically the definition of Hilbert’s paradoxical function is of interest since it has the structure used in modern undecidability proofs. The first unde- cidability results are due to Church [Chu36] and Alan Turing (1912–1954) [Tur36] answering negatively Hilbert’s Entscheidungsproblem for the first order predicate calculus. In both proofs, the essential technical step involves a form of diagonalization. Rephrasing the Entscheidungsproblem as the halting prob- lem (for, e.g., Turing machines), the proof may nowadays be carried out with relative ease by diagonalizing, for instance, over the index and the argument of a universal function (universal for the partial recursive functions), see e.g., [BJ80, Chapter 5, in particular p. 47]. In some cases (or presentations) this diagonalization is, in fact, implemented by a self-application. We would like to present here one instance, which comes extremely close to Hilbert’s paradoxical function.
Inspired by a “2-minute proof” of the undecidability of the halting prob- lem by Doron Zeilberger55, Nachum Dershowitz gave the following “full
52For von Neumann’s activities as lecturer in Berlin and Hamburg in 1928–1932 cf. [Has06b]. We just mention that, in 1928, he was appointed at the university of Berlin to lecture on the foundations of mathematics, and the list of lectures includes one called Hilbertsche Beweis- theorie (Hilbertian proof theory) [Has06b, p. 228].
53He was in the audience when Kurt Go¨del (1906–1978) first presented his First Incom- pleteness Theorem in public at a conference in K¨onigsberg, and independently he even derived the Second Incompleteness Theorem from it, cf. the first two letters published in the corre- spondence of Go¨del [G¨od03, p. 336–341] and the introduction to this correspondence [Sie03].
54Even today all official lectures notes of Hilbert are still accessible in this library.
55Doron Zeilberger. A 2-minute proof of the 2nd most important theorem of the 2nd millen- nium, http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/halt.html, October 1998.