Any time anyone wrestles with the underpinnings of human knowledge or the possibility of artificial intelligence they always expound at length on the supposed problem of Gödel’s incompleteness theorem. It’s mystifying how otherwise smart people continue to get this almost 180 degrees wrong. I’ve been reading The User Illusion and while I’m only a short way through author Tor Nørretranders has already abused the concept heavily.
Gödel Incompleteness is an idea that applies to certain types of logical formalisms. Using a formal framework – that is to say a set of basic axioms and the logical rules that follow from them, like a theory in mathematics – you can arrive at true statements in several ways. You can work forward from known truths and generate what you want, or you can start with what you want and see if its inverse produces a contradiction. Logically these are the same process; one is a derivation, the other a proof. A third thing that you can do is a construction, where you provide a method of transforming an unknown problem into one that has already been proved. By “reducing” the problem in this way you get to reuse a proof that someone else has already done.
What Gödel proved – using a formal theory about formal theories – is that for any logical formalism which is complex enough to produce arithmetic, there are true statements in the language which cannot be proved. His proof was a tricky construction that allowed him to form statements using the terms of the formalism itself, and then to concoct a special statement which was true but could not be proved. Called the Gödel sentence, in informal terms it’s basically “this statement cannot be proved.” While bizarrely self-referential it has exactly the properties required to prove incompleteness. It must be true, because if it’s false then it can be proved which would make it true, which is a contradiction. But this provides a true statement which cannot be proved, which is all that incompleteness says in the first place.
This is all very interesting for logicians and mathematicians, but what of the rest of us? Informally it just means that you can’t derive everything from first principles. Quell surprise. Not only that, but if the kinds of things we’re worried about are as arcane as the Gödel sentence then who cares? Are there more useful truths that fall into this category?
Yes there are. In the formal analysis of computers and algorithms there is a class of problems that are known to be unsolvable. That is to say that no computer, no matter how powerful or how long it ran, would be capable of getting the right answer. The exemplar for this class is the halting problem. “Halting” means that a computer program stops running, and solving the halting problem means writing a computer program that determines if some other program halts. This would be very useful to be able to do, as “halting” in the modern idiom is called a crash. If we could run our halting analysis on Microsoft Windows, for example, we could find out in advance whether it was going to give you the Blue Screen of Death. Software companies would pay a lot for a program that could do that.
Turns out it’s impossible. Imagine you have a program that can answer the halting problem. You can easily rig it up so that if the input program halts then your program goes into a loop a never halts, and if the input program doesn’t halt then your program does. Then you feed that program to itself as its own input. If it halts then it doesn’t, but if it doesn’t then it does, and we have our contradiction. Thus no such program can ever be written.
The self-referential element of Turing’s proof betrays the relationship it shares with Gödel’s incompleteness. In fact a great many problems in those two domains can be solved by reducing one to the other. So the question of what can be computed, and what can be known by “turning the crank” of a formal system of logic are one and the same. The fact that there are interesting truths (“does this program crash?” which must have a true or false answer) that cannot be computed is basically the same thing as true sentences that can’t be proven.
But why is this considered a big deal? Most of us over the age of about 24 are used to the idea that there are things that we just can’t know, no matter how much we learn. Oddly, however, Gödel’s result is taken as proof by some that man’s mind must be more than a mere machine. Mechanisms are bound by the limits of computation, which are also the limits of logical systems, but the human intellect somehow isn’t. Here’s Nørretranders from page 81:
The most interesting calculations take place inside a ‘computer’ that works completely differently from a Turing machine: the brain. Perhaps all the symbolic, mathematical computations the brain performs can be simulated by a Turning machine. But Turing machines cannot compute everything: As Gödel has shown, human beings know the truth of statements we cannot prove by mathematical symbols.
No, Gödel showed no such thing. As we have seen, he showed (by using formal symbol manipulation, by the way – not some oracular intuition) that every formal theory of a certain complexity is incomplete. He did not show, as Nørretranders claims, that humans are immune to incompleteness. It would be interesting to know which truths he thinks we know that are beyond the reach of any possible Turning machine (the formal model for all types of computation). The author sidesteps the question by asserting that we are different in “ways we do not know.”
Humans can’t solve the halting problem, for example. I know from harsh personal experience as a professional programmer that even the most carefully designed software – computer programs that have been meticulously engineered to prevent unwanted halting states – will still put up the dreaded “Application quit unexpectedly” dialog. We can solve the halting problem in specific cases, but only empirically. We have to walk through the steps in the debugger, comparing each state transition against our mental model until we understand why our brainchild wandered off into a cul-de-sac. That’s an “ah-ha” moment of realization, but it does not arise from pure contemplation. It’s not the result of the epi-computational powers of the brain but the ever so mundane application of everyday science. We compare expectations against reality and when we’re surprised, we learn.
The second remarkable claim in the quote above – although it does follow logically from the first – is that the brain is not a Turing machine. Hard to know what he’s talking about considering that anything that happens inside our bodies is equivalent to a Turing machine. Now, this may seem like a remarkable claim itself, but there’s nothing we’ve discovered in our biology that can’t – at least in principle – be “reduced” to a Turing machine. I put “reduced” in quotes because in practice such a machine can only exist as a hypothetical, but unless Nørretranders is postulating some unknown non-computable processes the physical brain can be reduced to a Turing machine.
Note that reduction does not mean simplification, which is a common misunderstanding that raises people’s hackles. The human mind is complex. A Turing machine equivalent would be just as complex (or more so, depending on how it’s constructed), having an upper bound of around ten to the ten trillionth power states. Very likely a minimally equivalent machine would be much less complex, but that’s not the point. No matter how complex it might be, the theoretical machine still bounds human potential by Gödel’s theoretical limitations. Not even quantum mechanics, like that proposed by Penrose and Hameroff, can save the brain from its physicality. Quantum systems can be described equally well by sufficiently complex, yet deterministic Turing machines.
I think the confusion arises from a common stereotype of computers. The idea that computers are logical and calculating at a low level drives people to think that high-level machine intelligence would be like Mr. Spock. It would reason with emotionless logic while we irrational and intuitive Kirks would run rings around it in real-world situations. But a machine intelligence would not manipulate symbols to understand the world the way a mathematician develops a proof. We already know that even algorithms we design ourselves are beyond our ability to understand completely, as in the halting problem; why could they not also generate behaviors that we would describe as creative rather than just linear or random? Given the overwhelming complexity of any software that would be able to approach the capabilities of the human brain, I think that’s pretty well given that such software would have emergent properties beyond our ability to predict from first principles.
But there remains a way that Gödel can cast a shadow across the notion of strong artificial intelligence. Perhaps some of the things we can’t know include the operation of our own mental machinery. The self-referential quality of a proof that said that for any intelligent system X, it cannot understand how X operates would be eerily familiar. Perhaps it’s not possible, in principle, for us to arrive at the truth of statements like “consciousness is caused by A” or “understanding means B” even though we know that some such statements must be true.
It’s possible, but I don’t think it’s the case. I believe, although this is on the fringe of science and I may be wrong, that strong artificial intelligence is not only possible – that the mind is reducible to computation – but that it is within the realm of engineering. We can understand our own understanding sufficiently to build machines that understand as much as we do. The halting problem hasn’t prevented us from flooding the internet with all kinds of software, even if it does crash from time to time. Likewise I don’t think Gödel is a serious obstacle for a satisfactory and useful theory of mind. The riddles of thought and consciousness can be unlocked empirically using the only tool that makes sense for the task: science.
- jack*
What's the difference between theory & practice? In theory, no difference!
Ha, ha.
More later....
Posted by: Ma'at's Feather | September 21, 2007 at 06:14 PM