Is this number computable?

Question

My question is based on this answer:

https://math.stackexchange.com/a/458768/292477

Let $T$ be the Turing machine which looks for a proof of a contradiction in ZFC. If ZFC is consistent, then whether or not $T$ halts will be independent of ZFC. (Indeed, if not, then this would contradict Gödel's incompleteness theorem!) (Zhen Lin)

Given now this program that prints a number (print doesn't include a newline):

print "0."
for i = 0 to infinity:
    halted = execute_i_steps_of_the_given_turing_machine_and_return_true_if_it_halted()
    if halted:
        print "1"
    else:
        print "0"

I think it should be computable, but I'm not sure if the definition of the number is even valid.

Maybe someone could help me here? Is the number computable?

Thank you

score 29 · Accepted Answer · answered Jun 16 '17 at 00:24

29

Yes, this number is computable. Your definition of it is an algorithm for computing its digits.

More generally, you should be aware that not knowing what a number's value is has little to do with whether the number is computable. For instance, define a number $n$ as follows. If ZFC is consistent, $n=1$. If ZFC is inconsistent, $n=0$. This number is certainly computable: either the program that just outputs $1$ computes it, or the program that just outputs $0$ computes it. It doesn't matter that we can't determine (in ZFC) which of these programs is the right program to use: either way, there exists a program that works.

answered Jun 16 '17 at 00:24

Eric Wofsey

330,363

Hm, so I don't know if this is possible, but what if the consistency of ZFC is undecidable? Wouldn't that make n uncomputable? – user541686 Jun 16 '17 at 13:09
5

@Mehrdad No. Eric's answer did not assume that the consistency of ZFC is decidable. If it's undecidable, then we don't know which of the two programs "print 1" and "print 0" computes $n$, but one of them does. To say "$n$ is computable" just means that there is an algorithm computing it; it does not mean that we know what the algorithm is, nor that there is a proof (in your favorite formal system) that the algorithm is correct. – Andreas Blass Jun 16 '17 at 13:41
As I always note, the proof that $n$ is computable is highly contingent on either the assumption of consistency of ZFC (in which case $n=1$) or the excluded middle. For some reason, there are still some skeptics of the excluded middle out there... – cody Jun 16 '17 at 15:14
@AndreasBlass: I think our confusion is what you mean when you say "compute n". Do you mean "compute the set of potential values for n", or do you mean "compute n itself"? Because if the consistency of ZFC is undecidable, then I don't know how an algorithm could decide whether to print 0 or 1 without deciding what n is. – user541686 Jun 16 '17 at 16:19
3

@Mehrdad: Saying that an algorithm computes $n$ is a very weak statement; particularly, the algorithm doesn't have to have anything to do with how we defined $n$. It's purely a statement about the output of the algorithm, not what it does internally. One of the two programs print 0 and print 1 computes $n$; we don't need to figure out which. – user2357112 Jun 16 '17 at 16:48
@Mehrdad Concerning "I don't know how an algorithm would decide whether to print 0 or 1 ..." The algorithm "print 0" makes that decision quite easily. The algorithm "print 1" also makes that decision easily. These are the only two algorithms involved in my comment and in Eric's answer. You're probably thinking about more complicated algorithms that involve working with the axioms of ZFC. Such algorithms might indeed have difficulty deciding what to print, but they're not relevant here. – Andreas Blass Jun 16 '17 at 19:59
@user2357112: Let me give a different example to illustrate what I mean. Instead of ZFC, let's say I want a program to give me the first digit, in binary, of Chaitin's constant with respect to some fixed encoding (the digit after the leading zero, obviously). Are you going to claim that every digit must be 0 or 1, so therefore every digit is computable? That seems wrong to me, because it seems neither would be more "correct" than the other (regardless of whether or not we would know which one is correct). If you're not claiming this, then how is it different than our ZFC case? – user541686 Jun 16 '17 at 23:58
2

@Mehrdad: Indeed, every digit is computable. That doesn't mean that there's one program that can take an index and compute that digit; it means that for every digit, there is a program that computes it. Chaitin's constant itself is not computable; for that, we'd need the take-an-index-and-compute-that-digit program. – user2357112 Jun 17 '17 at 00:06
@user2357112: Yes, I'm not having trouble with the "all-the-digits" part. What I'm finding bizarre is that neither program computing the first digit might actually be correct regarding it, so to say one of them is computing that digit it is quite... jarring. You need to know one of them is correct (even if you don't know which one) but how do you even know one of 0 or 1 must be more correct than the other? – user541686 Jun 17 '17 at 00:09
2

@Mehrdad: How could neither of them be correct? Do you think that the binary digit you want to compute might be something other than 0 or 1? Are you working under a nonstandard model of logic? – user2357112 Jun 17 '17 at 00:15
@user2357112: I don't know if this is equivalent to excluding the law of the excluded middle (I'm not a mathematician), but I'm basically saying that if a binary number is (colloquially) "unknowable, even in approximation" (which is, hand-wavily, what Chaitin's constant seems to be, or at least that was my intention in choosing it) then it seems wrong to claim that one of two programs must somehow "know" the first digit, and that you merely don't know which one does. Do you see what's bothering me? If it's unknowable, both would be wrong in their claims. – user541686 Jun 17 '17 at 00:27

score 14 · Answer 2 · answered Jun 16 '17 at 00:56

14

Of course, this value is either $0$ or $2^{-n}$ for some $n$, and all of those numbers are computable, so this number is computable. (Assuming the result is treated as binary.)

If base $10$, then this value is either $0$ or $9^{-1}\cdot 10^{-n}$ for some $n$, and any rational number is computable.

answered Jun 16 '17 at 00:56

Thomas Andrews

177,126

technically this program doesn't halt when the TM halts. Once it prints a 1, it will continue printing 1's, making it more than 10^-n. Of course this doesn't change the computability of it – Cruncher Jun 16 '17 at 12:00
I didn't say anything about halting. :) @Cruncher – Thomas Andrews Jun 16 '17 at 14:50
Oh I know. But the number will have infinite trailing 1's after the first 1. so 10^-n is not accurate as that implies 0's after the 1. – Cruncher Jun 16 '17 at 20:15
1

I didn't say $10^{-n}$. I said $9^{-1}\cdot 10^{-n}$, which is $0.0000\dots01111\dots$. @Cruncher – Thomas Andrews Jun 16 '17 at 20:24
Oh. Carry on then :) – Cruncher Jun 16 '17 at 20:58

Is this number computable?

2 Answers2

Linked