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. 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 (<math>TM</math> 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 :
$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. 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 (<math>TM</math> 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.
GATECSE