11
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What do you know about Turing degrees? $\endgroup$ – Asaf Karagila Aug 13 '14 at 20:59
  • 2
    $\begingroup$ The answer to your question is no, but counterexamples are a little artificial until you get used to computability theory. $\endgroup$ – James Aug 13 '14 at 21:02
  • 2
    $\begingroup$ Bob, he was speaking intuitively. $\endgroup$ – Eric Stucky Aug 13 '14 at 21:39
  • 1
    $\begingroup$ I think one of Sacks open question includes some formalization of "natural" and asked if there was a natural intermediate c.e degree between 0 and 0'. $\endgroup$ – William Aug 13 '14 at 22:00
  • 2
    $\begingroup$ I think what James mean by artificial is that counterexample are constructed by taking a universal Turing machine and doing a very clever diagonalization argument. In this way the Halting is also artificial. However there are many natural mathematical problem (like tiling problem, integer root of polynomial) which are equivalent to the Halting problem. This makes the Halting seem more natural. The other counterexample are not known to be associated to any concrete math problems like this. $\endgroup$ – William Aug 13 '14 at 22:08
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The "maybe" answer might be theoretical justification for a restricted flavor of set theory. What should we remove from set theory so that "specific constructions of strange sets" (the words of Downey) becomes impossible, thus giving a positive answer to my question? Probably someone already came up with such restriction. $\endgroup$ – Bob Aug 14 '14 at 8:03
  • $\begingroup$ Pretty much everything should be removed from set theory in order to forbid the construction of those 'strange sets'. They are actually not that strange. They are computably enumerable. If you keep enough axioms to talk about Turing computations (which seems reasonable) then the existence of those sets is provable. You can prove for example (Sacks did) that you can split the halting problem into two disjoint c.e. sets, so that none of those two halves can decide the other half. Then at least one of them is not computable, but cannot decide the halting problem. $\endgroup$ – Archimondain Aug 14 '14 at 12:13
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Er, er, what do you mean? $\endgroup$ – Bob Aug 13 '14 at 21:48
  • $\begingroup$ But this does not suffice, as in this context we want to restrict our attention to r.e. reals. $\endgroup$ – Andrés E. Caicedo Aug 14 '14 at 6:02
  • 2
    $\begingroup$ I don't see anything in the original question about r.e. sets; I voted this +1. $\endgroup$ – Carl Mummert Aug 14 '14 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.