Problem Detail: 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.
Asked By : swarnim_narayan
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13559
