GATE2003 q54 - Revision history

Arjun Suresh: /* {{Template:Author|Arjun Suresh|{{arjunweb}} }} */

2014-09-10T19:40:48Z

‎{{Template:Author|Arjun Suresh|{{arjunweb}} }}

Arjun Suresh at 10:56, 28 July 2014

2014-07-28T10:56:18Z

Arjun Suresh at 11:22, 15 July 2014

2014-07-15T11:22:16Z

Arjun Suresh at 09:44, 7 July 2014

2014-07-07T09:44:02Z

Arjun Suresh at 07:06, 15 April 2014

2014-04-15T07:06:29Z

Arjun Suresh at 14:03, 14 April 2014

2014-04-14T14:03:28Z

Arjun Suresh at 17:10, 22 February 2014

2014-02-22T17:10:12Z

Arjun Suresh at 11:19, 19 February 2014

2014-02-19T11:19:32Z

Arjun Suresh: /* Alternate Solution */

2014-02-18T21:18:29Z

‎Alternate Solution

Arjun Suresh: /* Alternate Solution */

2013-12-15T21:54:03Z

‎Alternate Solution

@@ Line 20: / Line 20: @@
 ==={{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$.
-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 (<math>TM</math> for a recursively enumerable language stops and accepts, when provided with a word in its language).
+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.

@@ Line 5: / Line 5: @@
 $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 = L_0 ∪ L_1$. Which of the following is true ?

← Older revision		Revision as of 11:22, 15 July 2014
Line 61:		Line 61:

	[[Category: GATE2003]]		[[Category: GATE2003]]
−	[[Category: Automata questions]]	+	[[Category: Automata questions from GATE]]

← Older revision		Revision as of 09:44, 7 July 2014
Line 61:		Line 61:

	[[Category: GATE2003]]		[[Category: GATE2003]]
−	~~[[Category: Automata Theory]]~~
	[[Category: Automata questions]]		[[Category: Automata questions]]

@@ Line 62: / Line 62: @@
 [[Category: GATE2003]]
 [[Category: Automata Theory]]
-[[Category: Previous year GATE questions]]
+[[Category: Automata  questions]]

@@ Line 18: / Line 18: @@
 '''(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ʼ$.

@@ Line 29: / Line 29: @@
 Hence, neither $L$ nor $Lʼ$ is recursively enumerable.
+<!--
 ===Alternate Solution===
@@ Line 54: / Line 54: @@
 $=$ not <math>RE</math>
+-->
 {{Template:FBD}}

@@ Line 32: / Line 32: @@
 ===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 element of $L_0$.)
+$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.

← Older revision		Revision as of 21:54, 15 December 2013
Line 53:		Line 53:

	$=$ not <math>RE</math>		$=$ not <math>RE</math>
		+

	{{Template:FBD}}		{{Template:FBD}}