Goedel's theorem and the AI debate

[Micha]

Since I have been reading Goedel, Escher, Bach many years ago, the question, what (if anything) Goedel's theorem has to say about the relation between human intelligence and AI has been working in the back of my mind. Later my thinking was influenced by reading the books of Roger Penrose (eg. The Emperor's New Mind).
I always found Penrose's argument for the superior power of our human mind compared to computer algorithms very convincing. For example, he argues, that every child can understand the concept of natural numbers, whereas the Peano axioms and any extension can not distinguish them from supernatural numbers.
On the other hand, formalists like to make the case of how strictly formalizing geometry helped to solve the centuries lasting struggle with the parallel axiom and resulted in the birth of the fruitful mathematical field of non Euclidian geometry. In their view, this example shows, how intution can be fooled and thus is not per se superior to formal systems.
A vague idea I have on this, is, that maybe the reason, why very smart people on "plantonist" and "formalist" sides can not agree on a common standpoint on this, might be, that the question is not well posed in the current form. I think, whenever we try to compare the power of the intuitive concept of truth with the formal concept of formal provableness, we are lacking a third independent concept, which could act as a referee between the two. How could intution ever be recognized to be superior to a formal system, when all what we allow as a referee, is a proove in a formal system.
If you are able to read German, here is a very nice link:
http://www.joergresag.privat.t-online.de/
Especially reading chapter 4.4 of "Die Grenzen der Berechenbarkeit" has given me the stong feeling, that the appearance of supernatural numbers out of the Peano axioms is to be regarded as resulting from a limitation of the concept of formal systems and is not due to the "fuzziness" of the the intuitive concept of natural numbers (unlike in the case of geometry). But how can you make the case, if all you have, is formal systems and our "fuzzy intution"?

 

[Hurkyl]

You seem to be bouncing around between separate ideas, but I'll try to respond anyways.


Gödel's first incompleteness theorem says that there is a statement about the arithmetic of the natural numbers that cannot be proven or disproven. I honestly don't see why people think this has any relevance to AI -- so what if a computer is incapable of logically deciding certain questions? So are humans!


