Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
@anon, it's not an oracle that halts. It's an oracle that (immediately) answers instances of the Halting Problem. –  Henning Makholm Sep 12 '11 at 19:22
    
@Henning: Oh. That's what I get for only ever reading about this stuff on Wikipedia. –  anon Sep 12 '11 at 19:24
    
I expect the answer to this problem to be "no," so a follow-up question: how efficiently can you verify that the halting oracle is correct for programs of length up to $n$ in terms of $n$? –  Qiaochu Yuan Sep 12 '11 at 19:41

1 Answer 1

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.

share|improve this answer
    
What if I didn't ask a yes-no question? What if my question was of the form, does this Turing machine halt on this input, and if so, in how many steps? –  Craig Sep 12 '11 at 20:02
    
Then it wouldn't be an "oracle" in the usual sense -- it's supposed to deliver one bit of information each time it is invoked. Of course you could require the oracle to be able to answer questions about single bits of the running time, but since the running time could be arbitrarily long, it would be impossible to reliably detect a cheating oracle that kept saying, "oh, there are more bits of the result yet; keep asking". –  Henning Makholm Sep 12 '11 at 20:06
    
I don't know. My problem statement was that he is claiming to have a halting oracle. So I think I should be able to ask him any (set of) question(s) that a person, equipped with a halting oracle, could answer in finite time. Yes, if he takes an infinite amount of time to answer any question, I can't verify it. –  Craig Sep 12 '11 at 20:23
1  
The obvious change to handle step counting is to give it TM description + step count limit and ask "Does it halt in fewer steps?" But then it's easy to construct a TM which is equivalent to that oracle. –  Peter Taylor Sep 21 '11 at 13:04
3  
@Peter: +1 for that. But the trouble is, the TM that you construct may take a very long time to run if the number of steps is very large. So what you could do instead, given a number of steps $n$, is to construct a TM which halts if and only if the original TM halts in $n$ steps or fewer. Then just feed this new TM to the oracle. –  TonyK Sep 21 '11 at 14:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.