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 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
GATECSE