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

Question

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.

Answer 1

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

Answer 2

Just posting a slight elaboration on JeffE's answer.

We know that two functions/cases exist that can compute the function f(n):

1. A function that always returns true (for all n, there exist n number of consecutive 0's)
2. A function that will return true if n is smaller than an integer N, where N is defined as the maximum length of consecutive 0's that exist in the given irrational number (otherwise it returns false).

One and only one of these functions can be correct. We do not know which, but we know for certain that an answer exists. Computability requires that a function exist that can determine the answer within a finite amount of steps.

The number of steps in case 1 is trivially bound to just returning 1.

In case 2 the number of steps are also finite. For every integer $N$ we can construct a Turing machine $T_N(n)$ that accepts if $n < N$ and otherwise rejects in finite time. So not knowing an upper bound on $N$ doesn't matter. For every $N$ there exists a Turing machine, namely $T_N(n)$, that computes correctly whether $n < N$ (we don't know which of these are correct, but it doesn't matter, one exists).

While it may not be possible to choose between the two cases (though one seems more likely than another), we know that exactly one of them must be correct.

As a side note: our solution supposes that while we can not determine which function will elicit a correct value the essence of computability does not rely on the constructability of the proof. Pure Existence is sufficient.

Answer 3

Step 5 of the following proof attempt is unjustified, and in fact wrong - a counterexample can be found here. (thanks, Yuval; it did feel like the sketchiest part of the sketch). I've left the answer here as I think the mistake is instructive.

---

First off: JeffE's pair of answers is sufficient; f is computable either way.

A brief detour, though, into an attempt at a sketch of a proof by induction:
Premise R: $\pi$ does not repeat.
1. Look at $\pi$ in base 2. This is mostly to cut down on the number of cases.
2. No matter how far down the line you go, you will always find another 1 somewhere: the alternative is all zeros, which would mean $\pi$ starts repeating, which goes against R.
3. Same goes for going down the line and finding 0.
4. Expand to two-digit sequences: you can't stop finding either 01 or 10 (that is, places where it switches), because otherwise $\pi$ would start repeating on 1's or on 0's. Similarly, you can't stop finding 11 or 00, because otherwise it starts repeating on 1010101...
5. The inductive step: each finite sequence has to appear an infinite number of times, because the alternative is that $\pi$ starts repeating on one of the shorter sequences, which contradicts R.