How can it be decidable whether $\pi$ has some sequence of digits?

Question Detail: 

We were given the following exercise.

Let

$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

Prove that $f$ is computable.

How is this possible? As far as I know, we do not know wether $\pi$ contains every sequence of digits (or which) and an algorithm can certainly not decide that some sequence is not occurring. Therefore I think $f$ is not computable, because the underlying problem is only semi-decidable.

Asked By : Raphael

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/367

Answered By : JeffE

There are only two possibilities to consider.

• For every positive integer $n$, the string $0^n$ appears in the decimal representation of $\pi$. In this case, the algorithm that always returns 1 is always correct.

• There is a largest integer $N$ such that $0^N$ appears in the decimal representation of $\pi$. In this case the following algorithm (with the value $N$ hard-coded) is always correct:

  Zeros-in-pi(n):  if (n > N) then return 0 else return 1 

We have no idea which of these possibilities is correct, or what value of $N$ is the right one in the second case. Nevertheless, one of these algorithms is guaranteed to be correct. Thus, there is an algorithm to decide whether a string of $n$ zeros appears in $\pi$; the problem is decidable.

---

Note the subtle difference with the following proof sketch proposed by gallais:

1. Take a random Turing machine and a random input. 2. Either the computation will go on for ever or it will stop at some point and there is a (constant) computable function describing each one of these behaviors. 3. ??? 4. Profit!

Alex ten Brink explains:

watch out what the Halting theorem states: it says that there exists no single program that can decide whether a given program halts. You can easily make two programs such that either one computes whether a given program halts: the first always says 'it halts', the second 'it doesn't halt' - one program is always right, we just can't compute which one of them is!

sepp2k adds:

In the case of Alex's example neither of the algorithms will return the right result for all inputs. In the case of this question one of them will. You can claim that the problem is decidable because you know that there is an algorithm that produces the right result for all inputs. It doesn't matter whether you know which one that algorithm is. 10