I'm having a problem with proving the following statement:

For every infinite language $L$, does there exists an infinite language $L' \subseteq L$ such that $L'$ is not decidable?

  • $\begingroup$ You are having a problem formulating a proper question. Read the faq, and take a little time and effort. $\endgroup$ – Dave Clarke May 27 '13 at 20:07
  • $\begingroup$ Try writing the question in the body, not in the title. $\endgroup$ – Dave Clarke May 27 '13 at 21:04
  • 1
    $\begingroup$ And making the title descriptive. $\endgroup$ – Dave Clarke May 27 '13 at 21:07

The set $\{L' : L' \subseteq L\}$ is an uncountable set of languages, and since there is only countably many decidable languages, it has to contain an undecidable language. (You can get a concrete $L'$ by a diagonal argument.)


Since $L'$ is totally free, you can always define it directly as something undecidable.

For example ordering the words of $L$ with lexicographic order and ordering turing machines (in any order you like) you can define $L'$ as: $L'=\{w_i|w_i\text{ ith word in $L$ and $M_i$ stop on }\epsilon\}$.

If $L'$ is decidable then termination with empty tape of Turing machine is decidable. Contradiction.

Hence $L'\subseteq L$ and $L'$ is undecidable.

Note I assumed $L$ decidable. If $L$ is already undecidable then take $L'=L$.

  • 1
    $\begingroup$ I'm afraid this will not work in general - only if $L$ is decidable. $L$ could be a weird undecidable language such that if you filter it to get $L'$, it will become decidable. Here's a sketch of an example. Assume that naturals include 0 (we start indexing from 0), and that the ordering of TMs is such that every $M_{2i}$ stops on $\varepsilon$, which can be done. Suppose that indices of halting machines are 0,1,2,4,6,8,9,10,11,12,13..., and assume $L$ contains $a^0,a^2,a^4,a^5,a^6,a^7,a^8,a^9,a^{10},a^{12},a^{14},a^{16},a^{18},a^{20}...$. $\endgroup$ – sdcvvc May 27 '13 at 22:35
  • $\begingroup$ Then 0-th element of $L'$ is $a^0$, 1-st element is $a^2$, 2-nd is $a^4$, 3-rd is $a^6$, 4-th is $a^8$ etc. This pattern can be continued. So $L'$ is $a^{2n}$ which is decidable. $\endgroup$ – sdcvvc May 27 '13 at 22:36
  • 1
    $\begingroup$ Thanks @sdcvvc I edited the answer to take in account your comment. $\endgroup$ – wece May 28 '13 at 12:20
  • $\begingroup$ If $L$ has to be decidable, you don't answer the question. $\endgroup$ – Raphael May 28 '13 at 17:46
  • $\begingroup$ @Raphael if $L$ is undecidable $L'=L$ trivially answer the question doesn't it? $\endgroup$ – wece May 28 '13 at 21:19

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.