Friday, October 20, 2006

Strong AI

In the late eighties and early nineties, Roger Penrose in two books, presented an argument that the brain cannot be algorithmic and thus the AI program is doomed to failure. Unfortunately, he also proposed that a new theory of quantum gravity may be necessary to understand the brain and consciousness and so his ideas were largely ignored by the neuroscience community. However, I think his argument for the noncomputational aspect of brain function was actually well thought out and deserved more attention. I personally believe the argument is flawed but it does stir up some interesting questions.

Penrose's argument is essentially based on the theorems of Godel, Turing and Church. Godel showed that for any formal system, there will be statements that are true but not provable within that system. Hence, formal systems are incomplete in that there will always be undecidable statements. Turing then showed that for any computer (or any algorithmic system), there exist programs that we know and can prove will not stop but no computation on that computer can ever determine this fact. Penrose then argued that since we (at least Turing and Godel) can determine the truth of such undecidable statements, then we (they) could not be doing that computationally or algorithmically.

The implications are quite profound. It means more than just the futility of traditional AI. It also means the brain cannot even be simulated on a computer because any simulation on an algorithmic machine implies the outputs are also algorithmic. Pushing it further, if the brain is based on physical principles, then this implies that physics itself (or at least aspects of it) can't be simulated on a computer either. This is why Penrose was led to postulate that there must be some new physics out there that is beyond computation. The idea is really not that crazy if you think about it. However, it is definitely not air tight.

I think the hole in Penrose's argument is that he believes that we actually can circumvent Godel's theorem and decide undecidable problems. However, I don't think that this is necessarily true. We don't know what formal system our brain happens to be using so don't know which undecidable statements happen to be true but we can't prove. The ability to prove Godel's theorem and to decide truths for other formal systems that are not ours could be implemented computationally. So, the existence of Godel's and Turing's theorems does not necessarily imply that the brain is noncomputational.

Furthermore, it is doubtful that the formal system of our brains are even constant in time or conserved between individuals. More likely, our brain and hence formal system is constantly changing because of random environmental inputs. Thus, Penrose's argument for the futility of traditional AI may be correct. A truly human-like intelligent machine couldn't be built from a fixed formal system that is knowable. It may need to arise from a massively parallel learning system that constantly changes its axioms. Thus even if you could measure the formal system at some point in time, it would be changed before you could use this knowledge. This would be the equivalent of an uncertainty principle for the brain.

Penrose also rules out the role of randomness in breaking algorithmicity. He argues that randomness can be mimicked by an algorithmic pseudo-random number generator. I don't see why this is the case. Perhaps, true randomness is beyond computation. This then leads to the question of where randomness actually comes from. Perhaps it is a vestige of the initial conditions of the universe. And where did that come from? Well we may need a theory of quantum gravity to figure that one out. Hmm, maybe Penrose was right afterall:).


Daniel said...

While interesting, isn't this work getting a little ahead of itself? We cannot connect (or even make a good-faithed effort) towards connecting cognitive computation to physical principles yet. With any luck, we will be there relatively soon (that is the type of problem I work on in Neuroscience).

Also, we do not yet know what type of problems break the system. Testing for such a problem may prove impossible due to the adaptive properties of the brain. Assume the brain is a finite, formal system. After showing the brain (person?) a new problem, if the brain were to adapt to include this new problem (making a brain state b+1), the brain would still be a finite system. Applying this logic to a lifetime, a finite system could appear infinite due to the fact that the b+1 state would always be possible.

Hal said...

One view is that Penrose's argument against Strong AI is valid but that he is incorrect in saying that thought will be explained in terms of some yet-to-be-developed theory of physics.

I read SOTM fairly carefully, and after thinking it over for a couple years on and off I decided that one would probably end up with the same pseudo-paradox regardless of what sort of physical theory you were trying to use. Theories of physics always come down to precisely described mathematical models, and if the brain is described in terms of any such model it seems to me that you always end up with a paradox.

He gave an example of this in SOTM where he considered a hypothetical model of the brain based on "oracles" that could determine whether a Turing machine would stop. He tries to get around this by saying that what is required is a new theory of physics that is so radically different that these sorts of paradoxes could be avoided, but my view is that this is wishful thinking.

Speaking of wishful thinking, I don't think the mind will ever be completely explained. I don't buy these arguments about "massively parallel learning system that constantly changes its axioms." I do think there is some value in deciding what one thinks about these sorts of questions. Either the mind will be understood or it won't. Anyone who states an opinion is engaging in wishful thinking, but what's wrong with having an opinion?

If you think the mind will be understood one day, then that's fine, but the burden of proof rests on people with this opinion. Those of us who think this is impossible shouldn't be expected to prove a negative (rigorously, at least).