all finite start sequences of decimal representation of $\pi$ decidable?

Question

$L^1 \subset \{0,\dots 9\}^*$ consits of all finite start sequences of the decimal representation of $\pi$ (without comma). Is L decidable?

I guess it is not, but I do not know how to prove it. Help is much appreciated

Answer 1

This is easily decidable by the following procedure:

1. Count the length of the input string.
2. Compute that many digits of $\pi$.
3. Accept if the digits you computed are identical to the input string; otherwise reject.

---

If you can't assume as a known fact that it's possible to compute digits of $\pi$, then the question becomes one about real analysis more than one about computability. There are then various possible approaches; a relatively simple one would be:

To ask whether, say, 3141592653521 is in your $L$ is to ask whether $\pi$ is between $\frac{3141592653521}{1000000000000}$ and $\frac{3141592653522}{1000000000000}$. (It can't be equal to either of these endpoints because we know $\pi$ is irrational). So what we need is to be able to compare $\pi$ to arbitrary rational numbers. We can do that by this procedure

1. If $x<3$ then $x<\pi$.
2. If $x>4$ then $x>\pi$.
3. Otherwise, if $\cos \frac x2 > 0$ then $x<\pi$, and if $\cos \frac x2<0$ then $x>\pi$.

For the last step we can compute the cosine from the power series: $$ \cos x = 1 - \frac12 x^2 + \frac1{24}x^4 - \frac1{720}x^6 + \cdots + (-1)^n \frac{1}{(2n)!}x^{2n} + \cdots $$ After the first two terms (when $x<2$), this is an absolutely decreasing alternating series, which means that we can know the sign of the limit in finite time by finding the first time where we have just added something and yet the sum so far is negative, or we have just subtracted something and yet the sum so far is positive. Since we know the limit is not $0$ (the cosine of a rational number never is), this will happen sooner or later, and therefore our decision procedure terminates.

Note that all numbers encountered during this computation are rational, so we can keep everything as exact fractions throughout -- there's no floating-point arithmetic involved.