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.