Why isn't the idea of "an oracle for the halting problem" considered self-contradictory?

Question

Doesn't the halting problem's uncomputability mean that if you had an oracle that "computed" it you could derive a contradiction?

Answer 1

I think this is a situation that can be made clearer by introducing a more general concept: relative computability.

There is a notion of "oracle Turing machine." In essence, an oracle Turing machine is a Turing machine with an "extra feature:" that we can equip it with an arbitrary set of natural numbers, which it is then allowed to query in the course of its computations. Just like with normal Turing machines, there is a natural listing of oracle Turing machines $(\Phi_e)_{e\in\mathbb{N}}$. We write "$\Phi_e^X$" for the $e$th oracle Turing machine with oracle $X$. Note that classical Turing machines can be viewed as oracle Turing machines equipped with a computable oracle (say, $\emptyset$).

For example, here is some pseudocode describing an oracle Turing machine $\Psi$:

• On input $n$, with oracle $X$: ask whether $n\in X$. If yes, output $0$; if no, output $1$.

For any oracle $X$, $\Psi^X$ gives the characteristic function of the complement of $X$: $\Psi^X(n)=1-X(n)$.

Say that a set $Y\subseteq\mathbb{N}$ is $X$-computable, and write $Y\le_TX$, if for some $e$ the oracle machine $\Phi_e$ with oracle $X$ computes the characteristic function of $Y$; concisely, if for some $e$ we have $$\Phi_e^X=Y.$$

Now, here's the neat fact:

There isn't just one halting problem!

For any $X\subseteq\mathbb{N}$, there is the "halting problem relative to $X$": this is the set $$X'=\{e:\Phi_e^X(e)\downarrow\}$$ (here "$\downarrow$" means "halts"). The usually proof of the undecidability of the halting problem shows that we never have $X'\le_TX$, and it's a good exercise to show that we always have $X\le_TX'$. It's also not hard to show that if $X_0\equiv_TX_1$ then $X_0'\equiv_TX_1'$. So the map $X\mapsto X'$ - called the "Turing jump" - induces a strictly increasing function on the Turing degrees (these are just the $\equiv_T$-classes of sets of natural numbers).

So if you have the halting problem $0'$ as an oracle, congratulations! You can compute $0'$. What you can't do, however, is compute your own jump $0''$. You've increased the power you have to compute with, but that's also increased the complexity of your halting problem, and you'll never catch your tail.

There's nothing wrong with one oracle computing another oracle's halting problem. That just means that the first oracle is much more complicated than the second. No oracle, however, will be able to compute its own halting problem.