11
$\begingroup$

Im sorry if this question has some trivial answer which I am missing. Whenever I study some problem which has been proven undecidable, I observe that the proof relies on a reduction to another problem which has been proven to be undecidable. I understand that it creates some kind of an order on the degree of difficulty of a problem. But my question is - has it been proven that all problems which are undecidable can be reduced to another problem which is undecidable. Is it not possible that there exists a undecidable problem which can proved to have no reduction to any other undecidable problem (Hence to prove the undecidability of such a problem, one cannot use reductions). If we use reductions to create an order on the degree of computability then this problem cannot be assigned such a degree.

$\endgroup$
  • $\begingroup$ Short answer: far from trivial! Look at Arithmetical hierarchy. $\endgroup$ – Hendrik Jan Aug 1 '13 at 7:25
  • $\begingroup$ What about this: If $L$ is an undecidable language and $x \min L$ be the smallest element in $L$. Then $L' = L \setminus \{x\}$ is reducible (and vice versa) to $L$. If you in addition add an element to $L'$ (say the smallest element not in $L$), then you have a 1-1-reduction. $\endgroup$ – Pål GD Aug 1 '13 at 10:39
9
$\begingroup$

As Hendrik Jan mentioned, there are in fact different degrees of undecidability. For example, the problem of deciding whether a Turing machine stops on all inputs is harder than the halting problem, in the following sense: even given an oracle to the halting problem, we can't decide whether a given Turing machine stops on all inputs.

One important technique used to show relations like these is diagonalization. Using diagonalization, given a problem $P$ we can always find a harder problem, namely the halting problem for Turing machines with an access to a $P$ oracle. The new problem $P'$ is harder in the following sense: a Turing machine with an oracle access to $P$ cannot solve $P'$. In that sense there is no "hardest" problem.

$\endgroup$
  • $\begingroup$ Thankyou for the answer. I understood what your are saying. We can construct "harder" problems from "hard" ones. But do these schemes of construction of harder problems from hard ones (for example say diagonalization is one such scheme as you mentioned) necessarily cover "all" existent undecidable problems (i.e. are they guaranteed to construct the set of all undecidable problems). Is it not possible that some maybe left out in the construction and they cannot be constructed from other undecidables? $\endgroup$ – swarnim_narayan Aug 2 '13 at 10:10
  • $\begingroup$ On the contrary, we know that most problems will be left out, since there are only countably many definable problems, but uncountably many problems in total. More concretely, you ask how to define "really hard" problems, the recursion-theoretic analog of large cardinals. If that's what you're interested in, ask a new question focused on this aspect. $\endgroup$ – Yuval Filmus Aug 2 '13 at 12:00
  • $\begingroup$ A similar problem shows up when constructing hierarchies of recursive fast-growing functions, in which case it is known that in some sense, there is no way to construct a nice, exhaustive hierarchy. $\endgroup$ – Yuval Filmus Aug 2 '13 at 12:03

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.