retagged by
820 views
5 votes
5 votes
Let $A=\{\langle M\rangle \mid M$ is turing machine that halts on all inputs and $L(M)=L'$ for some undecidable language $L'\}$. Then $A$ is ____

a. Regular language
b. Recursive language but not regular
c. Recursively enumerable language but not recursive language
d. Non-recursively enumerable language
retagged by

1 Answer

Best answer
8 votes
8 votes
$M$ is a Turing machine that halts on all inputs implies L(M) is recursive.

Now, L(M) = L' for some undecidable language L'.

So, this means L(M) is an undecidable language.  But L(M) must be decidable as $M$ is halting on all inputs. So, there cannot be any such $M$ making $A = \emptyset$ which is a regular language.
selected by

Related questions

0 votes
0 votes
0 answers
1
sripo asked Jan 5, 2019
538 views
As per the given solution,B should be the correct answer right why is D given as the correct answer as the machine accepts atleast one b.
0 votes
0 votes
1 answer
2
1 votes
1 votes
1 answer
3
0 votes
0 votes
0 answers
4