QV3: Incompleteness

The Quantum Veil
Part 3
Incompleteness

In September 1930 at Konigsberg (now Kaliningrad, Russia), Kurt Godel stunned the group of mathematicians and logicians by announcing his famous incompleteness theorem. The proof was not published until 1931, so it took awhile to sink in. But the end result was a radical rethinking about mathematics. Why was Godel’s theorem so unexpected? It helps to remember that there was a movement in mathematics at that time to encapsulate all of mathematics into a formal system of axioms and theorems. Part of the motivation was to eliminate the uncertainties associated with mathematical proofs. David Hilbert, a German mathematician, initiated a program in the 1920’s to formalize all of mathematics. Before Hilbert started his program, Bertrand Russell and Alfred North Whitehead published a 3-volume work named Principia Mathematica, which was an attempt to derive all mathematical truths from a single, consistent set of axioms. The title of the article published by Godel in 1931 was On Formally Undecidable Propositions in Principia Mathematica and Related Systems I.

So what did this famous theorem prove? In as simple a statement as I can make, it says that there is no consistent, formal system that can encapsulate all of mathematical truth. Put another way, it says that there will be some true mathematical propositions that cannot be proven within such a system. Therefore, any formal system is incomplete and the hopes of mathematicians who wanted to encapsulate all of mathematics in a single formal system were dashed.

(Incidentally, there is a very readable and fascinating account of the history of this period entitled “A Hundred Years of Controversy Regarding the Foundations of Mathematics” (http://www.umcs.maine.edu/~chaitin/unknowable/ch1.html) by Gregory Chaitin, mathematician and computer scientist.)

Why is this relevant? Well, Roger Penrose’s insight is that for Godel to arrive at this theorem, he must have been using, in his own thinking, something besides a formal mathematical system! Here is his summary:

• “It is in mathematics that our thinking processes have their purest form. If thinking is just carrying out a computation of some kind, then it might seem that we ought to be able to see this most clearly in our mathematical thinking. Yet, remarkably, the very reverse turns out to be the case. It is within mathematics that we find the clearest evidence that there must actually be something in our conscious thought processes that eludes computation. This may seem to be a paradox – but it will be of prime importance in the arguments which follow, that we come to terms with it.” (Shadows of the Mind, Oxford University Press, 1994, p. 64.)

Penrose follows this start to Chapter 2 with over 50 pages of explanation, example, argument and counter-argument concerning an extension of Godel’s theorem that applies directly to computers. This extension is named the ‘halting problem’ and is due to Alan Turing, one of the key contributors to the theory of modern digital computers. The ‘halting problem’ states that it is not possible to write a computer program that can, in general, determine if another computer program will ever produce an answer (which is when a computer program halts or stops processing.) Most of this material presents the usual objections to Godel-type arguments of incompleteness along with Penrose’s responses to those objections. Penrose is “trying to show that (mathematical) understanding is something that lies beyond computation, and the Godel (-Turing) argument is one of the few handles that we have on this issue.”

In Chapter 3, “The case for non-computability in mathematical thought,” Penrose tackles the issue directly. He considers several possible ways the Godel argument might not apply. Perhaps mathematicians are knowingly or unknowingly using an unsound algorithm. Perhaps they are using an unknowable algorithm. He considers natural selection; he considers multiple algorithms; he considers learning algorithms; he considers environmental input; he considers random events; he considers chaos theory; he considers acts of God. It is interesting to hear what he has to say about this last point:

• “Possibly there are some readers who are inclined to believe that such an algorithm could indeed simply have been implanted into our brains according to some divine act of God. To such a suggestion I can offer no decisive refutation; but if one chooses to abandon the methods of science at some point, it is unclear to me why it would be reasonable to choose that particular point!” (Shadows of the Mind, Oxford University Press, 1994, p. 144-145.)

Penrose is leading us to the point where we may well decide that some divine activity is taking place, but he will not say so directly. Ultimately he drops us off at the doorstep of quantum indeterminism and we will have to make our own decision. But the journey is well worth the effort.

His conclusion at the end of chapter 3, after about 80 pages of such arguments as above, is that “there is something essential in human understanding that is not possible to simulate by any computational means.” Although Penrose does not directly address free will and similar experiences, I think that he subsumes those experiences under the general term ‘consciousness.’ I think the act of understanding requires an act of will to choose the correct interpretation from among the various possible alternatives.

At this point, I should add that I am very much inclined to agree with Penrose. I have spent over 30 years analyzing, designing, programming and testing complex computer systems. I have seen the promise of automatic programming, programming by computer, come and go. If anything, computer programming is a more exact use of logic than mathematical reasoning and, so far, no computer program has been able to do what the skilled human computer programmer can do and that is analyze and understand a problem in ways that are helpful in designing a robust solution. From my experience, there comes a point in the analysis and design of a system when one must choose the best path through a maze of possibilities. There is inherent risk in that choice and many times it takes courage to proceed along a chosen path.

This is not a new insight. More than 40 years ago, Joseph Weizenbaum created a computer program named ELIZA that could converse in English somewhat like a non-directive psychotherapist. He wrote a book, Computer Power and Human Reason (W. H. Freeman, 1976,) that presents his views on the proper role of computers in society, a role that he strongly believed should be subservient to human will and subject to human moral judgment. Weizenbaum reached this conclusion not by the Godel-like arguments of Penrose, but from human experience of the way that life is. At the conclusion of this book, he argues that the teacher of computer science must resist the temptation to arrogance because his or her knowledge is somehow ‘harder’ than the knowledge of most people:

• “It the teacher, if anyone, is to be an example of the whole person to others, he must first strive to be a whole person. Without the courage to confront one’s inner as well as outer worlds, such wholeness is impossible to achieve. Instrumental reason alone cannot lead to it. And there precisely is a crucial difference between man and machine: Man, in order to become whole, must be forever an explorer of both his inner and his outer realities. His life is full of risks, but risks he has the courage to accept, because, like the explorer, he learns to trust his own capacities to endure, to overcome. What could it mean to speak of risk, courage, trust, endurance and overcoming when one speaks of machines?” (Weizenbaum, Computer Power and Human Reason, W. H. Freeman, 1976, p 280.)

I call this the existential approach and I hope to return to it in a future segment because, for most people, that is the only source of valid knowledge about the way that the universe works.

The Penrose argument is an argument from logic, not from general life experience. It is important because it sets a boundary for what we can legitimately conclude based on our own existential analysis. The Penrose argument is the most complete attempt that I know of to say definitively that the human mind can do something that no computer, no mater how powerful, can do. Whether you call it understanding, awareness, insight or something else, the conclusion is that something non-computational and therefore non-deterministic is taking place in human consciousness. So where does this non-computational capability come from? I will take up that question, and Penrose’s answer to it, in the next segment.