# Determining the classification of languages

$L_0 = \{ \langle M, w, 0 \rangle \mid \text{$M$halts on$w$}\}$
$L_1 = \{ \langle M, w, 1 \rangle \mid \text{$M$does not halt on$w$}\}$

$L = L_0 \cup L_1$

I need to determine where in the hierarchy of languages (recursive, recursively enumerable, not recursively enumerable) $L$ and its complement $\overline L$ belong. I reasoned as follows

$L = \{ \langle M, w, x\rangle \mid \text{$M$halts on$w$when$x=0$,$M$doesn't halt on$w$when$x = 1$,$x \in \{0, 1\}$}\}$

$L$ is clearly not recursively enumerable as a Turing machine wouldn't be able accept in all cases. It can accept only in case the input refers to $L_0$, but can't in case the input refers to $L_1$.

$\overline L = \overline L_0 \cap \overline L_1 = \emptyset$
Thus $\overline L$ is recursive.

Is my reasoning ok? This is a question from a previous exam paper.

• You have a mistake in the computation of $\overline{L}$. – Yuval Filmus Oct 25 '12 at 14:40

Here are two hints

1. If $\bar L$ would be decidable (recursive), then so would be $L$, and you just argued that $L$ is not even recursively enumerable. Maybe you have a closer look on what $\bar L_0 \cap \bar L_1$ really is. For example $\bar L_0 = \{ \langle M, w, 0 \rangle \mid \text{$M$does not halts on$w$}\} \cup \{ \langle M, w, x \rangle \mid x\not=0\}$.

2. If you want to argue formally correct that a language is not recursively enumerable, or decidable, then try to use a reduction, for example the many one reduction. Reduce a a problem, whose status you know, to $L$ and you can say something about $L$.

• I am thinking out aloud here. L is representative of the question, does a Turing machine accept/reject(halt) or loop around infinitely(not-halt) on an input string? $\overline L = \overline L_0 \cap \overline L_1$ has to represent, does a Turing machine halt and not halt simultaneously on an input string? The answer is a clear no. Thus $\overline L$ has to be decidable/recursive. I realise that the conclusion is wrong(If $\overline L$ would be decidable (recursive), then so would be L, and you just argued that L is not even recursively enumerable), but I can't seem to see the flaw. – Abhijith Madhav Oct 26 '12 at 2:17
• @AbhijithMadhav: I extended hint 1 slightly – A.Schulz Oct 26 '12 at 6:53
• Is your edit correct? Did you mean to say, $\bar L_0 = \{ \langle M, w, 0 \rangle \mid \text{$M$does NOT halt on$w$}\} \cup \{ \langle M, w, x \rangle \mid x\not=0\}$ – Abhijith Madhav Oct 26 '12 at 10:12
• @AbhijithMadhav yes you were correct. That was a typo. – A.Schulz Oct 26 '12 at 12:03
• $\bar L_0 \cap \bar L_1 = \{ \langle M, w, 0 \rangle \mid \text {$M$does not halt on$w$}\} \cup \{ \langle M, w, 1 \rangle \mid \text {$M$halts on$w$}\}$. Similar to the argument for $L$, $\bar L$ is also not recursively enumerable. I have assumed that the third element of the triplet of each language belongs to {0, 1}. The result won't matter otherwise. Initially, I think I got $\bar L$ wrong as a result of trying to verbalize everything at once. Breaking down things helped. Let me know if I have missed anything this time. – Abhijith Madhav Oct 26 '12 at 12:47

You can recognize (but not decide) $$L_1$$ (essentially checking it ends "0", if so simulating $$M$$ on $$x$$ by a universal Turing machine $$U$$, otherwise reject).

$$L_2$$ is essentially the complement of the language of $$U$$, which is not recognizable.

$$L$$ is not recognizable. If it was, say by a Turing machine $$R$$, you could run $$R$$ in parallel over $$\langle M, w, 0 \rangle$$ and $$\langle M, w, 1 \rangle$$. The one that accepts tells you if $$M$$ accepts $$w$$, which is impossible to do in general.