Universal Turing Machine with an Oracle

Question

(Note: For convenience, I'm phrasing this in terms of computer programs rather than Turing machines.) Consider computer program P which does the following:

1. It asks the user to enter the code of a computer program

2. It consults an oracle to find out if there is any possibility that it will not halt if it runs the computer program in question.

3. If the oracle tells it that it may not halt if it runs the program, then it outputs "ERROR" and halts.

4. If the oracle tells it that it is guaranteed to halt if it runs the program, then it runs the program.

Now the question is, is P guaranteed to halt? Suppose it is guaranteed to halt, and let the code for P be c. Then the user can run P, and when prompted he can enter c, and then P will be run again, and when prompted the user can again enter c, and then P will be run again, and the user can enter c, etc. So P is not guaranteed to halt.

But if P is not guaranteed to halt, then if the user enters c, P will just output "ERROR" and then halt. Thus P is guaranteed to halt. So what's going on?

Any help would be greatly appreciated.

Thank You in Advance.

Answer 1

I believe that P is guaranteed to halt on any finite input, which is where your proof that this is impossible breaks down, as you give P an infinite input.

It would be impossible to guarantee that P halts on any input, as if its input is infinitely long, then even if P does nothing but read in the input and pass it to the oracle, it will not halt.

Edit: While I believe the above is correct when the oracle cannot act on itself, the bigger issue here is that this oracle cannot exist if you expect it to work on programs using itself.

Answer 2

I think the problem here is a little different: your "oracle" is too powerful. I believe valid computational models have well-founded oracles, in some sense—an oracle can't predict its own behavior.

Edit: The halting problem applies to oracles too. Suppose you had an oracle machine (a Turing machine hooked up to an oracle in some fashion) that took as input a description of a Turing machine designed to be hooked up to the same oracle and determine whether that machine, hooked up to that oracle, would halt. Proceed along the same lines as the usual halting problem proof to demonstrate a contradiction.