I find formalism to be a rather practical position. It ignores precisely those issues that are irrelevant to actually doing mathematics. Platonists and formalists are doing the same mathematics; the formalist just doesn't see a need to require the symbols to have some sort of (non-mathematical!) deeper meaning. The formalist doesn't necessarily reject the notion that there might be a deeper meaning -- just the notion that that deeper meanings are a part of mathematics. (for example, I'll let the physicists try and associate mathematical symbols to the "real world")

For example, he argues, that every child can understand the concept of natural numbers, whereas the Peano axioms and any extension can not distinguish them from supernatural numbers.

I don't see what one has to do with the other.

 

[Micha]

Quote:
For example, he argues, that every child can understand the concept of natural numbers, whereas the Peano axioms and any extension can not distinguish them from supernatural numbers.

I don't see what one has to do with the other.

To oversimplify the point to make the idea clear:
My (or rather Penrose's) point is, that if a child can distinguish natural numbers from supernatural and any formal system can not, then the child is superior to any formal system.

I am not saying, this is to 100% my opinion. But I would be interested, how you would argue against it.

 

[Hurkyl]

Nobody said the child can distinguish between the naturals and the supernaturals -- just that the child can understand the naturals. (That's, of course, quite debatable, but I'm willing to grant that a child understands the naturals for the sake of discussion)

(I'm going to switch to the hypernaturals, because I know about those. I hadn't heard of the supernaturals until your post)


To put it a different way -- how do you propose to tell if you learned the natural numbers in elementary school, or if you learned the hypernatural numbers in elementary school? (and your teacher just told you they were natural numbers)

 

[Micha]

I would guess, that hypernaturals and supernaturals are just synonyms, but I am not sure.
For the definition of supernatural numbers please look here:
http://planetmath.org/encyclopedia/LcmOfSupernaturalNumbers.html
They are constructed by adding the negation of the undecidable statement G from the proof of Gödel´s to the axioms.

You could confront the child with a supernatural number and ask him, whether this fits into the concept of natural numbers it just learned or not. And even more, you could teach the child about the difference then, and the child could safely distinguish the two every time after, whereas a formal system can not be enhanced in such a way. You could simply say now, that this is not true, but we could make a test and I find it hard to believe, that a child could not do that.

By the way, I am using the child only for illustration. It would be enough to show, that at least one skillfull mathematician can do something, any formal system can't do and safely distinguish naturals from super naturals.

 

[matt grime]

How are you/child/mathematician distinguishing between them? And why is the machine not capable of distinguishing? With the extra information that there is an injection from one to the other, and not vice versa does that not allow the machine to distinguish? Or perhaps your point is that the machine would have to be told of different things in order to get the diffference, since all it knows are the axioms of some system of which they are models, and the child can pick it up 'naturally'.

 

[Micha]

Yes, I assume that the machine acts like a formal system in Gödel's sense. It follows then, from Gödel's theorem, that an undecidable statement G can be constructed and either it or its negation can be added to the system. By adding its negation, the system starts to talk about super naturals.
Now the point is, that even after adding G and having a more powerful system about natural numbers, Gödel's theorem can now be applied again to the enhanced formal system and so on.

I don't know, how we humans decide between the two concepts. Name it "picking it up natural" or "intution". Also, you have to decide for youself, if you buy my view, that we actually can do it, this is part of this discussion.
My point then is, if our brain, on a fundamental physical level acts like a formal system (and many biologists and physicists would agree), then how can "intution" do better. A good counter argument probably is, that intution is fuzzy and so it is more powerful than formal systems, but at the same time it makes mistakes. But is this really true with such a simple concept as natural numbers?

 

[matt grime]

I'm not going to buy most of what you've written. Here's why (and an explanation of what I will buy at the end).

When you say a child can differentiate between the Naturals and the Hypernaturals, you haven't quantified what this means. Certainly, presented with descriptions of the naturals and then shown a hypernatural (that isn't natural) they will agree that it is no a presentation of something they've been taught is a natural. But that is neither here nor there - the machine is equally capable of distinguishing between different presentations.

Furthermore, both machine and child cannot distinguish between the two systems purely internally (i.e. as a consequence of the axioms they both model).

If you don't buy this, consider this example:

Let G be the group of real numbers under addition, and H the group of strictly positive numbers nuder multiplication. We can all agree that they are different, because -1 is in G but not in H. But wait. They are in fact isomorphic as groups - x--> exp(x) (and there are infinitely many isomorphisms, in fact). Now consider K as the rationals under addition. Is K the same model of the axioms of a group as G? sqrt(2) is in G but not in K, but that is no guarantee, as we've just seen.

So how do we deal with that question? They cannot be isomorphic because they are not even in bijection by any map, but that is a different property, and not a groupy one. But now consider L as the group of integers under addition - this is in bijection as as set with K. But they aren't isomorphic - what is a boy/girl to do? Here L has a generator, K doesn't, or K is a divisible group, L isn't (divisble means that things like 2x=1 have solutions in K but not in L).

Thus I reject the hypothesis that a child can differentiate between the naturals an hypernaturals. All they can say is that there are two superficially different objects that satisfy the axioms of arithmetic. But the computer can also say that. The child might have a 'gut' feeling that they are genuinely different things, but like the examples above, I hope you realize that that is by no means a guarantee - gut feelings are often wrong.
The question then becomes 'can they be differentiated' and here's where we get into the stuff I would buy - how do we decide what to look for to differentiate things? Is that something that a sufficiently advanced machine would be able to do innately, somehow. Is that what it means to have (mathematical) consciousness?

And going back to the rationals/reals under addition, given how many times I here the 'it seems obvious they aren't the same but I can't show it' refrain, it is not clear that a child would come up with a way to distinguish between two different presentations of two genuinely different things. Even more seriously, there are known issues in group presentations, which say there is no algorithm (that terminates) that can tell if two finitely presented groups are isomorphic. There is no algorithm to even determine if a given presentation is of a finite group, or an abelian group.

 

[Micha]

Hi Matt,
it seems, my presention of Penrose's argument was oversimplified (or just wrong). You easily countered my punch line by saying that a child can only distinguish the two representations and not the two structures internally.
And that different representations can or can not have the same underlying
internal structure.
I have to go back and think harder, I guess. :-)