Arjun Suresh (talk | contribs) (→Solution) |
Arjun Suresh (talk | contribs) (→{{Template:Author|Arjun Suresh|{{arjunweb}} }}) |
||
| (11 intermediate revisions by the same user not shown) | |||
| Line 5: | Line 5: | ||
$L_1 = \{< 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 | + | Here $< M, w, i >$ is a triplet, whose first component $M$ is an encoding of a Turing |
| − | Machine, second component | + | 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 ? | Let $L = L_0 ∪ L_1$. Which of the following is true ? | ||
| Line 17: | Line 18: | ||
'''(D) Neither $L$ nor $L'$ is recursively enumerable ''' | '''(D) Neither $L$ nor $L'$ is recursively enumerable ''' | ||
| − | === | + | ==={{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 ( | + | 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. | Hence, using $L$ we can solve halting problem => $L$ is not recursively enumerable. | ||
| Line 29: | Line 30: | ||
Hence, neither $L$ nor $Lʼ$ is recursively enumerable. | 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$ 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_0'$ also is not recursively enumerable. | ||
| + | |||
$L_1'$ can be reduced to $L_0$, and hence $L_1'$ is recursively enumerable. | $L_1'$ can be reduced to $L_0$, and hence $L_1'$ is recursively enumerable. | ||
| − | + | Now, $L$ = $L_0 U L_1$ | |
| − | $L$ = $L_0 U L_1$ | ||
= <math>RE</math> U not <math>RE</math> | = <math>RE</math> U not <math>RE</math> | ||
| Line 53: | Line 55: | ||
$=$ not <math>RE</math> | $=$ not <math>RE</math> | ||
| + | --> | ||
{{Template:FBD}} | {{Template:FBD}} | ||
| Line 58: | Line 61: | ||
[[Category: GATE2003]] | [[Category: GATE2003]] | ||
| − | [[Category: Automata | + | [[Category: Automata questions from GATE]] |
| − | |||
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
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.
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
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 (<math>TM</math> 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.
$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_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>
$=$ not <math>RE</math>
GATECSE