Undecidability

"I used to be indecisive, but now I'm not so sure."

Boscoe Pertwee

A friend once presented me with a riddle: In the sequence OTTFF, what comes next? I replied, anything. My friend said no, SSENT came next, because what was clearly meant were the initial letters (in English) of the first ten integers.

I in turn remonstrated that this was one possible solution among an infinite possibility of solutions, that it would be the only possible answer if and only if the riddle stated that what it was referring to were the initial letters (in English) of the first ten integers, which admittedly would have rendered the riddle rather useless as a riddle. Nevertheless, it has its value as it stands, in logic.

Logically speaking, the additional information is essential for the answer the riddler wants. Without it, any answer would be as right as any other. Some answers would carry more meaning than others; some, the vast majority, would carry no discernible meaning at all, but meaningful or not, there is no valid way of deciding what the "right" answer is without the additional, riddle-effacing data.

To this day my friend considers me illogical and just plain contrary; even after I discovered that a similar riddle presented to the great philosopher Ludwig Wittgenstein had met with the same response as I had given, something I hadn't known at the time but which I found satisfying to learn.

What can we learn from this? We can learn of the existence of undecidability, which is as important--and perhaps more important--than learning what is true and what is false.

Logic and mathematics dictate that in the equation x + 1 = 2 there exists a limited number of possible solutions for x, in this case only one. But when we are faced with x + y = 2 there are an infinite number of solutions. The task of science is to determine which of the two cases reflects the true state of affairs and, if it is the first, to seek to achieve the one and only indisputably right answer. But the real problem is that it may not be possible to determine which is the case.

There is more than just the dilemma that mathematicians call the noncomputable questions that we know cannot be solved even with an eternity in which to work on them and an infinite number of computers. Heisenberg, Godel, Turing, and Chaitin have shown that some questions simply have no solution, even though the question is perfectly meaningful. But knowing something to be unknowable, noncomputable, is still better than being unable to decide whether it is or not. Knowing that Heisenberg's indeterminacy, Godel's incompleteness, Turing's halting problem, and Chaitin's incompressibility are certainly the case in this or that instance is a form of knowledge. Knowing we are up against a brick wall is very useful. But if there remains the niggling doubt about the wall's steadfastness under some perhaps indescribable, uncontemplatable circumstance, we are in existential hell, where we may or may not have free will, where our course of action, our ability to know, may or may not be fully predetermined. It is a no-w in situation with bells on. For we can't even know for a fact that we have lost. We are in eternal limbo, or rather, we can't be absolutely sure were in limbo or not. That, in a nutshell, is undecidability.

The question is, does the universe present us with this sort of riddle because it is intrinsically unknowable whatever the level of intelligence brought to bear on it? Is it always possible to know if all meaningful questions that can be raised are solvable or not, without first working through eternity to find out? We know that some meaningful queries fall into the category of insoluble, but how can we determine that this or that particular query is or isn't? We are thrown back on the too-oft-quoted reflection of J.B.S. Haldane (too-oft-quoted by him, among others) that the universe may not only be queerer than we imagine, but queerer than we can imagine. To which I can only add, how can we decide between the two possibilities?

Are you beginning to get the picture? If so, it's worse than that. Because it's no help to try escaping the dilemma by shrugging off and remarking that human logic and comprehension are, after all, not the be-all and end-all, as some philosophers have, happily (Kant) or unhappily (Schopenhauer). We can never know the thing-in-itself, Kant concluded, with a sigh of profound relief that the matter was now safely knowable, and Schopenhauer agreed, with his sigh of capitulating despair. End of problem. Oh really?

Well then, how can we be certain, so absolutely sure, that human thought cannot (eventually if not now) be the beall and end-all? The universe is rather large but the laws that govern it are few and their complexities are unlikely to be infinite. There maybe [10.sup.80] atoms in the known universe but each and every one of them obeys exactly the same rules. The workings of the universe, as the physicist John Barrow reminds us, is "the complicated coming together of many simple things." Corral and come to comprehend the simple, and the complicated will come to you of its own accord. Maybe.