From the “weird math questions” department...
Here’s something I’ve been wondering about, in the context of Solomonoff induction and uncomputable sequences.
I have a device that is either a halting oracle, or an ordinary Turing machine which gives the correct answer to the halting problem for all programs smaller than some finite length N but always outputs “does not halt” when asked to evaluate programs larger than N. If you don’t know what N is and you don’t have infinite time, is there a way to tell the difference between the actual halting oracle (which gives correct answers for all possible programs) and a “fake” halting oracle which starts giving wrong answers for some N that just happens to be larger than any program that you’ve tested so far?
The Kolmogorov complexity of an uncomputable sequence is infinite, so Solomonoff induction assigns it a probability of zero, but there’s always a computable number with less than epsilon error, so would this ever actually matter?
It’s very possible that I misunderstood your question, but here’s a stab at an answer.
Assume that you have such a testing procedure. First let’s run it on a device that is actually a halting oracle. Presumably the procedure would ask the device a finite number of questions, receive correct answers to all of them, and then declare “yes, this is a halting oracle”. Let N be the length of the longest question thus asked. Then a fake halting oracle with length limit N would also pass the procedure.
I think there’s an assumption in this that isn’t quite spelled out by the question being asked: your argument holds if the lengths of the programs which you test the argument on are not a function of the oracle.
To say that more clearly, you state that for all L, if you give programs of length at most L to the maybe-oracle, then there exists a maybe-oracle for which N>L and hence that maybe-oracle goes undetected. But if we reverse the for-all and the there-exists, then we don’t have a true statement: there does not exist a maybe-oracle such that for all L we cannot detect it. So if the question allows us to ‘inspect’ the maybe-oracle and then pick L, it might be possible.
That said, I strongly suspect that there’s no coherent way to ‘inspect’ a maybe-oracle without knowing whether it is a Turing machine or not and I bet that the OP was intending for the oracle to be a ‘black box’ with nothing known other than the outputs that we ask it for. I initially wanted to make L a function of the length of the maybe-oracle—but what is the length of the true oracle given that it is not a Turing machine? If it is expressed as some ur-machine that includes Turing machines as a subset, then it might be possible to define a length and use this to determine an L.
Rice’s theorem makes me suspect that even this is not enough, but I’m not familiar enough with this field to say more. Thoughts?
Oracles are not strings, and cannot be inspected. Typically what you do is consider a Turing machine that uses a particular oracle as a subroutine.
This comment confuses question length and program length.
Yeah, that’s what I kind of figured, too...
Note that the halting problem isn’t very relevant here. You can take a much simpler problem, like computing the sum of two integers. By the same argument, it’s just as impossible to fully test a black box that claims to be an adding machine, but outputs garbage for inputs greater than some N. Moreover, you can’t always determine whether a box is an adding machine even if you’re allowed to look inside the box and inspect its algorithm, by Rice’s theorem.
For any broken halting oracle there exists a broken halting oracle detector that identifies it and for any broken halting oracle detector there exists a broken halting oracle that escapes detection.
IF AND ONLY IF you know that the object is either a true or fake oracle: you can determine that it is oracular for all programs of some finite length X, where X is determined by the amount of time you want to spend feeding in n-length programs known to halt.
For any given X, you’ve identified that the oracle is true for X or less, but you cannot confirm that X > N, and thus cannot confirm whether the oracle is true or fake, simply that it will be true for all lengths X or less.
That said, if your goal is to evaluate program A, you can just run a known-halting problem of the same length past the oracle to confirm that it’s valid for evaluation of this program. If you do this for each program you evaluate, then your results become “halts”, “doesn’t halt”, “this is actually a fake oracle, oops”, with 100% confidence :)
(I realize 100% confidence should never exist, but if there is the possibility of it being a true oracle, a fake oracle, or a different sort of fake oracle, then NONE of these conclusions is valid. So we get to play with a hypothetical super-certainty world where there’s only true and fake oracles :))
I feel this is a bit of an artifact of the problem statement though—I feel a more “realistic” scenario is that we are given a block box which which is either an oracle, or is correct for programs <N and returns arbitrary answers (sometimes correct, sometimes not) for longer programs.
If false oracles are wrong 50% of the time for length > N, you can run the test program X times, and have 1/2^X odds of it being a false oracle if it matches each time. Obviously, if the test program fails, you now know N is less than the test program’s length.
So, if you run the test program 4 times, odds are 1⁄16 that the oracle is fake, and 15⁄16 that it is real. For any “realistic” scenario, there’s a probability of even a regular computer program failing due to hardware glitches, so you’ll eventually approach the same confidence you’d have in a standard desktop PC calculating 2+2 :)
(This solution does somewhat generalize to odds other than 50%: once you find ANY test program that fails, you can repeat that program numerous times to estimate the oracle’s actual failure rate.)
The idea that the oracle flips a coin to determine if the test program of length >N halts is also not terribly “realistic”.
Instead, how about the following: the black box is either an oracle, or uses some sort of clever but not foolproof heuristic to guess whether or not a program halts, such that all programs for which the heuristic fails have length >N. One example of this is a Turing machine that runs a given program for BB(N) steps to see if it halts.
Then finding a test program that fails would actually be fiendishly difficult: you basically have to come up with a better heuristic than whatever the black box uses, so that you get a program which you know to halt, but the black box will be wrong about.
Nice! Even simple problems are often just one step away from an interesting idea.
Follow-up: Would AIXI (the ideal implementation of Solomonoff induction) do significantly worse at predicting the next digit of Chaitin’s constant than a computable algorithm that “knows” that it’s trying to predict the next digit of a specific uncomputable sequence with defined properties?
Also, for the lulz, I’d like to run AIXItl on “A Million Random Digits” and see if it really is algorithmically random.
No matter what input sequence you have and what algorithm you use to predict it, as you process more and more digits, your accumulated log score will stay lower than Solomonoff induction’s log score plus a constant (the constant is allowed to depend on the input sequence and your algorithm).
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.
If N considers the program’s length regardless of compressability, then you should be able to feed the “fake” halting oracle longer and longer programs that you already know will halt (like “print 1“ “print 11” “print 111”). Since it actually gives reliable output after N, you can do something like a binary search (modified for infinite lists) to find its limit.
So, how do you know in finite time whether it is a true oracle or if you haven’t yet found N?
If the oracle is fake, you will find out in finite time since eventually you will print N 1s, and the oracle will lie about that program. If the oracle is true, this method will never terminate. But I don’t think there is a way for a Turing machine to check for a true oracle (only for a fake oracle!).
What if the finite time needed to determine N is greater than the finite time that you have available?
OP asked “is there a way” not “is there a fast way”.
“In finite time” is not the same as “Using a halting process”
Write a short program that applies my method to an oracle. (Don’t run it yet)
Use my method to determine whether the oracle is “true” or “fake” for N = your program length. If “fake”, then you’re done.
If “true” for N = your program length, then ask the oracle whether your program will halt. If so, then it’s “fake”.
EDIT: Somehow, I wrote the above having forgotten that the fake oracle outputs “never halts” above N, not “will halt”.
Alternatively, you could just keep applying the method up to N that you’re concerned about—you will thus always know before trusting the oracle with a program of length N, whether it’s true or fake.
Write a program which halts if our oracle is false in the specified manner, and which does not halt if the oracle is true (for example, a program which tests a trivial halting program of length ++ in a loop.) You don’t run that program, but you do determine that our oracle gives a true answer for programs of that size, by testing a longer halting program of the trivial type.
You then test the oracle on that program- if the oracle says the program halts, it is a false oracle. If the oracle says that program does not halt, it is not a false oracle of the specific type described in the problem.
And it can be solved in constant time- you need to ask the oracle twice.
I didn’t see that you didn’t actually have to test the oracle with a program of length N+1; you only need to figure out how to ask the oracle what it would say when asked that question.
This is not a program, since the oracle is not a program, and so can’t be called as a subroutine. Since this is not a program, it can’t be given to the oracle.
By the way, one way of doing this is:
Make your best guess for N and check it.
If the test comes out “fake”, perform a binary search from 1 (or the highest known “true” value) to N
If the test comes out “true”, double N and goto 1.
I don’t think there’s an optimal search algorithm for an infinite list of unknown distribution. Anyone know better?
That’s a good one, for some priors about N. Any definition of “better” or “optimal” will be with respect to a prior about N. That prior can be unbounded and still produce good algorithms.
The obvious thing to tweak about your program is the “double N” constant; you could instead go to 3*N or something.
If you know your prior in detail, you’ll want to make your next guess to split the remaining probability weight evenly, not just the numeric search space. (Similar in concept to arithmetic coding.) With a poor understanding of the prior, though, this is a very minor detail.
Are you allowed to write a program which calls the possible oracle as a function and which uses recursion, are you allowed to have multiple programs, and are you allowed to write to those programs? If so, I wonder if the series below would do. (I’m not going to suggest it works, until I have a few other people check it, and until I make sure that the psuedocode is understandable.)
Program A:
Call Program B;
if Possible Oracle(Program B)=”halts” then do;
Add line “Print ‘even more gibberish’ to the beginning of Program B;
Call Program A;
end if;
else if Possible Oracle(Program B)=”does not halt” then do;
print “Possible Oracle is a fake.”
end if;
End Program A.
Program B:
Print ‘even more gibberish’;
End Program B.
And then after defining all of that, run Possible Oracle(Program A);
Let’s say Possible Oracle is a 20 line fake.
It starts Running A to see if it halts. The first time it runs through the loop in A, it runs B, which is 1 line. It then tests B, which is 1 line. It reports correctly that B halts. Based on that, it adds 1 line to B, and runs B, which is now 2 lines. It then tests B again, which is 2 lines. It reports correctly that B halts.
(Later)
Based on that, it adds 1 line to B, and runs it again. B is 21 lines. It then tests B, which is 21 lines. It reports incorrectly that B does not halt. Prints “Possible Oracle is a fake.”, and Program A ends, so it reports Program A halts. sure enough, it’s a fake.
Let’s say Possible Oracle is real.
It starts Running A to see if it halts. The first time it runs through the loop in A, it runs B, which is 1 line. It then tests B, which is 1 line. It reports correctly that B halts. Based on that, it adds 1 line to B, and runs B, which is now 2 lines. It then tests B again, which is now 2 lines. It reports correctly that B halts. Based on that, it adds 1 line to B, and tests it again…
(Later)
Program A, as far as I can tell, can’t halt for a true oracle.
Let’s Assume B gets to the point where it does not halt. then since Program A will run that Program B, Program A will never halt.
Let’s Assume B never gets to the point where it never halts. then since Program A calls the possible oracle, it will report that Program B halts, and if that’s the case, it calls an additional Program A instead of ending. The first Program A will never halt.
I think that should work, but unfortunately I don’t have a fake oracle and a real oracle to use for testing.
Edit: Fixed line breaks
Presumably you can’t ask the oracle about the halting behavior of programs which call the oracle. Otherwise the standard proof that the halting problem is undecidable can be used to show that the oracle is fake: just have a program ask the oracle about itself, then do the opposite.
Ah, I didn’t realize that. From looking over my program again, this appears to mostly be a slightly longer algorithm that does more or less what Thomblake said earlier. I didn’t realize that was what I would end up with when I started trying to make one, but I guess it’s a standard way of looking at it.
If I am allowed to use only exponentially more computing power than you (are far cry from a halting oracle), then I can produce outputs that you cannot distinguish from a halting oracle.
Consider the following program: Take some program P as input, and search over all proofs of length at most N, in some formal system that can describe the behaviour of arbitrary programs (ie first order PA) for a proof that P either does or does not halt. If you find a proof one way or the other, return that answer. Otherwise, return HALT.
This will return the correct answer for all programs of which halt in less than (some constant multiple of) N, since actually running the program until it halts provides a proof of halting. But it also gives the correct answer for a lot of other cases: for example there is a very short proof that “While true print 1”.
Now, if I am allowed exponentially more computing power than you, then I can run this program with N equal to the number of computations that you are allowed to expend. In particular, any program that you query me on, I will either answer correctly, or give a false answer that you won’t be able to call me out on.
Can you re-phrase this please? I don’t understand what you are asking.
What if I give you a program that enumerates all proofs under PA and halts if it ever finds proof for a contradiction? There is no proof under PA that this program doesn’t halt, so your fake oracle will return HALT, and then I will have reasonable belief that your oracle is fake. Also, in this part:
Did you mean to write “for all programs that halt in less than (some constant multiple of) N steps”, because what you wrote doesn’t make sense.
Yes. Edited.
That’s cool. Can you do something similar if I change my program to output NOT-HALT when it doesn’t find a proof?
Consider a program that enumerates all proofs under PA of length up to N^c for some c. If it finds a contradiction, it loops forever, otherwise it halts. I have reasonable belief that it halts, but your fake oracle can’t prove that it does using a proof of length at most N, if c is sufficiently large (see On the length of proofs of finitistic consistency statements in first order theories).
Or here’s another way that doesn’t depend on that result. Define program A as follows: Enumerate all proofs under PA up to length N. If it finds a proof for “program A halts”, then it loops forever, otherwise it halts. If PA is consistent, then it must be that A halts but there’s no proof for it under PA of length N or less.
Okay, I concede. I recognize when I’ve been diagonalized.
Yes. There are programs that can neither be proven to halt nor to not halt. The knowledge that these do not halt would need to be specifically programmed in, and the K-complexity would increase for each one.
On the other hand, it’s not exactly known how common these are. They might be pretty rare.
In any case, you could change it from shortest computer program to shortest definition, and thus get definable numbers instead of computable ones.
The only way to tell the difference between such a a machine and a halting oracle is to test a program larger than N which is known to halt.
So, no.