Does the Godel theorm disallow computers with minds?

[pivoxa15]

Penrose seems to argue that computers will never have minds or understanding as humans do due to Godel's Incompleteness theorem. I think he is right about this one as computers just are formal systems. But why then are there still so many critics that claim that AI is possible?

 

[mandril]

Seems to my that incompletness theorem should be interpreted as: no Turin-like machine is able to have an algorithm that has the capability of proving all the theorems within a system (that is, all the logicall consecuenses of the axioms). But, if you think about it, humand mind is also unable to complet this task. A.I., at least in its modern form is trying to go beyond algorithm determinism. We are trying to create systems complex enought so that they have emerging propertis, that can't be predicted from the code itself. Genetic algorithms and Neural networks (NN) are the most used ones now, and to give you an example: the use of NN in data minig has tha capability of showing staistical correlation beetwen data, that you had no idea it existed. As a mater of fact it crates its own "questions" to the data. So, even if we are very far away from creating a "thinking machine" (from my poit of view that is imposible) the development on that field is leading to some very useful results

 

[Hurkyl]

I have no idea what Penrose's argument is... but I expect I'll disagree with it.

Gödel's (first) incompleteness theorem says that there exists a statement P in the language of integer arithmetic for which neither P nor ~P can be proven from the axioms of integer arithmetic.

The usual consequence that is stated is that if you have an actual model of the integers, then either P or ~P must be a true statement. Therefore, you have a true statement that cannot be proven from the axioms.

