Changing a complete undecidable turing machine language

Question

$L = \{\langle M\rangle\mid \text{M is a TM and }L(M) = \{101\}\}$ meaning M accepts only the string $101$. Which is neither co-recognizable / recognizable. Can be proven easily by $HALT \leq_m L (\text{ or } \bar{L})$ mapping reduction. Reasoning being its very to prove for all TM that none accepts 101 or none rejects 101. How do I tweak this to make this either recognizable or co-recognizable but not both?

My attempt:

$L = \{\langle M,w\rangle\mid \text{M is a TM and for some }L(M) = \{101\}\}$

$\bar{L} = \{\langle M,w\rangle\mid\text{M is a TM and for none }L(M) = \{101\}\}$

I'm trying to change it to it can accept 101 instead of it only accepts 101. And the complement is that it cant accepts 101. I'm stuck at the complament i don't think its proper and the wording of the language. I don't know if theres a easy way to change this language.

Answer 1

How about the following languages?

• $L_{101}=\{\langle M\rangle\, \mid 101 \in L(M)\}$, which is recognizable but not co-recognizable.
• $\overline{L_{101}}=\{\langle M\rangle\, \mid 101 \not\in L(M)\}$, which is co-recognizable but not recognizable.

Let $\text{HALT}_\epsilon:= \{ \langle M \rangle \mid M \text{ is a TM that halts on empty input.}\}$. $L_{101}$ and $HALT_\epsilon$ can be reduced to each other easily.

Another set of choices can be the following classic languages.

• $\text{ACCEPT}=\{\langle M, w\rangle\, \mid w\in\Sigma^*\text{ and } w\in L(M)\}$, which is recognizable but not co-recognizable.
• $\overline{\text{ACCEPT}}=\{\langle M, w\rangle\, \mid w\in\Sigma^*\text{ and } w\not\in L(M)\}$, which is co-recognizable but not recognizable.

Answer 2

Well, lets start with your $L$ first. Claim: $L$ is undecidable.#

Clear: $L$ is not empty (there exist TM that accept that input) and not trvial (there exist a input w on some $M$ where $w \notin L(M)$ by definition of $L$. Thus, $L$ ist not trival and no property of $M$, so by Rice'S Theorem $L$ is not decidable.

For your $L^C$ the argumentation is basically the same, it is also undecidable.

To make a language r.e (recursive enumerable), in your terms co-recognizable we need a aditional property:

1. Termination properties of your TM For the recursive languages, we need this also, because REC is a subclass of RE.

A language $L$ is r.e. iff. for each $w \in L$ there exists a TM M, such that M halts and accepts. For recursive language you need more, here the TM must even halt and decline the input if it is not part of the language.

A recursive language would be:

$L_{rec} = \{<M> |$ for each input $w$ M halts and accepts, if $w = 101$, otherwise M halts and declines. $\}$

EDIT: Language is not reursive (but r.e). If $L_{rec}$ would be recursive, it would be co-recognizable. Given a word $x = <U>w$ (coding of U and input word w for U). Chose $U$ as a TM that never halts and $w=101$.

Assume there exists a TM $M$ which could compute that $<U>w \notin L_{rec}$. That is if $U$ does not halt. So, $M$ has to know if $U$ halts and thus never halts (it always waits for U to stop). A contradiction.

I will let this answer stay here to clarify the pitfall between decidability and recognizability. Recognizablity is a weaker property of a language then decidability.