13
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ Yo, dawg, I heard you like decidability so... $\endgroup$ – David Richerby May 6 '15 at 9:27
  • $\begingroup$ Your question isn't answerable in its current form, as shown by the two answers that basically say, "Trivially, no" and "Trivially, yes" (with a bonus comment saying "no" to the "no"). You've asked if a problem is decidable but you haven't defined what that problem is. In particular, what is the input? If you want to design a Turing machine $M$ that will tell you whether a problem is decidable, you have to give that problem as an input to $M$. But how do you do that? $\endgroup$ – David Richerby May 6 '15 at 9:29
  • 3
    $\begingroup$ Given the current answers, there's the question "Is Deciding Deciding Decidability Decidable Decidable?", but I'm not going to ask it :-) $\endgroup$ – Mark Hurd May 8 '15 at 5:27
10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thank you! Understanding, at least shallowly, both answers gave me the information I was looking for, which is approximately: "Can we create a machine that can decide what it can and can't decide in general?" (Not good phrasing, I know, but I can't think of better phrasing.) Very helpful, especially that you acknowledge both interpretations. $\endgroup$ – sync May 6 '15 at 23:03
  • $\begingroup$ I thought showing that for every decidable problem there is a certificate (algorithm with a proof) and for every undecidable problem there also is a certificate (reduction from undecidable problem) is sufficient. $\endgroup$ – rus9384 Oct 2 '17 at 7:30
9
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think Ricky Decker's interpretation of the question is superior. Given some encoding of a problem, decide whether the problem is decidable. $\endgroup$ – Yuval Filmus May 6 '15 at 5:06
  • 1
    $\begingroup$ @YuvalFilmus, OK, that's reasonable. Do you have a finite encoding for problems (i.e., languages) that you think is reasonable, and doesn't make the problem trivial? The natural finite encoding for a language is as a Turing machine that recognizes that language, but that makes the problem trivial, as your comment on Ricky Decker's answer illustrates. So we'd need some other reasonable encoding, that doesn't suffer from this kind of problem. Do you have any suggestions for that? $\endgroup$ – D.W. May 6 '15 at 5:13
  • $\begingroup$ You can use first-order logic in some appropriate language. Or the input could be a machine in 0' (for example), i.e. a Turing machine with access to a halting oracle. $\endgroup$ – Yuval Filmus May 6 '15 at 5:24
  • $\begingroup$ By Rice's theorem, we know even deciding R in the RE universe is undecidable. Isn't that sufficient? (Not all TMs are deciders.) $\endgroup$ – Raphael May 6 '15 at 6:54
  • $\begingroup$ Thank you! While, not the interpretation I intended, this helped me see why the question I asked might not be sufficiently well stated to reflect my intentions. $\endgroup$ – sync May 6 '15 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.