Given an infinite decidable language $L$, then if $S \subset L$ such that $L \setminus S$ is finite, then $S$ must be decidable. This is true since given a decider of $L$ we contruct a decider for $S$:

Simulate the decider of $L$ on the input, if it accepts, go over $L \setminus S$ and check if it is there, if it is, reject. If it isn't accept. If the decider of $L$ rejects - reject.

Another point is if $S \subset L$ is finite then $S$ also must be decidable, this is immediate that every finite language is decidable.

Now we have the last case where $S$ is infinite and $L \setminus S$ is infinite. We know that there must be some subsets $S$ corresponding to this case that are undecidable. This is since there are $\aleph$ such $S$ but only $\aleph_0$ deciders. Denote $D(L) = \{ S \subset L : |S|= |L \setminus S|=\infty \wedge S \text{ is decidable} \}$

Is it true that for all infinite decidable languages $L$ we have $D(L) \neq \phi$?

If this is true then as a conclusion we will have for all infinite decidable languages $L$ a sequence of decidable languages $L_n$ such that $L_0=L$ and $L_{n+1} \subset L_n$ and $|L_n \setminus L_{n+1}| = \infty$

We will also have a limit-set $L_\infty = \{ e \in L : \forall n \in \mathbb{N} \text{ } e \in L_n \}$ and can dicuss if it is empty/finite/infinite and decicable or not.

This seems like a nice way to study decidable languages, and curious to know if this direction is indeed interesting and whether there are articles published regarding these questions

Thanks for any help


If $L$ has a finite alphabet, then $L$ is recursively enumerable.

Then, from such an enumeration $w_0,w_1,w_2,...$ of the words of $L$ you can take $S=\{w_0,w_2,w_4,...\}$, which will also be decidable. To check if a word $w$ is in $S$ check if it is in $L$. If it is then use the enumeration of $L$ to check if its position is even or not.


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.