Preface
The motivation for organizing the Workshop on Logic and Computation
was straightforward. The refined interaction of mathematics and computa-
tion theory is one of the most fascinating and potentially most fruitful devel-
opments in logic. This interaction has been accelerated by the emergence of
computers as a powerful research tool for mathematicians; but, independent
of this development, it has been intrinsic to various attempts at carrying
out significant parts of mathematics in computationally informative ways.
The broad issue is indeed a long-standing one and, historically, connected
with particular views on the nature of mathematics and appropriate method-
ologies.
It
came to the fore in response to the use of analytic methods in
number theory. I allude, of course, to Dirichlet's famous proof of the fact
that arithmetical progressions of the form
ax+ b,
with
a
and
b
relatively
prime, contain infinitely many primes;
1
but, I also allude to Dedekind's and
Kronecker's responses.
Let me point to one, pertinent feature of Kronecker's views; he considered
a proof of an existential statement as completely rigorous only if
it contains
a method that allows us to find [in finitely many steps] the magnitude whose
existence has been claimed.
2
Assuming the statement contains parameters,
the proof presumably has to provide a uniform method for finding the mag-
nitude, i.e. an effective function. The Kroneckerian viewpoint is appealed to
later in the French predicativists' rejection of abstract, set-theoretic methods.
Let me quote from Borel's most interesting contribution to the controversy
surrounding Zermelo's proof of the well-ordering principle:
One may wonder what is the real value of these arguments that I do not
regard as absolutely valid but that still lead ultimately to effective results.
1
G. P. Lejeune Dirichlet, Beweis des Satzes, dass jede arithmetische Progression, deren er-
stes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Faktor sind, unendlich viele
Primzahlen enthiilt ( 1837), reprinted in Dirichlet's Gesammelte Werke /, L. Kronecker (editor).
2Reported by K. Hensel in his introduction to Kronecker's Vorlesungen zur Zahlentheorie,
Leipzig, 190 I.
ix
Previous Page Next Page