Godel and the Origins of Computer Science

G¨odel and the Origins of Computer Science
John W. Dawson Jr.
Penn State York
1031 Edgecomb Avenue
York PA 17403, U.S.A.
[email protected]
Abstract. The centenary of Kurt G¨odel (1906–78) is an appropriate
occasion on which to assess his profound, yet indirect, influence on the
development of computer science. His contributions to and attitudes to-
ward that field are discussed, and are compared with those of other pi-
oneer figures such as Alonzo Church, Emil Post, Alan Turing, and John
von Neumann, in order better to understand why G¨odel’s role was no
greater than it was.
Kurt G¨ odel’s impact on the development of computer science was at once semi-
nal and indirect. His (first) incompleteness theorem, published in 1931 and later
recast by Alan Turing in the guise of the Halting Problem, established bounds on
what is and is not computable (and more recently, has been invoked to demon-
strate that there can be no perfect virus checker [5]). In proving that theorem,
G¨ odel gave a precise definition of the class of functions now called primitive
recursive, which he employed in a way that, as Martin Davis ([4], 120) has re-
marked, “looks very much like a computer program” and anticipated “many of
the issues that those designing [and using] programming languages” would later
face. Furthermore, he introduced the fundamental technique of arithmetization
of syntax (“G¨ odel-numbering”) — the first explicit instance in which one mathe-
matical data type (that of syntax) was represented by another (that of numbers)
for the purpose of computation.
During the years 1932–33, before the enunciation of Church’s Thesis, G¨ odel
published two papers on decision problems for formulas of the predicate calcu-
lus, in one of which he established both that the validity of prenex formulas in
one prefix class is a decidable question, and that for an arbitrary formula, the
decision problem for validity is reducible to that of formulas in another such
prefix class. Then in 1934, in a series of lectures at the Institute for Advanced
Study, he went on to define the notion of general recursive function — one of
several definitions that were later proved to be equivalent and adduced as evi-
dence for Church’s Thesis.
1
Nevertheless, G¨ odel was a bystander in the further
development of recursion theory. He came to accept Church’s Thesis only in the
wake of Turing’s characterization of abstract computing machines, and despite
1
G¨odel’s definition was based on a suggestion of Jacques Herbrand, which Herbrand
communicated to G¨ odel shortly before his own untimely death in a mountaineering
accident. See [15] for a detailed analysis of that correspondence.
A. Beckmann et al. (Eds.): CiE 2006, LNCS 3988, pp. 133–136, 2006.
c Springer-Verlag Berlin Heidelberg 2006
134 J.W. Dawson Jr.
his presence at the Institute for Advanced Study — where von Neumann and
others developed one of the earliest digital computing machines — he was never
involved in the physical realization of computers (nor, as Turing and von Neu-
mann were, with their applications to problems in ballistics, cryptography, or
the development of nuclear weapons).
Similarly, in 1936, in his short note [7], G¨ odel stated an instance of what,
thirty years afterward, would be called a “speed-up” theorem — a topic that
subsequently became a major focus of research in computational complexity the-
ory. But he gave no proof of the result he stated there and did not pursue the
idea further. In 1956, however, he raised a related issue in a letter to von Neu-
mann
2
(then terminally ill and unable to reply) — a question closely related to
the P = NP problem that is today the central problem in theoretical computer
science.
3
During his early years in Princeton G¨ odel was in contact with several of the
pioneers of recursion theory, including Stephen C. Kleene, J. Barkley Rosser,
and Alonzo Church, and he also had correspondence with Emil Post, who had
come close to anticipating the incompleteness theorem twenty years before G¨ odel
and whose approach to recursion theory foreshadowed the later development of
automata theory. Regrettably, however, after G¨ odel’s emigration in 1940 there
is little documentary evidence to indicate how extensive his interaction was with
those, such as Church and von Neumann, who lived nearby.
Turing, too, was in Princeton during the years 1936–38, working on his doc-
torate. But G¨odel was away then, incapacitated by an episode of depression, and
by the time he recovered Turing had returned to Britain and become involved
with the ultra-secret cryptographic work at Bletchley Park. That, and Turing’s
untimely death in 1954, is no doubt the reason the two never met. Surprisingly,
however — especially in view of their shared interest in the question whether
the capabilities of the human mind exceed those of any machine — they seem
never to have corresponded either.
In that regard, the contrast between G¨odel’s views and those of Post and
Turing is stark. For whereas Post sought to establish the existence of absolutely
unsolvable problems, in his Gibbs Lecture to the American Mathematical Society
in 1951 G¨ odel maintained that the incompleteness theorems imply either that
“the human mind . . . infinitely surpasses the powers of any finite machine” or
that “there exist absolutely unsolvable Diophantine problems”. (He did not fall
into the error, first advanced by J.R. Lucas and subsequently by Roger Penrose,
of asserting that the incompleteness theorems definitively refute mechanism; but
it is clear that he believed the first alternative in the above disjunction to be the
correct one.) And though, in a note he added in 1963 to the English translation
of his incompleteness paper, G¨ odel conceded that Turing’s work had provided “a
precise and unquestionably adequate definition of the general notion of formal
2
Published in [13], 372–375.
3
See [14]. The claims G¨odel made in his 1936 paper and in his letter to von Neumann
attracted notice only posthumously. They were first verified by Samuel Buss in the
1990s. See in particular [1].
G¨odel and the Origins of Computer Science 135
system” — systems in which “reasoning . . . , in principle, can be completely
replaced by mechanical devices” — he later maintained
4
that Turing had erred
in arguing that “mental procedures cannot go beyond mechanical procedures.”
Specifically, G¨odel claimed that Turing had overlooked that the human mind
“in its use, is not static but constantly developing.” He argued that though at
each stage of its development “the number and precision of the abstract terms at
our disposal may be finite”, in the course of time both might “converge toward
infinity”, whence so might the “number of distinguishable states of mind” that
Turing had invoked in his analysis.
That criticism of Turing, however, seems quite unfounded. For between the
years 1948 and 1952 Turing had written and lectured on several occasions
5
on the
question whether machines can be said to think. He had proposed a criterion —
the so-called “Turing test” — for judging whether or not they do, had cogently
rebutted many of the arguments adduced to show that they cannot (including
those based on the incompleteness theorems), and had stressed the possibility
of designing machines that would, like the human mind, be capable of learning.
Overall, then, how ought G¨ odel’s role in the development of computer science
to be assessed? Certainly, he introduced many crucial theoretical ideas; and his
prescience, concerning such matters as the representation of data types and the
significance of questions related to the P = NP problem, is truly remarkable.
6
He did not contribute to the further development of many of those ideas, but
that is in accord with his other mathematical work (in set theory, for example):
He was a path-breaker, eager to move on to new conquests while leaving follow-
up work to others; and his orientation was predominantly philosophical rather
than practical.
Indeed, in many respects G¨ odel was quite otherworldly, and some of his pro-
nouncements seem remarkably naive — such as his statement, in the Gibbs
Lecture, that if there are absolutely undecidable propositions, then mathemat-
ics must not be a creation of the human mind, because a “creator necessarily
knows all properties of his creatures, [which] can’t have any others than those
he has given them”. (To be sure, in the very next paragraph he admitted that
“we build machines and [yet] cannot predict their behavior in every detail.” But
he claimed that that was because “we don’t create . . . machines out of nothing,
but build them out of some given material.” [??]). One is reminded of an ob-
jection to the idea of machine intelligence that Turing considered in his 1948
report “Intelligent Machinery” ([3], pp. 411–412): To claim that “in so far as a
machine can show intelligence, [that must] be regarded as nothing but a reflec-
tion of the intelligence of its creator”, is, Turing says, like claiming that “credit
4
In a note ([9]) first published posthumously in vol. III of his Collected Works.
5
See chapters 9–14 in [3].
6
To appreciate just how remarkable, compare G¨odel’s idea of arithmetizing syntax
with the statement by computer pioneer Howard Aiken (in 1956!) that “If it should
turn out that the basic logic of a machine designed for the numerical solution of
differential equations coincides with [that] of a machine intended to make bills for
a department store, [that would be] the most amazing coincidence I have ever en-
countered.” (Quoted in [2], p. 43.)
136 J.W. Dawson Jr.
for the discoveries of a pupil should be given to his teacher”. “In such a case”,
he counters, “the teacher [sh]ould be pleased with the success of his methods of
education” but “[sh]ould not claim the results themselves unless he . . . actually
communicated them to his pupil.”
G¨ odel died in 1978, on the eve of the microcomputer revolution, so we are
left to wonder what he might have thought of that development. No doubt he
would have welcomed computers as tools for mathematical experimentation,
which might lead to the formulation of new conjectures and extend our mathe-
matical intuition. But I doubt he would have wavered in his belief that the power
of the human mind surpasses that of any machine, and that we possess the abil-
ity to solve any mathematical problem we are capable of posing — a belief he
shared with David Hilbert, despite his own incompleteness results, which had
shown Hilbert’s formalist program for securing the foundations of mathematics
to be unrealizable.
References
1. Buss, S.S.: On G¨odel’s Theorems on Lengths of Proofs II: Lower Bounds for Recog-
nizing k Symbol Provability. In: Clote, P., Remmel, J.B. (eds.): Feasible Mathe-
matics II. Progress in Computer Science and Applied Logic, Vol. 13. Birkh¨auser,
Boston (1995) 57–90
2. Ceruzzi, P. E.: Reckoners, the Prehistory of the Digital Computer, from Relays
to the Stored Program Concept, 1933–1945. Greenwood Press, Westport, Conn.
(1983)
3. Copeland, J. (ed.): The Essential Turing. Oxford University Press, Oxford (2004).
4. Davis, M.: The Universal Computer. The Road from Leibniz to Turing. W.W.
Norton and Company, New York London (2004)
5. Dowling, W.F.: There Are No Safe Virus Tests. American Mathematical Monthly
96 (1989) 835–6
6. G¨odel, K.:
¨
Uber formal unentscheidbare S¨ atze der Principia Mathematica und
verwandter Systeme I. Monatshefte f¨ ur Mathematik und Physik 38 (1931) 173–
198. Reprinted with English translation in [10] 144–195
7. G¨odel, K.:
¨
Uber die L¨ange von Beweisen. Ergebnisse eines mathematischen Kollo-
quiums 7 (1936) 23–24. Reprinted with English translation in [10] 396–399
8. G¨odel, K.: Some Basic Theorems on the Foundations of Mathematics and Their
Philosophical Implications. In: [12] 304–23
9. G¨odel, K.: Some Remarks on the Undecidability Results. In [11] 305–306
10. Feferman, S., et alii (eds.): Kurt G¨odel Collected Works, vol. I. Oxford University
Press, New York Oxford (1986)
11. Feferman, S., et alii (eds.): Kurt G¨odel Collected Works, vol. II. Oxford University
Press, New York Oxford (1990)
12. Feferman, S., et alii (eds.): Kurt G¨odel Collected Works, vol. III. Oxford University
Press, New York Oxford (1995)
13. Feferman, S., et alii (eds.): Kurt G¨odel Collected Works, vol. V. Oxford University
Press, New York Oxford (2003)
14. Hartmanis, J.: G¨odel, von Neumann, and the P = NP Problem. Bulletin of the
European Association for Computer Science 38 (1989) 101–107
15. Sieg, W.: Only Two Letters: The Correspondence Between Herbrand and G¨odel.
The Bulletin of Symbolic Logic 11 (2005) 172–184