1
$\begingroup$

If $L$ is an infinite ($|L|=|\mathbb{N}| $) decidable language, prove that it contains:
a) An infinite subset that is not recognizable.
b) An infinite subset that is recognizable and not decidable.

For the (a) I considered all the subsets of $L$, i.e., $\mathbb{P}(L)$. Since $|\mathbb{P} (L)| = |\mathbb{R}|$, there exists $A \subset L$ that is not recognizable (for there are not enough Turing machines to recognize them all). If $A$ were finite, it would be decidable and hence recognizable, which would be a contradiction. Therefore $A$ is infinite and not recognizable.

For (b) I thought about $B=L\setminus A$. Then $B$ is recognizable because $A$ is not. But I'm not really sure.

$\endgroup$
1
  • 1
    $\begingroup$ If you’re not sure, try proving it. $\endgroup$ Oct 28, 2020 at 6:13

1 Answer 1

1
$\begingroup$

Let $K$ be the set of indices of Turing machines which halt on the empty input. Consider the following language:

$$X = \{ 0 w : |w| \in K \} \cup \{ 1 w : |w| \notin K \}. $$

You can check that neither $X$ nor its complement are recognizable.

Therefore your proof idea doesn't work. Here is a different idea. Let $w_1,w_2,w_3,\ldots$ be the words in $L$, enumerated according length and then lexicographically (so if $L = \Sigma^*$, the order would be $\epsilon,0,1,00,01,10,11,\ldots$). The language

$$ Y = \{ w_i : i \in K \} $$

is recognizable but not decidable.

$\endgroup$
2
  • $\begingroup$ But I don't understand how are you defining Y $\endgroup$
    – user719961
    Oct 28, 2020 at 23:17
  • $\begingroup$ Does it contain all the words whose indices correspond to a Turing machine which halts on the empty input? $\endgroup$
    – user719961
    Oct 28, 2020 at 23: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.