3
$\begingroup$

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?
$\endgroup$
7
  • $\begingroup$ How is $0^n \in \pi$ trivially decidable? Maybe I'm missing something obvious. $\endgroup$ Jan 5 at 15:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bruno
    Jan 5 at 15:57
  • $\begingroup$ "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). $\endgroup$
    – rus9384
    Jan 6 at 10:58
  • $\begingroup$ @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. $\endgroup$
    – Bruno
    Jan 7 at 13:12
  • $\begingroup$ @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.") $\endgroup$
    – Bruno
    Jan 7 at 13:15

0

Browse other questions tagged or ask your own question.