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