Asked By : sync
Answered By : Rick Decker
$P=$ Given a language, $L$, is it decidable?
Then you ask
Is $P$ decidable?
As D.W. and David have noted, the answer is, “yes it is”, though we don’t know which of the two trivial deciders is the right one. In order to frame your problem so that it’s not quite so trivial, I’d suggest this. First, let’s restrict things slightly by considering only those languages $L(M)$ which are the languages accepted by some TM $M$. The reason for doing this is that if a language is not accepted by any TM, then it’s not r.e. (recognizable) and so can’t be recursive (decidable). Then we can recast $P$ as
$P’=$ Given a description, $langle Mrangle$ of a TM, $M$ is $L(M)$ decidable?
Now $P’$ is a language of TM descriptions, rather than a language of languages as $P$ seemed to be (under a generous interpretation), and it’s now perfectly reasonable to ask whether the language $P’$ is decidable. Under this reading, the language $$ {langle Mranglemid M text{ is a TM and $L(M)$ is decidable}} $$ consisting of TM descriptions is not decidable. This is an easy consequence of Rice’s Theorem. So now we have two answers: my “no” and D.W.’s “yes”, depending on the interpretation.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42198 Ask a Question Download Related Notes/Documents