# How to decide whether a language is decidable when not involving turing machines?

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?

• Why would this be undecidable? You can calculate the binary expansion – nir shahar Jun 5 at 20:55
• Your language is decidable. – Yuval Filmus Jun 5 at 21:29
• What do you mean by "the binary expansion of 2"? – D.W. Jun 5 at 21:34
• @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$. – John L. Jun 6 at 0:17
• 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. – Yonatan N Jun 6 at 0:33

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 1s}\}$$ 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.