$0^n$ in the digits of Pi

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 know which of 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 , but it 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.