Consider the following function:

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

Is $f$ computable?

- $0^n$ refers to $\underbrace{00000 \ldots 0}_{n\, \text{times}}$

Yes
We do not know yet
No

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

A very important result that will be used in this solution twice is the following: if we have a number of propositions $A_1, A_2, A_3, \ldots$ such that at least one of them is correct (that is, $A_1 \vee A_2 \vee A_3 \vee \ldots$ is true), and each of these propositions implies the same thing (that is, $A_i \rightarrow B$ for all $i$ ), then the latter thing is true ( $B$ is true). When there are two propositions, this is a special case of

constructive dilemma. This is obvious when put this way, but its power is when we don't knowwhichof the $A_i$ should be true, but we can conclude $B$ is true regardless.We claim $f$ is computable. To see this, note that there are only two cases: either $0^n$ (a run of $n$ consecutive 0's) exists in the decimal representation of $\pi$ for arbitrarily large $n$ , or there is a greatest integer $m$ such that $0^m$ exists in the decimal representation of $\pi$ (but $0^{m+1}$ doesn't).

Case 1: There are arbitrarily long runs of 0's.Thus for any $n$ , $f(n) = 1$ . This function is clearly computable: the algorithm simply returns 1 and halts.

Case 2: There is a longest run of 0's (and longer ones don't exist).Suppose that the maximum length is $m$ . Then $f$ is also computable: if $n \le m$ , then return 1, otherwise return 0. In either case, the function halts. Note that

we don't know what $m$ is, butit doesn't matter. This uses the above result; $A_i$ is the proposition "the longest run of 0's is of $i$ 0's", and $B$ is the proposition " $f$ is computable". Clearly one of the $A_i$ 's is true (from the assumption of the case; if none is true, we have Case 1), and we have just shown $A_i \rightarrow B$ for all $i$ . Thus $B$ is true; $f$ is computable.Now, those two cases are exhaustive, and so we can apply the result again. Either Case 1 or Case 2 is true, but in both cases, $f$ is computable. So the end result is

$f$ is computable, even though we don't actually know which case is true.