From: atten@phil.ruu.nl (Mark van Atten)
Newsgroups: comp.ai.philosophy
Subject: goedel and ai - correct version!!
Keywords: ai,goedel
Date: 6 Apr 92 10:23:07 GMT
Organization: Department of Philosophy, University of Utrecht, The Netherlands

Mea Culpa! Something went wrong with the version I posted April 3. This is the
correct version, i.e. part I is the same but now part II is also included.

There is an ongoing discussion right now on mathematical realism in the ai
group. Some people question the relevance of this to ai. In this article,
I want to discuss
1 The objective existence of mathematical objects
2 The significance of this for ai

(the lion's share of this article consists of quotes from the philosophers
I like best - I think it's better to be as precise as possible in stating
their views. Anyway, I agree with them completely (i.e., Leibniz and Goedel)

I THE OBJECTIVE EXISTENCE OF MATHEMATICAL OBJECTS

I.1 Leibniz on constant fundamental ideas
I.2 Goedel on objectivity
I.3 math. and logic cannot be 'explained away'
I.4 Goedel on intuition
I.5 comparison of math. and physics
 
II THE SIGNIFICANCE OF GOEDEL'S THEOREM TO AI

II.1 This is not repeat not Lucas' argument
II.2 Penrose's argument
II.3 Goedel's theorem and ai
II.4 non-algorithmic processes
II.5 the infinite mind

I.1 'Hobbes saw that all truths can be demonstrated from definitions [we're
not so sure anymore since Kant, but for the sake of argument, never mind], but
he believed that all definitions are arbitrary and nominal, since the
imposition of names on things is arbitrary. But it must be known that concepts
cannot be combined in an arbitrary fashion, but a possible concept must be
formed from them, so that one has a real definition. From this it is evident
that every real definition contains some affirmation of at least possibility.
Further, even if names are arbitrary, yet once they have been imposed their
consequences are necessary and certain truths arise which, though they depend
on the symbols imposed, are nevertheless real. For example, the rule of nine
depends on symbols imposed by the decimal system, and yet it contains a real
truth. Again, to form a hypothesis, i.e. to explain a way of producing
something, is simply to demonstrate the possibility of the thing; and this is
useful, even though the thing in question has often not been generated in such
a way.'
( Leibniz, Of universal synthesis and analysis; or, of the art of discovery
and of judgement, 1683)

>I.2 Goedel on objectivity
>'The same possibilities of thought are open to everyone, so the world of
>possible forms is objective and absolute. Possibility, then, is not dependent
>on an observer; it is therefore real because it is not subject to our will.'
>(quoted in Rucker 1984)

>I.3
>'Logic and mathematics (just as physics) are built up on axioms with real content which cannot be 'explained away'.

