The mother of all undecidable problems

Question

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P.

Is it the case that the halting problem is the mother of all undecidable problems in the sense that it reduces to any undecidable problem? If the answer is negative, can you show a (preferably simple) counterexample, i.e., an undecidable problem to which the halting problem does not reduce?

Answer 1

If I understand the question correctly, it is : "is the halting problem the simplest of all undecidable problems, in the sense that the knowledge of any other undecidable problem would be enough to solve the halting problem ?".

I would say the answer is both no and maybe. It is no in the sense that there are undecidable sets which cannot compute the halting problem. "almostall" proposed a nice non-constructive argument for that. It is also possible to construct such sets. In particular, there are non decidable computably enumerable sets (then decidable by the halting problem) but which cannot decide the halting problem (search "Post problem" and "priority method" on google).

Now for the "maybe", it is true that there is no natural example of such problems, and an attempt to formalize mathematically what is a 'natural example', in order to prove that the halting problem is the only one, has been made. I cite here a part of "There is no degree invariant half-jump" from Rod Downey, that emphasizes this phenomenon:

A striking phenomena in the early days of computability theory was that every decision problem for axiomatizable theories turned out to be either decidable or of the same Turing degree as the halting problem $\emptyset'$ the complete computably enumerable set). Perhaps the most influential problem in computability theory over the past fifty years has been Post’s problem of finding an exception to this rule, i. e. a noncomputable incomplete computably enumerable degree. The problem has been solved many times in various settings and disguises but the solutions always involve specific constructions of strange sets, usually by the priority method that was first developed (Friedberg and Muchnik) to solve this problem. No natural decision problems or sets of any kind have been found that are neither computable nor complete. The question then becomes how to define what characterizes the natural computably enumerable degrees and show that none of them can supply a solution to Post’s problem.

It might take us too far now to continue on what is the mathematical formalization of the question of the existence of a 'natural example' of undecidable problems, plus, I'm not a specialist on this anyway. But if you want to do some research, maybe you can look for Sacks question : "Is there a degree invariant solution to Post problem ?", which as far as I know is still open, at least in its general form.

Answer 2

One way to show this is by proving that the set of reals that compute the halting problem has both measure zero and is of first category (countable union of nowhere dense sets). The existence of reals that do not compute the halting problem follows.