6
$\begingroup$

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

$\endgroup$
30
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mehrdad Jun 16 '17 at 13:09
  • 5
    $\begingroup$ @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. $\endgroup$ – Andreas Blass Jun 16 '17 at 13:41
  • 3
    $\begingroup$ @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. $\endgroup$ – user2357112 Jun 16 '17 at 16:48
  • 2
    $\begingroup$ @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. $\endgroup$ – user2357112 Jun 17 '17 at 0:06
  • 2
    $\begingroup$ @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? $\endgroup$ – user2357112 Jun 17 '17 at 0:15
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Cruncher Jun 16 '17 at 12:00
  • $\begingroup$ I didn't say anything about halting. :) @Cruncher $\endgroup$ – Thomas Andrews Jun 16 '17 at 14:50
  • $\begingroup$ 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. $\endgroup$ – Cruncher Jun 16 '17 at 20:15
  • 1
    $\begingroup$ I didn't say $10^{-n}$. I said $9^{-1}\cdot 10^{-n}$, which is $0.0000\dots01111\dots$. @Cruncher $\endgroup$ – Thomas Andrews Jun 16 '17 at 20:24
  • $\begingroup$ Oh. Carry on then :) $\endgroup$ – Cruncher Jun 16 '17 at 20:58

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.