The set of such oracles is at least recursively enumerable, I think. In order to detect that your oracle is not a true halting oracle for programs larger than N, all you must do is find a program larger than N that halts. If you have a proof that such a program halts, you simply feed it to your oracle, notice that the oracle is lying, and you are done.
But it’s not hard to find such a program. Simply simulate all programs of length ⇐ 1 for 1 steps, then all programs of length ⇐ 2 for 2 steps, etc. At some finite point you will find a program of size >N that halts in k steps. If your oracle is a true halting oracle, this procedure will not terminate, of course.
cousin_it’s argument below shows we can’t do much better than recursively enumerable here.
From the OP: “you don’t know what N is.” But, yes, you don’t have to do the “step simulation”, you are right. You can just check a single known halting program of every length, starting at 1, and increasing. Eventually you will catch the oracle in a lie.
See also: thomblake’s comment below, which gives the same algorithm.
I am aware that this is not a decision algorithm. I said in my original comment that the set is recursively enumerable, and I also said that the algorithm will not terminate on true oracles. That is, we can list the fake oracles, but we cannot decide on the fake status of an oracle in finite time. This is what recursively enumerable means: http://en.wikipedia.org/wiki/Recursively_enumerable_set.
If there is such a method, it has to get around cousin_it’s argument below. I believe you can only enumerate fake oracles, not answer if an oracle is fake or real, in finite time.
The OP didn’t ask what you can determine for a particular given finite time k. He asked if there is some finite way, period.
This is starting to remind me of wikipedia edit wars. I think it’s time to exit this conversation. OP’s question is answered, if he’s still interested.
You don’t need to do it for all N, just up to the N which the fake oracle is computing. Expected computational time for a randomly chosen N is infinite, but expected computation time for any -given- N is finite.
And only finite time is available- for most N, expected computation time is greater than available time; expected time is constant, and a finite number of N will have computation tine less than any C.
The set of such oracles is at least recursively enumerable, I think. In order to detect that your oracle is not a true halting oracle for programs larger than N, all you must do is find a program larger than N that halts. If you have a proof that such a program halts, you simply feed it to your oracle, notice that the oracle is lying, and you are done.
But it’s not hard to find such a program. Simply simulate all programs of length ⇐ 1 for 1 steps, then all programs of length ⇐ 2 for 2 steps, etc. At some finite point you will find a program of size >N that halts in k steps. If your oracle is a true halting oracle, this procedure will not terminate, of course.
cousin_it’s argument below shows we can’t do much better than recursively enumerable here.
Wouldn’t it be easier to just generate a single program of size > N that halts by construction?
From the OP: “you don’t know what N is.” But, yes, you don’t have to do the “step simulation”, you are right. You can just check a single known halting program of every length, starting at 1, and increasing. Eventually you will catch the oracle in a lie.
See also: thomblake’s comment below, which gives the same algorithm.
This is not a decision algorithm: if the oracle actually is real, your program will never terminate.
Edit: I guess you realize this already, but there are a few confused comments from other people here, so I will not retract this.
I am aware that this is not a decision algorithm. I said in my original comment that the set is recursively enumerable, and I also said that the algorithm will not terminate on true oracles. That is, we can list the fake oracles, but we cannot decide on the fake status of an oracle in finite time. This is what recursively enumerable means: http://en.wikipedia.org/wiki/Recursively_enumerable_set.
This is different from “recursive” (http://en.wikipedia.org/wiki/Recursive_set) where we can decide on membership in finite time.
I’m pretty sure that there is a method to determine the fake status of any oracle in finite time.
If there is such a method, it has to get around cousin_it’s argument below. I believe you can only enumerate fake oracles, not answer if an oracle is fake or real, in finite time.
Right.
It’s even easier to find such a program. String together N-1 commands that each leads into the next, and then a STOP.
Now, do this in finite time for all N without knowing N.
This procedure works for all finite N, without knowing what N is. I am confused by your comment.
Given finite time, there is a maximum N that you can test.
The OP didn’t ask what you can determine for a particular given finite time k. He asked if there is some finite way, period.
This is starting to remind me of wikipedia edit wars. I think it’s time to exit this conversation. OP’s question is answered, if he’s still interested.
You don’t need to do it for all N, just up to the N which the fake oracle is computing. Expected computational time for a randomly chosen N is infinite, but expected computation time for any -given- N is finite.
And only finite time is available- for most N, expected computation time is greater than available time; expected time is constant, and a finite number of N will have computation tine less than any C.