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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ You have a mistake in the computation of $\overline{L}$. $\endgroup$ Commented Oct 25, 2012 at 14:40

2 Answers 2

Reset to default
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$.

Improve this answer
$\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$ Commented Oct 26, 2012 at 2:17
  • 1
    $\begingroup$ @AbhijithMadhav: I extended hint 1 slightly $\endgroup$ Commented 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$ Commented Oct 26, 2012 at 10:12
  • $\begingroup$ @AbhijithMadhav yes you were correct. That was a typo. $\endgroup$ Commented 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$ Commented 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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.