[Solved]: Is Deciding Decidability Decidable?

Problem Detail: 

I am wondering if deciding the decidability of problem is a decidable problem. I am guessing not, but after initial searches I cannot find any literature on this problem.

Asked By : sync

Answered By : Rick Decker

Major edit of my original:

A naive reading of your question seems to be, let $P$ be the problem

$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 M\rangle$ 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 M\rangle\mid 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