1
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Abhijith Madhav Oct 26 '12 at 2:17
  • 1
    $\begingroup$ @AbhijithMadhav: I extended hint 1 slightly $\endgroup$ – A.Schulz Oct 26 '12 at 6:53
  • $\begingroup$ 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\} $ $\endgroup$ – Abhijith Madhav Oct 26 '12 at 10:12
  • $\begingroup$ @AbhijithMadhav yes you were correct. That was a typo. $\endgroup$ – A.Schulz Oct 26 '12 at 12:03
  • $\begingroup$ $\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. $\endgroup$ – Abhijith Madhav Oct 26 '12 at 12:47

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.