[Math] Is this number computable

computabilityturing-machines

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

Best Answer

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.

Related Solutions

Logic – Diagonalization on Turing Machines and Proofs: Where Does the Argument Fail?

The issue that you have run into is that you need to specify the system in which these proofs are being carried out. The set of "all possible proofs" is not r.e. - only the list of proofs in some fixed effective theory.

However, as a corollary of the incompleteness theorems, we know that such systems are very bad at talking about their own proofs. So, although ''we'' can use $T'$ and $P'$ to construct a new machine, this construction cannot be carried out within the same system which was used to make the list $P'$ in the first place. Instead, as it turns out, we will need to form $P''$ in a stronger system. This does not lead to a contradiction because $P''$ will not be in the previous enumeration.

Functions corresponding to Turing machines that might not halt but consume bounded tape

Firstly, bounded memory use is not an artifact of Turing machine mechanics. You can ask the same question for any Turing-complete programming language, where it corresponds to whether or not the program uses unbounded memory (defined as appropriate) on a run. For example, if the language supports integer and string variables, then bounded memory means that the integer variables have bounded value and the string variables have values with bounded length.

Secondly, a bounded-memory program must on every input either halt or eventually cycle. I doubt there is a nicer characterization. Note that it is not known whether even the following simple non-halting program f uses bounded memory on every positive integer input or not:

def f(n):
  while n>0:
    if n%2==0: n=n*3+1;
    n=n/2;

Also, it is easy to prove that there is no program that can decide whether a given input is a bounded memory program or not. In fact, via a simple generalization of f, one can show that this decision problem is not only undecidable but actually $Π_2$-complete, implying that it cannot be solved even by a program that has access to the halting oracle (see here).

Best Answer

Related Solutions

Logic – Diagonalization on Turing Machines and Proofs: Where Does the Argument Fail?

Functions corresponding to Turing machines that might not halt but consume bounded tape

Related Question