2
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ Note you can use \langle and \rangle instead of < and >, respectively, and which are much better to read. Also, the | in set comprehension is best typeset by \mid. $\endgroup$ – dkaeae Jun 6 at 7:11
  • $\begingroup$ Deleting my answer since I completely misread the question... sigh $\endgroup$ – dkaeae Jun 6 at 8:07
0
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Yeah this is what I wanted but wondering what this would be in words. Would $L_{101} = \{\langle M \rangle | \text {M is TM and M accepts some string 101}\}$ and $\bar{L_{101}} = \{\langle M \rangle | \text { M is a TM and M accepts all strings but 101 }\}$ be this in words? $\endgroup$ – aki Jun 6 at 16:48
  • $\begingroup$ In plain words, $L_{101}=\{\langle M\rangle\, \mid M\text{ is a TM that accepts 101}\}$ and $\overline{L_{101}}=\{\langle M\rangle\, \mid M\text{ is a TM that does not accept 101 }\}$. You are more careful in that I should have specified that $M$ is a TM. $\endgroup$ – Apass.Jack Jun 6 at 17:08
  • $\begingroup$ Is this well defined? I'm confused whether like for $L_{101}$ does it accept only $101$ and nothing else or can it accept all else. ? And for $\bar{L_{101}}$ it rejects 101 but can accept all else. $\endgroup$ – aki Jun 6 at 17:17
  • $\begingroup$ In plain words, a string $s$ is in $L_{101}$ if and only if there is a Turing machine $M$ that accepts 101 and $s$ is $M$ encoded according to a predefined way that is assumed to be understood by all. All requirement of $M$ is that as a Turing machine, $M$ accepts 101. It may or may not accept the empty word. It may or may not accept 0. It may or may not accept 1. It may or may not accept 0111001011. $\quad$. $\endgroup$ – Apass.Jack Jun 6 at 17:35
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am afraid that $\{\langle M\rangle \mid \text{ on input 101 }M\text{ halts and accepts; on other input }M\text{ halts and declines. }\}$ is not recognizable. It is not co-recognizable, either. $\endgroup$ – Apass.Jack Jun 6 at 14:59
  • $\begingroup$ @Apass.Jack Ah I see. I mixed up recognizablity and decidability, my bad. But can you give my an argument why $L_{rec}$ is not (co-) recognizable and thus not recursive? Because that would mean that $L_{rec}$ is not recursive. $\endgroup$ – Panzerkroete Jun 7 at 12:07

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.