12
$\begingroup$

Suppose someone comes to you and claims to have a halting oracle. Is there any way for you to verify the truth or falsity of their claim in finite time? If so, what constraints on the proof process are there? Does the verification have to be interactive? Can you only prove it to a given probabilistic bound?

Update: Henning, below, suggested an oracle $A_F$ that will say "Halt" unless the TM in question can be proved to have infinite run-time by some formal system $F$. He then claimed that one cannot tell this oracle from a true halting oracle. I am not certain of this; I suspect there may be some sequence of questions one can ask this oracle to trip it up in a lie. Can anyone prove or disprove this statement?

  • 0
    Could the answer be a probabilistic yes that converges to certainty if the available resources (time and space) are constrained?2018-10-16

2 Answers 2

11

It's clear that you cannot possibly hope for more than a probabilistic result -- any testing procedure that can pass a true halting oracle after asking it $n$ questions will also pass a random oracle with probability at least $2^{-n}$.

But I much doubt that you can get even a probabilistic guarantee. Suppose that the purported oracle was in reality a proof-search oracle that answers correctly when the program can be proved (in some fixed but unknown formal system) to either terminate or diverge, and otherwise answers "Halts". In order to conclude that this is not a true halting oracle, we would need to ask it about something that diverges, but unprovably so. We could ask it to search for a proof of an undecidable Gödel sentence, but since the formal system the fake oracle uses is unknown, it could just have added a finite number of Gödel sentences to its static knowledge.

  • 0
    @Tony, how is that trouble? We may easily imagine a fake oracle that gives the output of Peter's TM instantly (it's an oracle all right, just not the one we're trying to recognize).2011-09-21
0

A Turing machine can only answer a subset of the decision problems correctly, so with access to a larger subset you can rule out the machine having a halting oracle. However, this does not allow you to identify a halting oracle unless you yourself are a halting oracle.

On the other hand, if the Turing machine is constrained on size this limits the number of correct answers it can make. Then you can say it has a halting oracle operator if it exceeds the number of correct answers. This is only probably true if it is a probabilistic machine, but the probability goes to 1 as the trials go to infinity.