58
$\begingroup$

To be more specific, does there exist a decision problem $P$ such that

  • given an oracle machine solving $P$, the Halting problem remains undecidable, and
  • given an oracle machine solving the Halting problem, $P$ remains undecidable?
$\endgroup$
58
$\begingroup$

Yes!

We can define an equivalence relation on decision problems: $A\equiv_T B$ if $A$ computes $B$ and $B$ computes $A$. This defines the partial ordering of Turing degrees: decision problems ordered by relative reducibility.

The properties of this partial order have been extensively studied. Some results include:

  • Given any nonzero (= not the degree of the computable sets) Turing degree $d$, there is a $\hat{d}$ which is incomparable with $d$ (this answers your question).

  • In fact, any Turing degree is contained in an antichain of degrees of size continuum.

  • Every Turing degree is above only countably many degrees, so the "height" of the Turing degrees is $\omega_1$; in case CH fails, this means the poset of Turing degrees are "wider" than it is "tall."

  • The Turing degrees form an upper semilattice - given decision problems $A, B\subseteq\omega$, the join of their degrees is the degree of $\{2n: n\in A\}\cup\{2n+1: n\in B\}$. Moreover, this semilattice has no top element (because of the Turing jump).

  • However, their exist Turing degrees $d, \hat{d}$ with no greatest lower bound.

  • Moreover, nontrivial infinite joins never exist (Exact Pair Theorem): given an infinite set of degrees, $D$, if $D$ is nontrivial (= does not have a finite subset $D_0$ such that $\forall d\in D\exists d_0\in D_0(d\le_T d_0)$) and $a$ is an upper bound of $D$, then there is a degree $b$ which also is an upper bound of $D$, and which is incomparable with $a$; moreover, $\{d: d\le a, d\le b\}=D$.

  • If $A'$ and $B'$ are the halting problems of $A$ and $B$, and $A\le_T B$, then $A'\le_T B'$. This means the jump can be thought of as an operation on degrees, not just sets. It turns out this operation is definable just in terms of the partial ordering! This was an extremely surprising result; see https://math.berkeley.edu/~slaman/talks/sw.pdf.

  • The converse of the above bullet point fails extremely badly: the jump is not injective, and indeed given any degree $d$ above the halting problem, there is a minimal degree $\hat{d}$ whose jump is $d$. (Minimal here means, "not $\ge_T$ any degree except itself and the degree of computable sets.)

This is all about the global theory of the Turing degrees; people have also studied extensively the local theory of special subclasses of Turing degrees. The best known such class is the class of degrees of domains of partial computable functions, the c.e. degrees. Of course, the degree of the halting problem is the maximal c.e. degree, so in this context the answer to your question is “no;” however, given any c.e. degree which is not the degree of the halting problem or the computable sets, there is an incomparable c.e. degree. This is the Friedberg-Muchnik Theorem, and its proof was a precursor to the method of forcing in set theory.

Let me end by stating my favorite two open questions about the Turing degrees:

  • Does the poset of all Turing degrees have any nontrivial automorphisms?

  • Does the poset of c.e. degrees have any nontrivial automorphisms?

Back in the day both these degree structures were believed to be very homogeneous, with lots of automorphisms; the theme of pure computability theory post-1955ish, however, was quite the opposite: the Turing/c.e. degrees are structurally rich, with lots of definable subclasses, and in fact it is now believed that both partial orders are rigid. All that is currently known however is that the automorphism groups are at most countable.


Finally, having said that the answer to your question is “yes,” let me explain a sense in which the answer to your question is “no.” The only “natural” increasing functions on the Turing degrees which have been discovered so far are (essentially) iterates of the Turing jump. Martin conjectured that

(1) Assuming ZF+AD, every increasing function is (perhaps when restricted to the set $\{d: d>c\}$ for some $c$; that is, “on a cone") an iterate of the jump.

(2) Assuming ZFC, Every Borel function which is degree-invariant and increasing is an iterate of the jump, on a cone.

Currently weak versions of Martin’s conjecture have been proved, although the full conjecture is still very much open.

$\endgroup$
  • $\begingroup$ Very thorough answer! If you'll allow me to go one step further, are you aware of any explicit examples of decision problems with independent undecidability from the Halting problem? $\endgroup$ – David Zhang Jun 16 '15 at 15:16
  • 1
    $\begingroup$ No, and in fact none are known: this is part of the motivation behind Martin's conjecture, that we don't know of any natural degrees "off the beaten path" of iterates of the jump of 0. $\endgroup$ – Noah Schweber Jun 16 '15 at 15:21
  • $\begingroup$ However, such degrees do have explicit descriptions: you can write down a $\Sigma^0_2$ formula $\varphi$ such that $\{x: \varphi(x)\}$ is Turing incomparable with $0'$. Unfortunately, it's not unique even up to $\equiv_T$. So, one might say that there are explicit examples, but no natural examples. $\endgroup$ – Noah Schweber Jun 16 '15 at 15:22
  • $\begingroup$ Looking instead at natural examples of c.e. sets, about which more is known: there are some precise negative results known in this direction. For example, I believe (I'm blanking on the reference) that Sacks showed there is no $e$ such that for all $X$, $X<_TW_e^X<_TX'$, that is, we can't find intermediate c.e. degrees uniformly. On the other hand, this leaves "unrelativizing" candidates. For example, it is possible (but extremely unlikely) that the set of (codes for) polynomials with rational solutions is of intermediate c.e. degree; see qcpages.qc.cuny.edu/~rmiller/slides/IMS2015.pdf. $\endgroup$ – Noah Schweber Jun 16 '15 at 16:12
  • 1
    $\begingroup$ @MarioCarneiro Sorry, I missed your comment. The construction is a nice one, and goes as follows: we build an infinite perfect subtree $T$ of the full binary tree $2^{<\omega}$ such that any two paths through $T$ have incomparable Turing degree. Now since $T$ is perfect, there is a natural bijection $f$ between $2^\omega$ and $[T]$ (the set of paths through $T$). Moreover, $f$ is computable relative to $T$, in the sense that there is a natural number $e$ such that for all reals $X$, $$f(x)=\Phi_e^{T\oplus X}.$$ $\endgroup$ – Noah Schweber Jul 27 '15 at 2:59
2
$\begingroup$

The Wikipedia article on Turing degree states that for every non-zero degree there is an incomparable degree. In your case, this means that there is some degree which is incomparable with 0', and any member of this degree answers your question.

$\endgroup$
  • 4
    $\begingroup$ Are you aware of any explicit examples of decision problems having such a degree? $\endgroup$ – David Zhang Jun 16 '15 at 15:18
-2
$\begingroup$

Although the given answers are correct (and quite thorough and explanative), i would say that the answer to your question is no.

To be more clear, the halting problem is not a specific problem, but a class of problems, one for each machine (or class of machines) $X$.

Each higher (un-)decidability problem is just a version of a halting problem for an appropriate machine $X$. The fact that there are machines that can compute more than other machines (e.g through oracles), is reflected in their corresponding halting problems.

In this sense, no undecidability problem is different than a halting problem (and the answer to your question is no and it has been already hinted in this direction by other answer).

However, if one refers to a specific halting problem (e.g for the classic universal turing machine) then as already stated there are undecidability problems that can be termed as harder (i.e turing degrees etc..)

Some references (related to first answer as well):

  1. Global Properties of the Turing Degrees and the Turing Jump
  2. Defining the Turing Jump
  3. Degrees of Unsolvability
  4. Turing Degree, wikipedia
  5. Turing Jump, wikipedia
$\endgroup$

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.