Is Deciding Decidability Decidable?

Question

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.

Answer 1

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.

Answer 2

As we have seen in the different answers, part of the answer is in formulating the right problem.

In 1985 Joost Engelfriet wrote "The non-computability of computability" (Bulletin of the EATCS number 26, june 1985, pages 36-39) as an answer to a question posed by a clever student. Unfortunately, the BEATCS was at that time paper-only and the article left no electronic traces.

The author assumes we have a (logical) formalism $\Psi$ with the usual boolean operators and variables. Its precise definition is not important. A formula $F(m,n)$ specifies a function $f:\Bbb N \to \Bbb N$ iff (for all $m,n\in \Bbb N$) $f(m)=n$ $\Leftrightarrow$ $F(\underline m,\underline n)$ is true, where $\underline m$ is the numeral representing the number $m$.

I quote:

Theorem 1. Let $\Phi$ be a formalism in which both a computable and a non-computable function $\Bbb N \to \Bbb N$ can be specified. Then there is no algorithm that for an arbitrary specifiable function $f$ (given by a formula that specifies it) decides whether $f$ is computable.

The fun part is in the following observation made in the paper:

Note that this theorem applies in particular to formalisms $\Phi$ in which all computable functions can be specified (a natural condition for such a formalism), because then also a non-computable function can be specified.

Answer 3

Yes. It's always decidable.

For any problem P, let Q be the problem of determining whether P is decidable or not. I claim that Q is decidable. Here's why. Tautologically, either P is decidable, or it isn't. So, one of the two programs is correct: (1) print "yup P is decidable" or (2) print "nope P is not decidable". It might be non-trivial to figure out which of those two programs is correct, one of them is correct, so a decider for Q surely exists. Therefore, the problem Q is decidable.

This is reminiscent of the following classic question: Is it decidable to tell whether Collatz's Conjecture is true? The answer is yes. This might look odd, as no one knows whether Collatz's Conjecture is true (that's a famous open problem). However, what we do know is that Collatz's Conjecture is either true or it's not. In the former case, the program print "yup it's true" is a decider. In the latter case, the program print "nope it's not true" is a decider. We don't know which one is a valid decider, but this is enough to prove that a valid decider exists. Therefore, the problem is decidable.