Is Chaitin's constant well-defined?

638 Views Asked by At

Chaitin's constant is this amazing example of a real number that we can define, however we can not compute. However, I have a doubt in the claim that the constant is well-defined.

If I understand correctly, however this might very well be the part where I'm wrong, the way Chaitin's constant is defined is by defining a sequence of programs, and then defining the $i$'th binary digit of our number to be $1$ if the $i$'th program halts, and $0$ otherwise. If this sequence enumerates every program, then, because the halting problem is provably undecidable, the constant is uncomputable.

My problem lies in the claim that every program either will halt or not. Take for example the algorithm that enumerates every even natural number greater than $2$ and tries to write it as the sum of two primes, until it finds a number that can not be written this way, at which point it will halt. This program will halt if, and only if, the Goldbach conjecture turns out to be wrong. However, we do not even know if the Goldbach conjecture might be independent of ZFC. If the Goldbach conjecture is independent of ZFC, then is the digit of Chaitin's constant corresponding to this program well-defined?

Even if the Goldbach conjecture turns out to be dependent of ZFC, I doubt that the halting problem is dependent of ZFC for every fixed program.

EDIT: So this apparently depends on the definition of a definable number. A number does not have to be dependent of your universe to be definable. However, then the following follow up question comes to my mind.

If we define a super-definable number to be a number both definable and dependent of ZFC, does there exist a super-definable uncomputable number? Is this known?

EDIT 2: I mean "dependent of ZFC" to say there is a string of symbols in ZFC that determines the value of each digit. But then we can write a program iterating through all strings of symbols until it finds such a string, so the number is computable.

2

There are 2 best solutions below

6
On BEST ANSWER

Look at the number $x\in[0,1]$ whose $n$th digit is $0$ if and only if $2^{\aleph_n}=\aleph_{n+1}$ and $1$ otherwise. This is certainly a definable real number, I just defined it, but it is consistent to be $0$ and it is consistent to be $1$, and in fact, it is consistent to be any other number whose decimal expansion is only $0$ and $1$. Being definable means you are constant within a fixed universe of your theory. It means it is provably a fixed number. But what is the value? That might depend on your universe.

Or, you know, just take $x=\begin{cases}0 &\rm CH\\ 1 &\lnot\rm CH\end{cases}$ also works.

The key thing to understand is that being definable is Platonistically-constant, but not necessarily constant if you allow for a more multiversial approach (or even a more formalistic approach) to mathematics.


But this is very much like saying that $\pi_d$ is half of the length $\{x\in\Bbb R^2\mid \|x\|_d=1\}$, when $d$ is a metric on $\Bbb R^2$. It will invariably depend on the metric you choose.

1
On

Actually there is no just one Chaitin's constant since the definition depends on the (universal) Turing machine used to define it - see

http://mathworld.wolfram.com/ChaitinsConstant.html

But once the Turing machine is chosen the constant is perfectly well defined. The program testing the Golbach conjecture (running on a given Turing machine) will stop or not, and that will have an impact on the value of the corresponding Chaitin's constant regardless of our ability to determine it. If the Golbach conjecture turns out to be undecidable in ZFC that would imply that it is true because its falsehood would be unveiled by a counterexample and the program would eventually stop. We just would be unable to find out using only the tools of ZFC. That would translate on the impossibility (in ZFC) to determine the value of Chaitin's constant within some degree of accuracy, but it won't change its value.

Edit: After I wrote my answer I noticed that spaceisdarkgreen expressed a very similar idea it the comments. I guess I am a $\Pi_1$ platonist :)