(Of course, what people seem to neglect is that while P may be true in this model, ~P will be the one that's true in some other models)


I really don't know how people leap from this to saying that our human brains are superior. We are just as unable to find a proof of P as a computer is.

 

[selfAdjoint]

I really don't know how people leap from this to saying that our human brains are superior. We are just as unable to find a proof of P as a computer is.

There are known theorems in number theory that are Goedel undecidable wrt the ZF axioms. Penrose had some friends who deduced one such theorem. Penrose claimed that by their "mathematical intuition" he and his friends could see that these theorems were true, although Goedel undecidable. So he says a computer (he assumes a digital computer, representable by a Turing Machine) is as limited as the ZF axioms, and there would be statements that any given computer could not determine the truth value of. But human mathemations could use mathematical intuition to determine the truth value of them. So human minds and digital computers are in different categories.

I find this argument beneath contempt. Mathematical intuition has led many fine minds into falsehood. Consider the storied history of the Dirichlet principle, as told for instance by Eric Temple Bell. Great mathematicians of the nineteenth century, including Dirichlet himself and Poincare, thought the priinciple must be true, even though they couldn't prove it; their intuition told them so! Then in the twentieth century it was shown to be false!

 

[Hurkyl]

Attacking the argument from the opposite direction, in principle I know of no reason why a computer could not be programmed with heuristics to guess the truth values of propositions, much as humans would use their intuition. Of course, the computer will be wrong from time to time. (Much as humans would. )

 

[hypnagogue]

I think he is right about this one as computers just are formal systems.

Of course, one could just as well view the brain itself as "just" a formal system. And of course, to the extent that the brain can be regarded as a computer, we already have an existence proof of a kind of computer that has a mind.

The term "mind" is ambiguous, but if by "mind" we just mean some information processing system that shows some degree of sophistication in various cognitive tasks (which would subsume mathematical reasoning among other things), I see no reason why a man-made computer could not have a mind, at least in principle. At the very least, although it would be an enormous undertaking, in principle one could model a brain and its environment down to the molecular level, given sufficient computational resources and knowledge of the physical systems involed. Such a model would process information in the same way as its flesh and blood counterpart.

 

[pivoxa15]

I think that having a mind would imply having understanding. Although understanding is hard to define also.

We have understanding but current computers do not (if they did they should easily pass the Turing Test). A good example is for computers to search through a dictionary. They can only go through definition after definition in a circular manner because they have no understanding. They can never get out of the system so to speak. However, We can just look up a definition and know what it implies without looking at the definitions of other words because we understand the word. We are something above the formal systems of a computer and dictionary. I think that is one of the main issues Penrose was trying to address. An analogy is that a 2D object can never be identical to a 3D object.

 

[pivoxa15]

There are known theorems in number theory that are Goedel undecidable wrt the ZF axioms. Penrose had some friends who deduced one such theorem. Penrose claimed that by their "mathematical intuition" he and his friends could see that these theorems were true, although Goedel undecidable. So he says a computer (he assumes a digital computer, representable by a Turing Machine) is as limited as the ZF axioms, and there would be statements that any given computer could not determine the truth value of. But human mathemations could use mathematical intuition to determine the truth value of them. So human minds and digital computers are in different categories.

I find this argument beneath contempt. Mathematical intuition has led many fine minds into falsehood. Consider the storied history of the Dirichlet principle, as told for instance by Eric Temple Bell. Great mathematicians of the nineteenth century, including Dirichlet himself and Poincare, thought the priinciple must be true, even though they couldn't prove it; their intuition told them so! Then in the twentieth century it was shown to be false!

At least human mathematicians have an intuition and able to explain how we arrived at our intuition. While (for the same problems) the computers are not able to come up with any explanation or valid output at all (by definition). Maybe Penrose is saying that the ability to have an intuition for some problems that computers (by definition) cannot solve puts us at a different level to computers. And the difference is that we have understanding hence a mind.

 

[selfAdjoint]

At least human mathematicians have an intuition and able to explain how we arrived at our intuition. While (for the same problems) the computers are not able to come up with any explanation or valid output at all (by definition). Maybe Penrose is saying that the ability to have an intuition for some problems that computers (by definition) cannot solve puts us at a different level to computers. And the difference is that we have understanding hence a mind.

Well there are AI systems that can prove theorems they've never "seen" before, and even come up with new consequences! (Unimportant) new theorems have even been discovered this way. You do have to carefully train the system in the branch of mathematics being studied, but you have to do that with human mathematicians too. Penrose went through an apprenticeship when he was learning what he needed to do further creation, just like everybody else.

I believe Penrose wrote The Emperor's New Mind in reaction against strong AI triumphalism arising from just such events as successful theorem proving. Every now and then in the math journals there is raised the question "Are mathematicians becoming obsolete?". So far the answer is no, but just like Chess Grand Masters, they're running scared, and part of running scared is whistling past the graveyard. That's where I put Penrose.

 

[pivoxa15]

Well there are AI systems that can prove theorems they've never "seen" before, and even come up with new consequences! (Unimportant) new theorems have even been discovered this way. You do have to carefully train the system in the branch of mathematics being studied, but you have to do that with human mathematicians too. Penrose went through an apprenticeship when he was learning what he needed to do further creation, just like everybody else.

I believe Penrose wrote The Emperor's New Mind in reaction against strong AI triumphalism arising from just such events as successful theorem proving. Every now and then in the math journals there is raised the question "Are mathematicians becoming obsolete?". So far the answer is no, but just like Chess Grand Masters, they're running scared, and part of running scared is whistling past the graveyard. That's where I put Penrose.

Have you read Shadows of the Mind? What do you think about his Godel-Turing conclusion where we will always know things which a computer cannot possibly (compute hence) know? The chess example on p46 and fanatasy dialogue on p189 is also good.

Are you sure computers are able to prove theorems that mathematicians accept with Q.E.D standard? I've only heard about the 4 colour theorem but that was the computer going through all the possbilities which is not how human mathematicians prove things - I think I heard that some mathematicians do not accept it. Penrose gave reasons to why a computer cannot prove things like using inductive reasoning as human mathematicians do. No doubt mathematicians use computers as a very useful tool as pointed out by Alan Connes and even more so for people in other disciplines like physics. But as Penrose points out there may be internal limitations of the computer due to the way it is built - which is a formal system. If you say a computer can replace a mathematician than they will be able to replace everything else as well such as a physicist, biologist ...

 

[selfAdjoint]

Have you read Shadows of the Mind? What do you think about his Godel-Turing conclusion where we will always know things which a computer cannot possibly (compute hence) know? The chess example on p46 and fanatasy dialogue on p189 is also good.

Are you sure computers are able to prove theorems that mathematicians accept with Q.E.D standard? I've only heard about the 4 colour theorem but that was the computer going through all the possbilities which is not how human mathematicians prove things - I think I heard that some mathematicians do not accept it. Penrose gave reasons to why a computer cannot prove things like using inductive reasoning as human mathematicians do. No doubt mathematicians use computers as a very useful tool as pointed out by Alan Connes and even more so for people in other disciplines like physics. But as Penrose points out there may be internal limitations of the computer due to the way it is built - which is a formal system. If you say a computer can replace a mathematician than they will be able to replace everything else as well such as a physicist, biologist ...

No I haven't read Shadows of the Mind. Do you know if his argument in Shadows is any diffrent from the one in The Emperor's New Mind? That one falls to the ground because it assumes what it seeks to prove, that humans can do things computers can't.

I wasn't referring to the kind of use of computers in theorem proving involved in the four color proof. In my view that was just data processing. For more of what I was referring to see http://en.wikipedia.org/wiki/Automated_theorem_proving" . The automated proof systems they mention are only the popular end of theorem proving. For example way back, a computer scientist published a book on a program that could prove any theorem in elementary geometry. Penrose's statement about induction needs qualification, I would think.

 

[Hurkyl]

There is an embarassingly simple proof that a computer can (in principle) come up with any formal proof that a mathematician can.

The basic components are:
(1) A computer can recognize a proof.
(2) A computer can iterate through every possible sequence of symbols.

For any provable statement P, we can find a proof with the following algorithm:
For every possible sequence S of symbols:
::: If S is a proof of P, then print S and quit.

Any decidable statement P can be decided with:
For every possible sequence S of symbols:
::: If S is a proof of P, then print "P is true" and quit.
::: If S is a proof of ~P, then print "P is false" and quit.


And, BTW, humans do prove things by checking all the cases -- we just usually try very hard to keep the number of cases very small, because we're "lazy".

 

[selfAdjoint]

There is an embarassingly simple proof that a computer can (in principle) come up with any formal proof that a mathematician can.

The basic components are:
(1) A computer can recognize a proof.
(2) A computer can iterate through every possible sequence of symbols.

For any provable statement P, we can find a proof with the following algorithm:
For every possible sequence S of symbols:
::: If S is a proof of P, then print S and quit.

Any decidable statement P can be decided with:
For every possible sequence S of symbols:
::: If S is a proof of P, then print "P is true" and quit.
::: If S is a proof of ~P, then print "P is false" and quit.


And, BTW, humans do prove things by checking all the cases -- we just usually try very hard to keep the number of cases very small, because we're "lazy".

That's to generate a proof of an existing theorem. The need is to generate new theorems. I don't think that's so simple!

BTW this reminds me of a proof of something in set theory I did on a quiz in grad school. I did it by casification; I think there were 16 cases and I did a page or so of reasoning on each case. At the end I wrote "This exhausts the cases". When I got the paper back it was marked in red "And the grader". But I got an A on it.

 

[Hurkyl]

That's to generate a proof of an existing theorem. The need is to generate new theorems. I don't think that's so simple!

The same idea can be used to generate a list of all theorems.

 

[selfAdjoint]

The same idea can be used to generate a list of all theorems.

Assuming the set (or "collection") of possible theorems is countable. Have you a proof of that?

 

[Hurkyl]

Theorems are written as finite-length strings over an alphabet. A computer can clearly enumerate all such strings when the alphabet is finite. With a suitable encoding, this works even if the alphabet is countably infinite.

Uncountably infinitely many variable symbols is superfluous -- they don't give you any extra power. The only possible problem is if you have an uncountable operator set.

Humans can't work with even a countably infinite operator set, let alone an uncountably infinite one! So humans are no better in this regard.

 

[quantumcarl]

If we let some genetic algorthyms go at some solutions/treatments for cancer mutation etc... a lot of people would be out of a (health industry) job in a hurry!.

For some reason there have been no advances in NN,GA or AI processing of medical conditions. But using them to design and build cars etc... is ok.

 

[TheStatutoryApe]

I think that having a mind would imply having understanding. Although understanding is hard to define also.

We have understanding but current computers do not (if they did they should easily pass the Turing Test). A good example is for computers to search through a dictionary. They can only go through definition after definition in a circular manner because they have no understanding. They can never get out of the system so to speak. However, We can just look up a definition and know what it implies without looking at the definitions of other words because we understand the word. We are something above the formal systems of a computer and dictionary. I think that is one of the main issues Penrose was trying to address. An analogy is that a 2D object can never be identical to a 3D object.

Your example is close to that of the Chinese Room Experiment. There are a few threads here where that particular thought experiment as well as the definition of 'understanding' has been beaten well beyond the death of a horse. The only thing I will say here is figure out how you think a human comes to 'understand' the words it uses and then try to figure out whether or not you think a computer could be made that could do the same.

 

[pivoxa15]

Your example is close to that of the Chinese Room Experiment. There are a few threads here where that particular thought experiment as well as the definition of 'understanding' has been beaten well beyond the death of a horse. The only thing I will say here is figure out how you think a human comes to 'understand' the words it uses and then try to figure out whether or not you think a computer could be made that could do the same.

So you think a substantive or physical definition of how humans come to 'understand' is what is needed? For example, lightning comes from an electronic discharge, consciousness comes from...

I think it is very important that this quetion is addressed which today is nowhere near close of being answered. As a result, people are able to claim all sorts of speculations such as digital computers being able to understand.

 

[quantumcarl]

John Searle's China(ese) Room

Ach! I thought all 14 pages of this discussion went rather well! You'll just have to step over the horse carcasses.

https://www.physicsforums.com/showthread.php?t=93274&highlight=Searle

 

[quantumcarl]

So you think a substantive or physical definition of how humans come to 'understand' is what is needed? For example, lightning comes from an electronic discharge, consciousness comes from...

I think it is very important that this quetion is addressed which today is nowhere near close of being answered. As a result, people are able to claim all sorts of speculations such as digital computers being able to understand.

To boil down the thread's conclusions for you:

I'm using the word "awareness" to replace the word "consciousness". Awareness was deemed to be a prerequisite to understanding.

Also... awareness of experience and the neuronal storage (memory) of the experience of primary events is indicated to be required to support understanding. Also, the actual presence of the observer/participant's receptors simultaneous to the occurrence of the primary event is required to build upon understanding. Meeting these conditions one can be said to understand a specific predicament or state... to a degree.

However, until one is aware of all the surrounding conditions and contributors to an event or concept, one cannot be said to "fully" understand it.

You may note that it is more probable that someone or thing does not understand a concept than it is probable to have them understand a concept... until they have, first hand, experienced the conditions of the concept themselves.
An example being medical students. These aspiring students collect rheams of semantic knowledge from lectures, books, labs and cadavers for many years... however, this does not mean they understand medicine. They only have semantic knowledge of it.

They are then required to spend a practicum in the field for several years before they are considered to be a person who has approached an understanding of medicine.

Similarily, I can possesses a physics vocabulary, hours of lectures, some math and a slide ruler, then address Zapper z about an issue concerning Quantum Mechanics... but... he will immediately recognize that I have no understanding of the background or the concept of QM.

 

[TheStatutoryApe]

So you think a substantive or physical definition of how humans come to 'understand' is what is needed? For example, lightning comes from an electronic discharge, consciousness comes from...

I think it is very important that this quetion is addressed which today is nowhere near close of being answered. As a result, people are able to claim all sorts of speculations such as digital computers being able to understand.

If we mean to replicate rather than simply imitate human consciousness then I think we need to understand better what the process is we are trying to replicate of course.

At the same time it seems that the best way to understand consciouness would be to replicate and model it in a computer.