1
$\begingroup$

Suppose there is a language $L$ that is not Turing-recognizable. Now suppose, for every word in $L$, you would concatenate a "0" as prefix, resulting in $L' = \{0w | w \in L\}$. Does this mean that $L'$ is also not Turing-recognizable?

I would argue that $L'$ is also not Turing-recognizable:

No Turing machine recognizes $L$. So there exists no TM that recognizes all the words in $L$. That means that all the words that can not be recognized by a TM that are in L, also can not be recognized even with a "0" added before them. Because after the TM's head reads the "0", we assume that the head will read what comes after, which is a word that is not Turing-recognizable. One could argue that the head doesn't need to read the word and just go to "accept" after reading the 0, but then I can also build a TM that would just go to "accept" straight away before reading this word at all, meaning that the word was not Turing-recognizable which contradicts the initial statement.

In other words, after reading the "0", the TM will have to come across the not Turing-recognizable word, which it can't recognize. Therefore $L'$ is also not Turing-recognizable.

To generalize, I think if a not Turing-recognizable language is a subset of another language, then that language is also not Turing-recognizable.

However, I feel my explanation is shaky and I'm not convinced I am correct. Can anyone verify my claim, and either prove me wrong or give tips for a better proof?

$\endgroup$
  • $\begingroup$ The language of all words is the superset of any language. $\endgroup$ – Yuval Filmus Jun 18 '17 at 22:43
1
$\begingroup$

If $L'$ were Turing-recognizable then there would be a TM $M$ which would enumerate every string in $L'$. In particular, we could construct a TM that would print on the tape every string in $L'$. Then we could easily modify this machine to enumerate the language $L$. Just do not print the first symbol on the tape (skip the initial $0$). Thus we construct a machine which enumerates $L$. But $L$ is not Turing-recognizable (not r.e.) by assumption. A contradiction.

$L'$ in your example may be expressed as a concatenation of languages $\{0\}$ and $L$, that is, $L' = \{0\}L$. However, we cannot generalize this result to arbitrary languages. For example, $\{0,1\}^*L = \{0,1\}^*$ is r.e. even if $L$ is not r.e. language on $0$ and $1$ containing empty string.

As for your claim "a not Turing-recognizable language is a subset of another language, then that language is also not Turing-recognizable", it is false too, since a not Turing-recognizable language $L$ on $0$ and $1$ is a subset of $\{0,1\}^*$ which is definitely r.e., even decidable.

$\endgroup$
  • $\begingroup$ Alright I see. So in this particular case, {0}L is indeed also not r.e., but in general this does not have to be the case. $\endgroup$ – Automaton Jun 18 '17 at 18:28
0
$\begingroup$

We know that if $L_1 \leq_{\mathrm m} L_2$ and $L_2$ is recognisable, then so $L_1$.

We have that $L \leq_{\mathrm m} L'$ by the simple mapping reduction

$f(w) = 0w$

It is easy to see that $w \in L$ iff $f(w) \in L'$ and $f$ is trivially computable.

Since $L_1$ is not recognisable, we know that $L_2$ cannot be recognisable.

Students have lots of favourite "theorems" about how language inclusion somehow preserves decidability or recognizability (or lack thereof), and none of them are true.

The student favourite

If $L_1$ is unrecognisable and $L_1 \subseteq L_2$, then $L_2$ is also unrecognisable

falls because every language $L$ is a subset of the total language $\Sigma^*$ which is trivially decidable.

$\endgroup$

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.