2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Most people, I think, are comfortably Platonist on $\Pi_1$ sentences of arithmetic. Either there is a counterexample or there isn’t. If Goldbach is independent of ZFC this simply means it is true but ZFC lacks the requisite power to prove this fact. (And the fact that we’ll probably never know the value of this digit only reinforces the fact that the number is not computable.) $\endgroup$ – spaceisdarkgreen Dec 18 '18 at 22:21
  • $\begingroup$ (I say “probably never know” only in the unlikely case that Goldbach turns out independent of ZFC. Perhaps that’s somewhat too strong even still, but as you say, replace Goldbach with something harder.) $\endgroup$ – spaceisdarkgreen Dec 18 '18 at 22:44
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the comment. It sure helps with the understanding, however I am still left with a burning follow up question. I edited the OP to include it. $\endgroup$ – SmileyCraft Dec 18 '18 at 21:58
  • 1
    $\begingroup$ Your secondary question makes things a bit unclear. Maybe karagila.org/2015/name-that-number can help a bit? $\endgroup$ – Asaf Karagila Dec 18 '18 at 21:59
  • $\begingroup$ Can you point out what makes things unclear about my secondary question? I do realise that my definition of super-definable might not be well-defined, but I find it hard to define what I have in mind. $\endgroup$ – SmileyCraft Dec 18 '18 at 22:02
  • $\begingroup$ What does it mean to be "dependent on ZFC"? Any incomplete foundational theory is not "enough", and by Gödel, any reasonable foundational theory is not complete. Again, read the link. $\endgroup$ – Asaf Karagila Dec 18 '18 at 22:04
  • $\begingroup$ That link is indeed satisfactory, thank you for that! I guess you can say that, for a super-definable number, there must be a string of symbols describing a proof that determines the $i$'th digit. Hence, we can write a program iterating through all strings of symbols until it finds such a proof, so the number is computable. $\endgroup$ – SmileyCraft Dec 18 '18 at 22:14
1
$\begingroup$

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 :)

$\endgroup$
  • $\begingroup$ This is a very interesting answer as well! I guess this argument generalizes to all digits of Chaitin's constant. If it is independent of ZFC whether a program halts or not, then it can not halt at some point, as then you can show within ZFC that the program would halt. $\endgroup$ – SmileyCraft Dec 18 '18 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.