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) So $|\mathbb{P} (L)| = |\mathbb{R}|$ so that means that it exists $A \subset L$ that is not recognizable (for there are not enough Turing machines to recognize them all) If A were finite, then it would be decidable so it would be recognizable which would be a contradiction. Therefore A is infinite and not recognizable.

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

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

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.

  • $\begingroup$ But I don't understand how are you defining Y $\endgroup$
    – user719961
    Oct 28 '20 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 '20 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.