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...") |
Arjun Suresh (talk | contribs) |
||
| 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}$ | + | $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 | 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 = L0 ∪ L1$. Which of the following | + | |
| − | is true ? | + | 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 ''' | |
| + | ===Solution=== | ||
Both L and L' are undecidable. Because halting problem can be solved with both L and L'. | Both L and L' are undecidable. Because halting problem can be solved with both L and L'. | ||
| Line 22: | Line 26: | ||
Hence, neither L nor L' is recursively enumerable. | Hence, neither L nor L' is recursively enumerable. | ||
| + | |||
| + | ===Alternate Solution=== | ||
| + | |||
| + | 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 | ||
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
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