Arjun Suresh (talk | contribs) |
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\} $ | + | $L0 = \{< M, w, 0 > |$ $M$ halts on $w\} $ |
| − | $L1 = \{< M, w, 1 > | M$ does not 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 | ||
| Line 19: | Line 19: | ||
===Solution=== | ===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'$. |
| − | 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 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. Hence, using L we can solve halting problem => L is not recursively enumerable. | + | 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. 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'. | + | Similarly, we can also show that halting problem can be solved with $L'$. |
| − | Hence, neither L nor L' is recursively enumerable. | + | Hence, neither $L$ nor $L'$ is recursively enumerable. |
===Alternate Solution=== | ===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. | + | $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> | + | $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 the Turing machine for $L1$ accepts $<M,w,1>$. 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 $L0'$ also is not recursively enumerable. |
| − | L1' can be reduced to L0, and hence L1' is recursively enumerable. | + | $L1'$ can be reduced to $L0$, and hence $L1'$ is recursively enumerable. |
| − | Now, L = L0 U L1 | + | Now, $L$ = $L0 U L1$ |
= re U not re | = re U not re | ||
= not re | = not re | ||
| − | L' = (L0 U L1)' | + | $L' = (L0 U L1)'$ |
| − | =L0' ∩ L1' | + | $=L0' ∩ L1'$ |
=not re ∩ re | =not re ∩ re | ||
=not 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 $<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. 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 the Turing machine for $L1$ accepts $<M,w,1>$. 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 <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 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. 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