Yesterday (2006 February 9), I ran into two numbers that are important in our lives. They help describe the logical world we live in, as well as our state of well being in it. Neither of these numbers can be computed precisely, for different reasons, but they nevertheless exist.
One came in an issue of Scientific American which arrived in my mail yesterday. That magazine contained an article called "The Limits to Reason", which describes a number defined by Gregory Chaitin and denoted by Ω, capital Omega. This number is defined by the probability that if a randomly chosen computer program is chosen, that it will halt. Now programs on these PCs that we use need to be designed to halt. If it doesn't, the computer freezes up, and I call that "bombing" or "crashing". So in a sense, Ω is the probability that if a computer program is run, that it will not bomb the computer. This number is not computable. In terms of my paper Hamlet II, it is an ultimately indescribable number. In that article, I show how Georg Cantor demonstrated that such numbers exist, but I did not give any examples of such numbers. Ω is an example of such a number. (Don't confuse Ω with ω, the first transfinite ordinal number, defined by Cantor, and Ω, sometimes used to denote the class of all transfinite ordinal numbers. Ω is a real number.)
Why? It derives from the famous Halting Theorem of Turing, which says that no computer program can be constructed that inputs a computer program as input and outputs whether the program, if executed, will halt or not. Another way of putting it: There can be no perfect Crash Guard. The proof of this, in a sketchy form, can be given like this. Suppose there were such a program P. Let's hack that program. Find the places in the code where it says that the input program will halt, take out the termination statement and replace it with something like A: go to B; B: go to A. Then go to those places that say that the input program will never halt, and put in the warning "Do not execute this program. It will never end, and it will bomb your computer." and follow that with a statement that halts the program. Call the hacked program H. H still inputs computer programs as input, so feed it the program H itself. Suppose this program halts. Then H will detect that, and it will go into the AB loop above and never halt. Contradiction. Suppose H never halts. Then H will detect that, print out the warning and stop. That is also a contradiction. This shows that H cannot exist, and therefore P can't either. There are many important derivative results of this theorem. For example, given a group with generators and relations and an element of the group, no computer program can compute whether that element is the identity element or not. Also there is no terminating algorithm that solves all Diophantine (answers have to be integer) systems of general polynomial equations.
And it shows that Ω is ultimately indescribable. For if I could describe it to you, then I could write a computer program to compute it, and then I could hack that program to yield a program that tells whether a computer program will halt, counter to Turing's theorem.
Chaitin has a number of other interesting observations. The most interesting, I found, was this remark:
Comprehension implies compression.
This says that in order to comprehend something, a simple description or program needs to be found for it. For example, to describe π, I can say add up with alternating signs all the reciprocals of odd integers and multiply the result by four. Or perhaps I can simply say the circumference of a circle divided by the diameter. On the other hand, to describe 0.92659876193865, the simplest way I know is to say 9, 2, 6, 5, 9, …, 5 after the decimal point, which is as long as the number is. So π is a simple number, but 0.92659876193865 is not. To understand π, I think of the circle. So the more I compress a description of a number or mathematical concept, the more I understand. Hence Chaitin's statement.
Another comment he made was on the principle of sufficient reason. That says that everything has a cause. The condensation of water vapor causes rain, for instance. But Chaitin says that there has to exist "irreducible" numbers, numbers as complicated as 0.92659876193865 that can't be described any simpler than naming the digits. If we generalize this to arbitrary mathematical concepts, there must exist mathematical statements that have no cause. Not even for mathematics is the principle of sufficient reason true. Some things are just the way they are. "Cause was not the reason for the evening", says the singing group America; in fact, the entire song "Tin Man" seems to have no cause or reason for it; it just is.
The other number I met yesterday was in a library book entitled The Number, by Lee Eisenberg. This number is more prosaically defined. Each person has The Number, and for him it is that sum of money, such that if he possesses it, it will enable him to live comfortably for the rest of his life. There is a simple way to compute this number, given you can get the inputs. Total up all the expenses you have or would have in the life style you want. Divide the result by the interest that a typical money market fund or a CD gives, and the result is, for you, The Number. For example, if your expenses are $50,000 per year and the interest rate is 5%, then $50,000/0.05 = $1,000,000 is The Number. That's right, a modest amount like that yields a million dollars. That is a point made by the author: many, in fact, the majority, of Americans simply don't have The Number. This will result in trouble for them later when they age and retire, and the sum total of them will seriously jolt the national economy. So it is an important discussion, and I ask you to figure out what is Your "The Number". And by the way, it is computable, given that your expenses and the ongoing interest rates, are computable. It is not a Chaitin's Ω.
