Difference between revisions of "GATE2003 q54"

(Created page with "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 compon...")
 
(→‎{{Template:Author|Arjun Suresh|{{arjunweb}} }})
 
(45 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} $
+
 
−
$L1 = {< M, w, 1 > | M does not halts on w}$  
+
$L_0 = \{< M, w, 0 > |$ $M$ 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.  
+
$L_1 = \{< M, w, 1 > |$ $M$ does not halts on $w\}$  
−
Let $L = L0 ∪ L1$. Which of the following  
+
 
−
is true ?  
+
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 '''
 +
 
 +
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
 +
 
 +
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$.
 
   
 
   
−
1) $L$ is recursively enumerable, but is not
+
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). 
−
2) $L$ is recursively enumerable, but$ L'$ is not  
+
 
−
3) Both $L$ and $L'$ are recursive 
+
Hence, using $L$ we can solve halting problem  => $L$ is not recursively enumerable.
−
4) Neither $L$ nor $L'$ is 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===
 +
 
 +
$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$.)
 +
 
 +
$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'$
  
 +
$=$ not <math>RE</math> $∩$ <math>RE</math>
  
−
Both L and L' are undecidable. Because halting problem can be solved with both L and L'.
+
$=$ not <math>RE</math>
  
−
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.
+
-->
 +
{{Template:FBD}}
  
−
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.
+
[[Category: GATE2003]]
 +
[[Category: Automata  questions from GATE]]

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
Retrieved from "https://gatecse.in/w/index.php?title=GATE2003_q54&oldid=4238"

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 ?

1) $L$ is recursively enumerable, but is not 2) $L$ is recursively enumerable, but$ L'$ is not 3) Both $L$ and $L'$ are recursive 4) Neither $L$ nor $L'$ is recursively enumerable


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.