Arjun Suresh (talk | contribs) (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...") |
(No difference)
|
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.
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.
GATECSE