Is there a Turing Machine that can distinguish the Halting problem among others?

306 Views Asked by At

Can there be a Turing machine, that given two oracles, if one of them is the Halting problem, then this machine can output the Halting problem itself?

Clearly, if the first oracle is always the Halting problem, then such machine exists, just copy the first oracle. But if the Halting problem can either be the first or the second oracle, can a Turing machine distinguish which one is the Halting problem (for all such pairs of oracles)?

2

There are 2 best solutions below

3
On BEST ANSWER

Great question! The answer is indeed no, but it's a bit subtle - in particular, I think the existing answer + comment thread, while in the right direction, doesn't quite "stick the landing." I've sketched the argument, with a few hints (trying to keep the length down so the idea is clear).

First, I need to formalize the notion of a Turing machine "picking" between two reals:

Definition. A set $X\subseteq\omega$ is discernible if there is some $e$ such that, for all $Y\subseteq \omega$ with $Y\not=X$, $\Phi_e^{X\oplus Y}=0$ and $\Phi_e^{Y\oplus X}=1$. Think of "$0$" and "$1$" as meaning "Left" and "Right," here.

Proposition. $X$ is discernible iff $X$ is computable. In particular, the Halting Problem is not discernible.

Proof. Fix $X$ noncomputable; we'll show $X$ is not discernible (the other direction of course is trivial). The key is to think about Turing computations as acting on finitely much of the oracles.

For $\sigma, \tau\in 2^{<\omega}$, say $\sigma$ beats $\tau$ - and write "$\sigma\sqsupset\tau$" - if $\Phi_e^{\sigma\oplus\tau}=0$. (Here I use the convention that $\Phi_e^\alpha$ diverges if it ever attempts to query the oracle past the first $\vert\alpha\vert$-many bits, for $\alpha$ a finite string.).

Is $0$ in $X$?

Say that $\sigma\in 2^{<\omega}$ is $0$-definitive if $$\{\tau\in 2^{<\omega}: \tau(0)\not=\sigma(0), \sigma\sqsupset\tau\}$$ is finite. Clearly if $\sigma$ is $0$-definitive, then $\sigma(0)=X(0)$ (why?), and the set of $0$-definitive $\sigma$s is r.e. (why?).

The key point is that there exists a $0$-definitive $\sigma$! Why? Well, let $$Bad(0)=\{\tau\in 2^{<\omega}: \tau(0)\not=X(0), \not\exists\sigma\prec X(\sigma\sqsupset\tau)\}$$ be the set of strings which are not beaten by any initial segment of $X$, but are also wrong about $0$. The set $Bad(0)$ is a tree, and any infinite path through $Bad(0)$ would be the characteristic function of a set $Y$ such that $Y\not=X$ but $\Phi_e^{X\oplus Y}\not=0$; so by Weak Konig's Lemma, $Bad(0)$ is finite.

But then we can find a single $\sigma\prec X$ such that for all $\tau\not\in Bad(0)$ with $\tau(0)\not=X(0)$, $\sigma\sqsupset\tau$! (Why? Note that $\sigma\sqsupset\tau$ and $\tau\prec\tau'$ implies $\sigma\sqsupset\tau'$.) But then this $\sigma$ is $0$-definitive.

So there is a $0$-definitive string $\sigma$. Since the set of $0$-definitive strings is r.e., we just wait until we see one - and then look at what its first bit is.

Is $n+1$ in $X$?

We compute the rest of $X$ inductively: after determining the first $n$ bits of $X$, we look at only those strings which so far are correct: e.g. which agree with $X$ on the first $n$ bits.

15
On

No. Using programs where both oracles give the same output, you obviously cannot distinguish them. Therefore the only way to distinguish the oracles is to analyse programs on which both oracles give different results.

However, if the two oracles give different results, the only way to decide which oracle is the one answering the halting problem is to determine whether that algorithm halts.

Since your Turing machine is intended to answer the question for any pair of oracles, it has to be able to answer that question for any arbitrary algorithm, in order to distinguish the oracle that gives a different answer at only that one algorithm from the halting oracle.

But that means, quite literally, that the Turing machine must be able to solve the halting problem, which we know is impossible.