1
$\begingroup$

For instance, consider L = {k : the binary expansion of sqrt(2) contains k consecutive 1s}. Obviously Rice Theorem would not work. I also tried the method of how it is to PCP undecidable but still no luck. How to prove that this is undecidable?

$\endgroup$
  • 1
    $\begingroup$ Why would this be undecidable? You can calculate the binary expansion $\endgroup$ – nir shahar Jun 5 at 20:55
  • $\begingroup$ Your language is decidable. $\endgroup$ – Yuval Filmus Jun 5 at 21:29
  • $\begingroup$ What do you mean by "the binary expansion of 2"? $\endgroup$ – D.W. Jun 5 at 21:34
  • 1
    $\begingroup$ @gauchopig It might come as a surprise to you, but the language $L=\{k\in\mathbb N : \text{the binary expansion of }\sqrt 2\text{ contains }k\text{ consecutive } 1\text{s}\}$ is decidable, even if we have NO idea how to construct an algorithm that can determine whether the binary expansion of $\sqrt 2$ contains $k$ consecutive $1$s or not given arbitrary $k$. $\endgroup$ – John L. Jun 6 at 0:17
  • 2
    $\begingroup$ Hint: one can decide this problem with a truly simple finite state automaton that does nothing resembling the calculation of the digits of $\sqrt{2}$. The problem has a major degeneracy that you can exploit. $\endgroup$ – Yonatan N Jun 6 at 0:33
3
$\begingroup$

It might come as a surprise to you, but the language $$L=\{k\in\mathbb N :\text{the binary expansion of} \sqrt2\text{ contains $k$ consecutive $1$s}\}$$ is decidable, even if we could not construct an algorithm that can demonstrate whether the binary expansion of $\sqrt2$ contains $k$ consecutive $1$s or not given arbitrary $k$.

As Yonatan N indicated, let us take a closer look at $L$. There are two disjoint cases.

  • $L$ is $\mathbb N$. Then $L$ is trivially decidable. For any given $k$, just return "Yes".
  • $L$ is not $\mathbb N$. Then there are some numbers in $\mathbb N$ that is not in $L$. Let $m$ be the minimum of such number. Then $L$ must be $\{1, 2, 3, \cdots, m-1\}$. Why?

    • Since $m>2$ is the minimum number that is not in $L$, $m-1$, which is a number smaller than $m$, must be in $L$. That is, $\text{bin}(\sqrt 2)$ contains $m-1$ consecutive $1$s. So it also contain $k$ consecutive $1$s for all $k\le m-1$.
    • Since $\text{bin}(\sqrt 2)$ does not contains $m$ consecutive $1$s, it does not contain $k$ consecutive $1$s for any $k\gt m$. That is, $k\not\in L$.

    Now we can construct an algorithm that decides $L$. For any given $k$, check whether $k\lt m$. If yes, return "Yes". Otherwise, return "No".

In either case, there exists an algorithm that decides $L$. Hence $L$ is decidable.


Most people, I believe, felt a bit disoriented the first time when this kind of proof/conclusion was encountered. Or at least myself.

The essential point is we do not have to identify/construct/bind to one algorithm that decides $L$. We do not have to understand fully what is $L$. All we need is there exists an algorithm that decides $L$, whatever $L$ turns out to be. This deviates from "the naive sense of decidability" that you might have even before you encountered the theory of computation/decidability/computability.

In particular, I do not know whether $L$ is $\mathbb N$ or not. Some people claimed to have proved that $L=\mathbb N$. I have not checked their proof, yet. Although it is certainly interesting to find whether $L=\mathbb N$, its result will not change the fact that $L$ is decidable.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.