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$
1
  • 2
    $\begingroup$ You have a mistake in the computation of $\overline{L}$. $\endgroup$ Oct 25, 2012 at 14:40

2 Answers 2

5
$\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$
8
  • $\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$ Oct 26, 2012 at 2:17
  • 1
    $\begingroup$ @AbhijithMadhav: I extended hint 1 slightly $\endgroup$
    – A.Schulz
    Oct 26, 2012 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$ Oct 26, 2012 at 10:12
  • $\begingroup$ @AbhijithMadhav yes you were correct. That was a typo. $\endgroup$
    – A.Schulz
    Oct 26, 2012 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$ Oct 26, 2012 at 12:47
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.