Im sorry if this question has some trivial answer which I am missing. Whenever I
ID: 650485 • Letter: I
Question
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.
Explanation / Answer
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.