# Reductions among Undecidable Problems

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.

• Short answer: far from trivial! Look at Arithmetical hierarchy. – Hendrik Jan Aug 1 '13 at 7:25
• 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. – Pål GD Aug 1 '13 at 10:39

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.