Line 40: Line 40:
  
 
Now, $L$ = $L0 U L1$
 
Now, $L$ = $L0 U L1$
 +
 
= re U not re
 
= re U not re
 +
 
= not re
 
= not re
  
 
$L' = (L0 U L1)'$
 
$L' = (L0 U L1)'$
 +
 
$=L0' ∩ L1'$
 
$=L0' ∩ L1'$
 +
 
=not re ∩ re
 
=not re ∩ re
 +
 
=not re
 
=not re

Revision as of 16:11, 10 December 2013

Define languages L0 and L1 as follows :

$L0 = \{< M, w, 0 > |$ $M$ halts on $w\} $

$L1 = \{< M, w, 1 > |$ $M$ does not halts on$ w\}$

Here $< M, w, i >$ is a triplet, whose first component. $M$ is an encoding of a Turing Machine, second component,$ w$, is a string, and third component, $i$, is a bit. Let $L = L0 ∪ L1$. Which of the following is true ?

(A) $L$ is recursively enumerable, but is not

(B) $L$ is recursively enumerable, but$ L'$ is not

(C) Both $L$ and $L'$ are recursive

(D) Neither $L$ nor $L'$ is recursively enumerable

Solution

Both $L$ and $L'$ are undecidable. Because halting problem can be solved with both $L$ and $L'$.

Halting problem can be stated as follows: A machine $M$ and a word $w$ are given. You have to tell, if $M$ halts on $w$.

So, to solve halting problem $<M,w>$ using $L$, just give $<M,w,0>$ and $<M,w,1>$ to two instances of $T$ which is the Turing machine for $L$. If $T$ accepts the triplet $<M,w,0>$, it means $M$ halts on $w$ => we have solved halting problem. If $T$ accepts the triplet $<M,w,1>$, it means $M$ doesn't halt on $w$ => we have solved halting problem. We know that either $<M,w,0>$ or $<M,w,1>$ is in $L$. So, if $L$ is recursively enumerable, $T$ is bound to stop on at least one of these inputs. Hence, using $L$ we can solve halting problem => $L$ is not recursively enumerable.

Similarly, we can also show that halting problem can be solved with $L'$.

Hence, neither $L$ nor $L'$ is recursively enumerable.

Alternate Solution

$L0$ is recursively enumerable. (Given $<M,w,0>$, we can just give $w$ to $M$. If $M$ halts on $w$, $<M,w,0>$ is element of $L0$.

$L1$ is not recursively enumerable. Because, halting problem can be solved with it. To decide if a turing machine $M$ accepts a word $w$, just give $<M,w,1>$ to the Turing machine for $L1$ and also give $w$ to $M$. Either $M$ accepts $w$, or the Turing machine for $L1$ accepts $<M,w,1>$. In either case we have solved halting problem. Hence, $L1$ is not recursively enumerable.

$L1$ can be reduced to $L0'$, and hence $L0'$ also is not recursively enumerable.

$L1'$ can be reduced to $L0$, and hence $L1'$ is recursively enumerable.

Now, $L$ = $L0 U L1$

= re U not re

= not re

$L' = (L0 U L1)'$

$=L0' ∩ L1'$

=not re ∩ re

=not re

Define languages L0 and L1 as follows :

$L0 = \{< M, w, 0 > |$ $M$ halts on $w\} $

$L1 = \{< M, w, 1 > |$ $M$ does not halts on$ w\}$

Here $< M, w, i >$ is a triplet, whose first component. $M$ is an encoding of a Turing Machine, second component,$ w$, is a string, and third component, $i$, is a bit. Let $L = L0 ∪ L1$. Which of the following is true ?

(A) $L$ is recursively enumerable, but is not

(B) $L$ is recursively enumerable, but$ L'$ is not

(C) Both $L$ and $L'$ are recursive

(D) Neither $L$ nor $L'$ is recursively enumerable

Solution[edit]

Both $L$ and $L'$ are undecidable. Because halting problem can be solved with both $L$ and $L'$.

Halting problem can be stated as follows: A machine $M$ and a word $w$ are given. You have to tell, if $M$ halts on $w$.

So, to solve halting problem $<M,w>$ using $L$, just give $<M,w,0>$ and $<M,w,1>$ to two instances of $T$ which is the Turing machine for $L$. If $T$ accepts the triplet $<M,w,0>$, it means $M$ halts on $w$ => we have solved halting problem. If $T$ accepts the triplet $<M,w,1>$, it means $M$ doesn't halt on $w$ => we have solved halting problem. We know that either $<M,w,0>$ or $<M,w,1>$ is in $L$. So, if $L$ is recursively enumerable, $T$ is bound to stop on at least one of these inputs. Hence, using $L$ we can solve halting problem => $L$ is not recursively enumerable.

Similarly, we can also show that halting problem can be solved with $L'$.

Hence, neither $L$ nor $L'$ is recursively enumerable.

Alternate Solution[edit]

$L0$ is recursively enumerable. (Given $<M,w,0>$, we can just give $w$ to $M$. If $M$ halts on $w$, $<M,w,0>$ is element of $L0$.

$L1$ is not recursively enumerable. Because, halting problem can be solved with it. To decide if a turing machine $M$ accepts a word $w$, just give $<M,w,1>$ to the Turing machine for $L1$ and also give $w$ to $M$. Either $M$ accepts $w$, or the Turing machine for $L1$ accepts $<M,w,1>$. In either case we have solved halting problem. Hence, $L1$ is not recursively enumerable.

$L1$ can be reduced to $L0'$, and hence $L0'$ also is not recursively enumerable.

$L1'$ can be reduced to $L0$, and hence $L1'$ is recursively enumerable.

Now, $L$ = $L0 U L1$

= re U not re

= not re

$L' = (L0 U L1)'$

$=L0' ∩ L1'$

=not re ∩ re

=not re