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$
$\endgroup$
3
-
$\begingroup$ You are having a problem formulating a proper question. Read the faq, and take a little time and effort. $\endgroup$– Dave ClarkeCommented May 27, 2013 at 20:07
-
$\begingroup$ Try writing the question in the body, not in the title. $\endgroup$– Dave ClarkeCommented May 27, 2013 at 21:04
-
1$\begingroup$ And making the title descriptive. $\endgroup$– Dave ClarkeCommented May 27, 2013 at 21:07
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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.)
$\begingroup$
$\endgroup$
6
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$– sdcvvcCommented May 27, 2013 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$– sdcvvcCommented May 27, 2013 at 22:36
-
1$\begingroup$ Thanks @sdcvvc I edited the answer to take in account your comment. $\endgroup$– weceCommented May 28, 2013 at 12:20
-
$\begingroup$ If $L$ has to be decidable, you don't answer the question. $\endgroup$– RaphaelCommented May 28, 2013 at 17:46
-
$\begingroup$ @Raphael if $L$ is undecidable $L'=L$ trivially answer the question doesn't it? $\endgroup$– weceCommented May 28, 2013 at 21:19