3

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)?

Xoff
  • 10,310
  • 2
    Hardly. If one of the oracle can decide the halting problem and another oracle differst only in the single input of one non-terminating algorithm that it falsly says should terminate, then I don't see how you could ever decide which one is right. – Peter Franek Mar 14 '15 at 12:39
  • Thanks, that's also what I thought. But I cannot turn it into a proof that there is no such Turing machine. – Tingxiang Zou Mar 15 '15 at 17:49
  • Well, let's suppose the two oracles differ only in the input i, and i does not terminate, then by padding, we can compute easily from i, some i' which do exactly the same as i, and ask oracles if i' terminates or not, then we can tell which one gives the right answer. Of course, there can be "consistent" oracles, if i and i' computes the same thing, then the oralce gives the same answer for i and i'. This makes it tricky to find a rigorous proof. – Tingxiang Zou Mar 15 '15 at 20:02
  • I agree, that's why this is a comment and not an answer. I believe, however, that it shouldn't be too hard to formalize this and it seems to me that celtchk's arguments are on the right track. – Peter Franek Mar 15 '15 at 21:45

2 Answers2

3

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.

Noah Schweber
  • 245,398
  • Wow, finally the answer is there! Thanks a lot! A little comment, since the machine works along the feeding of oracles, I think maybe it would be clearer if in the definition of discernible, we replace 0 by the inifinite constant sequence 0 and 1 by the infinite sequences which begins with finite-many 0 followed by all 1s (well, the machine can think left is the correct one in the beginning and then correct himself after seeing more bits.) – Tingxiang Zou Jun 07 '16 at 09:07
  • This question arised when I was trying some other problem which I have solved in the end, but still have not got the answer for this one. That problem is to disprove the following statement: there is a turing machine e, such that for all infinite sequnece X, if there is some turing machine e' with $\Phi_{e'}^X=halting$, then $\Phi_e^X=halting$. You see this statement is stronger than the original one, hence easier to disprove and interestingly I didn't use weak konig's lemma, maybe because the infinite thing is hidden in the statement itself. – Tingxiang Zou Jun 07 '16 at 09:23
  • The role of WKL is bothering me - I've asked a question at MathOverflow about it. http://mathoverflow.net/questions/241689/can-noncomputable-sets-be-distinguishable-in-rca-0 – Noah Schweber Jun 08 '16 at 02:10
1

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.

celtschk
  • 43,384
  • Thank you. But I cannot find a proof, if we assume such machine M exists, and construct some Turing machine which use M as a subrutine, then he should feed M with an input of which half should be the (finite sequence of) the Halting problem, which also seems impossible. – Tingxiang Zou Mar 15 '15 at 17:56
  • @TingxiangZou: I must admit I don't understand your comment. – celtschk Mar 15 '15 at 18:24
  • Sorry, I haven't made myself clear. I mean, it is intuitively true that a Turing machine which can distinguish the Halting from others should also be able to solve the Halting problem itself, but I cannot turn this idea into a rigorous proof. – Tingxiang Zou Mar 15 '15 at 19:34
  • Why don't you consider mine rigorous? – celtschk Mar 15 '15 at 19:47
  • Let's say the Halting problem is the version on empty input. Suppose the two oracles give different answers for i, one thinks i terminates, one thinks it does not terminate, then the machine can compute from i, by padding, i', which computes the same thing as i, and asks oracles again, if he is lucky, this time the oracles might give the same answer, that answer must be the right answer for i. So it is far from obvious that when oracles give different answers, the only way to decide is to determine the Halting probelm itself. – Tingxiang Zou Mar 15 '15 at 20:16
  • So oracle A gives "Yes", oracle B gives "No". The Turing machine adds an infinite loop, and both oracles give "Yes". So how is your machine to distinguish between (a) A is the halting oracle, i already doesn't halt, and B just happened to give "no" for i, and (b) B is the halting oracle, i does halt, and A just happened by chance to give "Yes" for i? Note that it could be that oracle A is "if the algorithm is i, give yes, otherwise consult the halting oracle", or it could be that oracle B is "if the algorithm is i, give no, otherwise consult the halting oracle". – celtschk Mar 15 '15 at 20:29
  • "By padding" means add something useless, adding a loop is not what I meant. For example, it can add an extra state into the set of states and all others remains the same, then i and i' will do exactly the same thing. If both oracle A and B says Yes for i', it must also be the case that the answer to i is yes. – Tingxiang Zou Mar 15 '15 at 20:54
  • So just choose as second oracle one that still gives the same answer for the padded machine (it may have access to a Turing machine equivalence oracle, after all). – celtschk Mar 15 '15 at 20:58
  • Yes, that can be the case, but we cannot prove it by discussing all such possibilities. – Tingxiang Zou Mar 15 '15 at 21:08
  • OK, take as second oracle the following: For any algorithm where your Turing machine can by itself decide whether it halts or not, it gives the same answer as the halting oracle, and for any other algorithm, it gives the opposite answer. There's no way your Turing machine can distinguish that oracle from the true halting oracle: If your Turing machine can proof two algorithms equivalent, either it can decide both, or it can decide neither. It it can decide it, it cannot use that to distinguish the oracles because both give the same result. Otherwise, it has no information to distinguish them. – celtschk Mar 15 '15 at 21:23
  • How do you define "a Turing machine can by itself decide a algorithm halts or not"? In the previous example we discussed, the Turing machine cannot decide whether i halts or not itself, but it can decide with the help of some particular orcales, namely, the oracles which have the same answer for i'. But with other oracles, this Turing machine will not be able to decide whether i halts or not. Thanks for your kindly help, and sorry for my annoying comments. – Tingxiang Zou Mar 15 '15 at 23:04
  • While a Turing machine cannot solve the halting pronlem for arbitrary code, it is possible to make a Turing machine that gives three results: "Halts for sure", "Runs forever for sure" and "Can't decide". As very simple example, it could give "Halts for sure" for the algorithm that halts immediately without doing anything, "Runs forever for sure" for the simplest infinite loop, and "Can't decide" for anything else. But more sophisticated algorithms will be able to successfully analyse more algorithms (but never all of them, as that would mean solving the halting problem). And since for some … – celtschk Mar 15 '15 at 23:16
  • … of the algorithms it can decide whether the algorithm halts, it could use those algorithms to test the oracles: If an oracle gives "Yes" for an algorithm known not to halt, it cannot be the halting oracle, and the same is true if the oracle gives "No" for an algorithm known to halt. Therefore our fake halting oracle must give the correct answer for all those algorithms the tested Turing machine can decide. But since the oracle is chosen only after knowing the Turing machine, that's not a problem; the set of algorithms it can decide is fixed as soon as the Turing machine is fixed. – celtschk Mar 15 '15 at 23:22
  • Well, that exlcudes the example we discussed before. But a Turing machine can decide the Halting with the help of oracles in other ways, for example, if oracle A says YES for algorithm i, while oracle B says NO, and for algorithm j, oracle B says YES, A says NO, then he can run i and j simultaneously, and one of them will halt, then he can decide which oracle is telling the truth. – Tingxiang Zou Mar 16 '15 at 09:32
  • Good point, I didn't think of that. But that's also easily solved: Just have an oracle that only lies on halting machines, and another one that only lies on non-halting machines (and otherwise both have the properties discussed before). Then this reciprocal situation cannot occur. Either all algorithms which give different results do halt, or all algorithms which give different results don't halt, depending which of the two oracles is connected, and there's no way the Turing machine can decide which of the two is the case, as all with different results are such that the machine can't decide. – celtschk Mar 16 '15 at 18:51