The number of all possible decimals is an uncountable infinity. But those that are like π or √2 can be computed with a finite computer program. There is a countable infinity of these, because the number of all computer programs is countable.
This is what Greg Chaitin figured out, based on the insights of Alan Turing and Kurt Gödel:
In any computer language, there is a finite number of symbols, from which all programs can be created. So you can think of every computer programs as just a long word. Sort these words out from the shortest (1 letter) on up, and within all programs of a given length, put them in alphabetical order. (In some languages, blank space is important, and you may need to think of blank space as one letter of the alphabet.)
Next, go through and cross out the ones that contain syntax errors, so that a computer would never even try to execute them. For example, they may contain an open parenthesis without a closing, or they may specify a loop without a terminating condition. You can think of doing this as you go along; for example, as you finish making the alphabetized list of all programs of length 7 symbols, you make another pass through your list and eliminate the nonsensical ones.
This well-defined procedure yields a list of all computer programs. It’s an infinite list, with a beginning and an ordering and no end.
Now, some percentage of these programs will ‘halt’. They will come to a natural conclusion, and the computer will produce some result (a number or a list of numbers, or a string of text) and then the computer will be ‘done’ with the program. There are other programs that will never halt, stuck in some kind of infinite loop, trying something over and over that never attaining the criterion for conclusion. Chaitin asked the question, what percentage of your list of programs will eventually ‘halt’? He called this number Omega.*
Omega is a number somewhere between 0 and 1. It’s well-defined, in that you have a procedure for calculating its value. More precisely, you have an infinite procedure that will give you better and better approximations to Omega the longer you continue. But it’s different from computing, say, the value of π. You can calculate the first 40 digits of π and be sure that as you keep going in your calculation, only digits beyond those 40 are at stake. But Omega is more mysterious. There’s no way to know how far you are along in the computation, and which digits have been established beyond further change.
Here’s the punch line: The single number Omega contains all of mathematical knowledge. If you knew Omega, you would know the answer to every question that can be asked about numbers (or geometrical objects, which can be represented as coordinates). You would be able to decide, for every theorem, whether it is true or it is false – even some theorems for which no proof may exist†.
Omega is the ultimate repository of mathematical truth.
*There’s a little further homework to be done in defining Omega rigorously. How are you to know when to give up on a computer that’s running a program and say it will never halt? Chaitin pointed out you don’t ever need to make that call. Just start the first program in your list, run ‘one step’ of that program, then start the second program and run it for one step, and the first program for an additional step, then start the third program and step the first two programs, and so forth. Whenever any program terminates, make a note of that fact, and update your estimate of Omega, dividing the number of programs that have terminated by the total number, including those that are still running.
† There are some mathematical statements that are true but not provable. In fact, there are an infinity of such statements. This is Gödel’s theorem. These statements are part of Omega, but the catch is that they’re in the part of Omega that we never get to see. If we were to set out to compute Omega§, we would, along the way, encounter computer programs that correspond to proofs of every provable theorem. A proof, by definition, is finite, and there are a countable number of them, so with enough patience we would eventually come across every proof. But at whatever point we give up, there are some computer programs already in our list that are still running, but will soon come to a halt, while others in our list will never halt; and because we stopped at some finite time, we don’t yet know which is which.
§ In fact, a computer has been programmed to calculate Omega, and after months of computation, it generated the first 19 digits, reproduced in the header above. How can they be sure that these 19 digits won’t change as the computation proceeds? I’ve said that as you calculate Omega, you can’t know how much progress you’ve made. In fact, Chaitin himself billed Omega as being the ultimate in unknowability. ‘Strongly non-computable’ is the way he put it. Then along come Calude, Dinneen and Shu, and they find the value of Omega to 19 digit accuracy. I don’t understand how they did it.
Another question: What gives us confidence that omega isn't zero, to an arbitrarily high precision? The fraction of programs that halts may be negligibly small...and then the number zero would contain no information at all about mathematics.
https://www.worldscientific.com/doi/abs/10.1142/S0218127407018130
There's a lot I don't understand about this. You can know for sure that a program is going to halt, but you never know that it WON'T halt at some point in the future. So you can't just start with small programs and go one-by-one to see if they halt or not.
Instead, you run the first program one step, then you run the first two programs 2 steps, then the first three programs 3 steps, etc.
But you might run the first program 10 steps, the second program 20 steps, the third program 30 steps, etc. How do you know that this procedure will eventually converge to the same omega as the other procedure?
For that matter, how do you know that you won't run into a very different pattern when programs have length 10 billion characters, and the algorithm that looked like it was converging for the first 9 billion characters now starts to move toward a very different number?