>1.4 Goedel on intuition
>'It should be noted that mathematical intuition need not be conceived of as a
>faculty giving an ***immediate*** knowledge of the objects concerned. Rather
>it seems that, as in the case of physical experience, we ***form*** our ideas
>also of those objects on the basis of something else which is immediately
>given. Only this something else here is not, or not primarily, the sensations.
>That something besides the sensations actually is immediately given follows
>(independently of mathematics) from the fact that even our ideas referring to
>physical objects contain constituents qualitatively different from sensations
>or mere combinations of sensations, e.g., the idea of object itself, whereas,
>on the other hand, by our thinking we cannot create any qualitatively new
>elements, but only reproduce and combine those that are given. Evidently the
>'given' underlying mathematics is closely related to the abstract elements
>contained in our empirical ideas. (Note that there is a close relationship
>between the concept of set and the categories of pure understanding in Kant's 
>sense. Namely, the function of both is 'synthesis', i.e., the generating of
>unities out of manifolds (e.g., in Kant, of the idea of ***one*** object out
>of its various aspects)) It by no means follows, however, that the data of
>this second kind, because they cannot be associated with actions of certain
>things upon our sense organs, are something purely subjective, as Kant
>asserted. Rather they, too, may represent an aspect of objective reality, but,
>as opposed to the sensations, their presence in us may be due to another kind
>of relationship between ourselves and reality. [...] The question of the
>objective existence of the objects of mathematical intuition is an exact
>replica of the question of the objective existence of the outer world.'
>(Goedel 1964, postscipt to 'What is Cantor's continuum problem?')

>Here, physical objects need not necessarily be understood in avery strict 
>sense, e.g. as material objects. It stands for all physical phenomena which
>we believe to be outside of us, i.e. exist independently of us. Physics studies
>these objects (materials, fields), and needs them in order to obtain a
>satisfactory theory of our physical experiences.
>Note that Goedel explicitly wishes to get rid of Kant's Ding an Sich and its
>transcedence.

>'Russell compares the axioms of logic and mathematics with the laws of nature
>and logical evidence with sense perception, so that the axioms need not be
>necessarily eveident in themselves, but rather their justification lies
>(exactly as in physics) in the fact that they make it possible for these
>'sense perceptions' to be deduced; which of course would not exclude that they
>also have a kind of intrinsic plausibility similar to that in physics. I think
>that (provided 'evidence' is understood in a sufficiently strict sense) this
>view has been largely justified by subsequent developments, and it is to be
>expected that it will be still more so in the future. It has turned out that
>(under the assumption that modern mathematics is consistent) the solution of
>certain arithmeticcal problems requires the use of assumptions essentially
>transcending arithmetic, i.e., the domain of the kind of elementary
>indisputable evidence that may be most fittingly compared with sense perception.(Goedel 1944, Russell's mathematical logic)


'Russell compares the axioms of logic and mathematics with the laws of nature
and logical evidence with sense perception, so that the axioms need not be
necessarily eveident in themselves, but rather their justification lies
(exactly as in physics) in the fact that they make it possible for these
'sense perceptions' to be deduced; which of course would not exclude that they
also have a kind of intrinsic plausibility similar to that in physics. I think
that (provided 'evidence' is understood in a sufficiently strict sense) this
view has been largely justified by subsequent developments, and it is to be
expected that it will be still more so in the future. It has turned out that
(under the assumption that modern mathematics is consistent) the solution of
certain arithmeticcal problems requires the use of assumptions essentially
transcending arithmetic, i.e., the domain of the kind of elementary
indisputable evidence that may be most fittingly compared with sense perception.(Goedel 1944, Russell's mathematical logic)

Of course, it's much better to read the full articles than just these quotes,
but I see them as a kind of pointers, just to give a hint at the underlying
ideas. Goedel's articles can be found in his Collected Works; in particular,
the 1944 and the 1964 articles, with good introductions, can be found in
volume II. Goedel gives quite a lot of additional arguments there.

II THE SIGNIFICANCE OF GOEDEL'S THEOREM FOR AI

II.1 This is ***not*** Lucas' argument!

Many writers , Hao Wang for example, have refuted Lucas' argument:
'the claim that I know Con(S) in each case is dubious, for all I know is:
 IF S is consistent, THEN Con(S) is true but unprovable in S...In order to beat
 every Turing machine, I would have to be able to decide correctly all cases
of an unsolvable problem.'
(Hao Wang, From Mathematics to Philosophy, p.316-7)

II.2 Penrose's argument

Let F be a formal system, and G(F) an undecidable formula in F. (e.g., Con(F))
Then Penrose's argument is this:
The ***deduction*** of G(F) from F is true and valid, we can ***see*** that. Theimportant thing is that it is the deduction is seen to be valid, while it is
not formalizable (is that correct English?).
Perhaps mathematical intuition cannot see ALL of true math. (Goedel thinks it
can, however), but that doesn't matter for this argument: there is at least
one math. truth that can not be formalized and hence, is not algorithmic.
It must be borne in mind that this is a question of principle. Probably no one
will ever be able to compute the 10^10^10^10 digit of pi, but in ***principle***, it is possible.
Again: it is the fact that we see the validity of Goedel's proof, not the truth
of G(f); that is the difference with Lucas.

II.3 relevance to ai

Please keep in mind that this concerns questions of principle. You can practice
ai very well without ever being troubled by arguments like this. However, as
soon as you want to address philosophical issues, it becomes relevant.
"It is only ***here*** (or with mathematical reflection principles generally)
that one can demonstrate, on anything like rigorous mathematical terms, that
our conscious understanding ***must*** be non-algorithmic. It is, indeed,
remarkable that any such clear general statement about the nature of our
thinking can be made at all! Without Goedel's theorem (or even with it, before
the full impact of that theorem is properly appreciated) one would have to
resort to much vaguer and less conclusive arguments about 'semantics', 'understanding', 'insight', and perhaps 'inspiration'.
(Roger Penrose, Precis of The Emperor's New Mind, Behavioral and Brain Sciences 1990, 13, p.643-705. This is a very helpful article which made a lot of things
very clear to me. In particular the peer commentaries and Penrose's answers to
them are very illuminating. If you can find this somewhere, READ IT)

II.4 non-algorithmic processes 

I used to be very impressed with the theories of Hofstadter ('statistically emergent mentality', see his Metamagical Themas). I consider him very good when
writing about the nature of intelligent behaviour, but his 'explanations' are
kind of weird. I mean, how to implement his Strange Loops (or, Tangled Hierarchies) which are clearly not algorithmic, on a Turing machine? That is impossible!
What to think of non-algorithmic behaviour coming out of a very large group of
algorithmical elements?
Anyway, whatever solution you choose, as soon as it can be implemented on a
Turing machine, it's algorithmic after all.
(In 'Information in the brain: a molecular perspective' MIT Press 19?, Ira B.
Black writes: 'We have identified the physical basis in the mind-brain system
of the 'strange loops' postulated by Hofstadter in his metaphorical GEB" However, it seems she is not quite right, especially as she continues to identify the
strange loop with continuous cycles, which Hofstadter explicitly tells they are
***not***(p.691, chap.XX in the 1980 Penguin ed.)

II.5 the infinite mind

This section was not intended to be included, but it is interesting, so never
mind. See Hao Wang, From Math. to Phil.,p.324ff. for details.
This is Goedel:
'Turing, in his 1937,p250, gives an argument which is supposed to show that
mental procedures cannot go beyond mechanical procedures. However, this argument is inconclusive. What Turing disregards completely is the fact that the mind, in its use, is not static, but constantly developing, i.e., that we understand abstract terms more and more precisely as we go on using them, and that more and more abstract terms enter the sphere of our understanding. There may exist systematic methods of actualizing this development, which could form part of the
procedure. Therefore, although at each stage the number and precision of the
abstract terms that are on our disposal may be finite, both (and therefore,
Turing's number of distinguishable states of mind) may converge to infinity in
the course of the application of the procedure. [...] This process, however,
today is far from being sufficiently understood to form a well-defined
procedure. It must be admitted that the construction of a well-defined
procedure would require a substantial advance in our understanding of the basic
concepts of mathematics.'


C
C
C
C
C
C
C
C
C
C
'Russell compares the axioms