Can we compute the fugitive integers k(n)

Question

Is this function $k:\mathbb{N}\to\mathbb{N}$ computable, which is defined as:

$$ k(n)=\begin{cases}\text{the position of the first $n$ consecutive 9's in $\pi$}\\0\text{ if there is no such position}\end{cases} $$

The term "fugitive integer" is taken from

Intuitionism: An Inspiration?
Wim Veldman - 2021
https://arxiv.org/abs/2102.01561

Answer 1

If excluded middle holds then the function is computable, as follows.

Consider the set $$S = \{n \in \mathbb{N} \mid \text{there are $n$ consecutive 9's in $\pi$}\}.$$ By excluded middle $S$ is bounded or unbounded. Consider both possibilities:

1. If $S$ is bounded then it has a largest element $m \in S$. The function $f$ can be computed as follows: on input $n$, if $n > m$ output $0$, otherwise compute the decimal expansion of $\pi$ until $n$ consecutive 9's are encountered, and output the position.

2. If $S$ is unbounded then $f$ can be computed as follows: on input $n$, compute the decimal expansion of $\pi$ until $n$ consecutive 9's are encountered, and output the position.

So, you see, $f$ is computable, but it is prety difficult to know which of the two candidate algorithms for it is the right one. (Note: we do not have to compute $m$ in the first case, we simply hard-wire it into the alrogithm, whatever it is.)

Answer 2

It is conjectured that $\pi$ is a normal number, which would imply that your function $k(n)$ is computable; since there would always exist a sequence of $n$ consecutive $9$'s in the digits of $\pi$; in particular, it would never take the value $0$ and be non-decreasing. Since very little progress has been made on this conjecture, I believe we don't have an answer to your question as of now.

The reason why this is conjectured is because we know that the set of real numbers which are not normal has measure zero, and so if you pick a real number in the interval $[a,b]$ at random, you pick a normal number with probability $1$, implying that the function $k(n)$ for this number would be computable. So we know it's almost always the case for a random number, but when it comes to specific numbers, we know very little.

Hope that helps,