({{Template:Author|Arjun Suresh|{{arjunweb}} }})
 
(44 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
Define languages L0 and L1 as follows :  
 
Define languages L0 and L1 as follows :  
  
$L0 = \{< M, w, 0 > | M$ halts on $w\} $
+
$L_0 = \{< M, w, 0 > |$ $M$ halts on $w\} $
  
$L1 = \{< M, w, 1 > | M$ does not halts on$ w\}$  
+
$L_1 = \{< 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  
+
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.  
+
Machine, second component $ w$ is a string, and third component $i$ is a bit.  
  
Let $L = L0 L1$. Which of the following is true ?  
+
Let $L = L_0 L_1$. Which of the following is true ?  
 
   
 
   
 
(A) $L$ is recursively enumerable, but is not  
 
(A) $L$ is recursively enumerable, but is not  
(B) $L$ is recursively enumerable, but$ L'$ is not  
+
 
 +
(B) $L$ is recursively enumerable, but $ L'$ is not  
 +
 
 
(C) Both $L$ and $L'$ are recursive   
 
(C) Both $L$ and $L'$ are recursive   
 +
 
'''(D) Neither $L$ nor $L'$ is recursively enumerable '''
 
'''(D) Neither $L$ nor $L'$ is recursively enumerable '''
  
===Solution===
+
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
  
Both L and L' are undecidable. Because halting problem can be solved with both L and L'.  
+
Both $L$ and $Lʼ$ are undecidable and not even semi-decidable (not recursively-enumerable). 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.  
+
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 ($TM$ for a recursively enumerable language stops and accepts, when provided with a word in its language). 
  
So, to solve halting problem using L, just put a 0 and 1 at the end and give it to L. If L accepts the triplet <M,w,0>, it means M halts on w => we have solved halting problem. If L accepts the triplet <M,w,1>, it means M doesn't halt on w => we have solved halting problem. We know either <M,w,0> or <M,w,1> is in L. So, if L is recursively enumerable, it's bound to stop on at least one of the input. Hence, using L we can solve halting problem => L is not recursively enumerable.
+
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ʼ$.  
  
Similarly, we can also show that halting problem can be solved with L'.  
+
Hence, neither $L$ nor $Lʼ$ is recursively enumerable.
 +
<!--
 +
===Alternate Solution===
  
Hence, neither L nor L' is recursively enumerable.
+
$L_0$ is recursively enumerable. (Given $<M,w,0>$, we can just give $w$ to $M$. If $M$ halts on $w$, $<M,w,0>$ is an element of $L_0$.)
  
===Alternate Solution===
+
$L_1$ 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 $L_1$ and also give $w$ to $M$. Either $M$ accepts $w$, or the Turing machine for $L_1$ accepts $<M,w,1>$. In either case we have solved halting problem. Hence, $L_1$ is not recursively enumerable.
 +
 
 +
$L_1$ can be reduced to $L_0'$, and hence $L_0'$ also is not recursively enumerable.
 +
 
 +
$L_1'$ can be reduced to $L_0$, and hence $L_1'$ is recursively enumerable.
 +
 
 +
Now, $L$ = $L_0 U L_1$
 +
 
 +
= <math>RE</math> U not <math>RE</math>
 +
 
 +
= not <math>RE</math>
 +
 
 +
$Lʼ = (L_0 \cup L_1)'$
 +
 
 +
$= L_0' ∩ L_1'$
  
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.
+
$=$ not <math>RE</math> $∩$ <math>RE</math>
  
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 <M,w,1> is accepted by the Turing machine for L1. In either case we have solved halting problem. Hence, L1 is not recursively enumerable.
+
$=$ not <math>RE</math>
  
L1 can be reduced to L0', and hence L0' also is not recursively enumerable.
+
-->
 +
{{Template:FBD}}
  
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)'
+
[[Category: GATE2003]]
=L0' ∩ L1'
+
[[Category: Automata  questions from GATE]]
=not re ∩ re
 
=not re
 

Latest revision as of 19:40, 10 September 2014

Define languages L0 and L1 as follows :

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

$L_1 = \{< 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 = L_0 ∪ L_1$. 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 by Arjun Suresh

Both $L$ and $Lʼ$ are undecidable and not even semi-decidable (not recursively-enumerable). 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 ($TM$ for a recursively enumerable language stops and accepts, when provided with a word in its language).

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.



blog comments powered by Disqus

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 using L, just put a 0 and 1 at the end and give it to L. If L accepts the triplet <M,w,0>, it means M halts on w => we have solved halting problem. If L accepts the triplet <M,w,1>, it means M doesn't halt on w => we have solved halting problem. We know either <M,w,0> or <M,w,1> is in L. So, if L is recursively enumerable, it's bound to stop on at least one of the input. 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 <M,w,1> is accepted by the Turing machine for L1. 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