[Solved]: Determining the classification of languages

Problem Detail: 

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

Asked By : Abhijith Madhav

Answered By : A.Schulz

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6309

3.2K people like this

 Download Related Notes/Documents