The Gateway to Computer Science Excellence
0 votes


in Theory of Computation by Active | 94 views
According to me answer should be None of these.

Question said that it can be arranged in a order now its countable set (of course) if they had said that it can be arranged in lexicographic order then we could have said it as Recursive, so now according to it if u see we will get Answer as NONE OF THESE

but its not the answer :/
I am also getting D. What is the explanation
It should be D. because say a TM that accepts all rational numbers. Now its a countable set but i cant say it as recursive can i ?

The proper interpretation should be that its a recursively enumerable language.

Correct me if i am wrong. Answer is C
$M$ is reducible to $L$, so $M$ can also be recursive. Isn't it ?
Yeah it can be recursive, there's a difference b/w can and will right ?

Because i will think by taking worst case wouldn't i brother ?
I thought the same as you didn't read your comment clearly.

I think the answer should be $D$, but by proper order can they mean lexographically ?
No, every proper order is not lexicographic, because say the alphabet consist of {0,1} then ? or any other order could have been used.
then it should be $D$
i saw your comment i just wanna see that wether you agree with my reason :p
yeah D

but I have small doubt In option C also...can you explain why it's not correct ??
$M$ is reducible to $L$, so $M$ can be recursive enumerable. So, $M\bigcap L$ is not recursive always.

Correct me if i'm wrong.
See we get that L is R.E.L and may or may not be Recursive though

Now if M <= L (Say L i assumed as Recursive)

then M will also be recursive then : M intersection L = Recursive intersection Recursive = Recursive

If I assume L as Recursively enumerable but not recusive and M is reducible to L them M can be recursive

So M intersection L will be Recusively enumerable not recursive

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
60,042 answers
94,725 users