# Decide whether a given string appears in the binary expansion of π [duplicate]

Is it known whether the language $$L_π = \{w\in\{0,1\}^* : w\text{ appears in the binary expansion of }π\}$$ is decidable?

• $$L_π$$ is easily recognizable (a.k.a. computably enumerable).
• A trivially decidable very classical variant of the language is $$\{n:0^n\text{ appears in the binary expansion of }π\}$$.
• There is a conjecture that $$π$$ is disjunctive in base 2, that is its binary expansion contains all possible finite strings: It implies decidability since in such case, $$L_π = \{0,1\}^*$$.

So a detailed version of my question:

1. Can we prove decidability without assuming the conjecture?
2. Does decidability implies something about the conjecture?
3. Do we have similar results for other well-known irrational constants?
• How is $0^n \in \pi$ trivially decidable? Maybe I'm missing something obvious. Jan 5 at 15:55
• It is a classic trick: Either $0^n$ appears in $π$ for all $n$ and the language is trivial (all $ℕ$); Or there is a largest $n$ for which it appears and the language is finite ($\{0,…,n\}$) hence decidable. This does not give an algorithm, only proves that there exists one. Jan 5 at 15:57
• "Or there is a largest n for which it appears and the language is finite ({0,…,n}) hence decidable." This strikes me as a non-uniform algorithm. That is, finding out if such largest $n$ exists and what it is must be undecidable itself (at least for an arbitrary computable real). Jan 6 at 10:58
• @rus9384 This is not quite a non uniform algorithm but definitely a non explicit one. Namely, there exist an infinity of algorithms, "return True" and for each $N$, "return $n≤N$", amongst which one is correct. We simply do not known which one. Jan 7 at 13:12
• @JeanAbouSamra You're absolutely right, I suspected that the questions had already been asked but did not find it… Unfortunately, there is no satisfactory answer yet! (Satisfactory could mean "it is known to be an open question.") Jan 7 at 13:15