The mother of all undecidable problems 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?
 A: 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.
A: 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.
