Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) (→{{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 : | ||
| − | $ | + | $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 | + | 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 = | + | 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 ''' | ||
| − | === | + | ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}=== |
| − | Both L and | + | 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). | ||
| − | + | 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=== | ||
| − | + | $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> | |
| − | + | $=$ not <math>RE</math> | |
| − | + | --> | |
| + | {{Template:FBD}} | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | + | [[Category: GATE2003]] | |
| − | + | [[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 :
$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
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.
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
GATECSE