0

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

Tom Lehman
  • 187
  • only if the oracle is a computable function – Tim kinsella Jan 28 '18 at 04:01
  • Is it not possible to derive a contradiction from only a "black box" that solves the halting problem (versus an actual "computer")? – Tom Lehman Jan 28 '18 at 04:03
  • no, you need the black box to be a turing machine to get a contradiction, because you have to plug its index into itself. the oracle only accepts indices of turing machines. – Tim kinsella Jan 28 '18 at 04:04
  • 2
    That set of Turning machines that halt is perfectly well defined set. A "halting oracle" is nothing but adding the possibility to your machine to see if something belongs to that set or not. – Mariano Suárez-Álvarez Jan 28 '18 at 04:05
  • The mapping that assigns to a given program $P$ and input $x$ the value $1$ if $P(x)$ halts and $0$ otherwise is a perfectly well-defined function; it's just not computable. The meanings of the first and second 'compute' in your post are not the same. – anomaly Jan 28 '18 at 04:32

1 Answers1

5

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.

Noah Schweber
  • 245,398