1
$\begingroup$

Define a "predicting oracle" to be an oracle that does as described in this question.



default (weak) version:

Is it the case that, for every predicting oracle $O$, there exists an
oracle machine $M$ such that when $M$ operates on $O$, the result
computes a function that dominates all (ordinarily) computable functions?


uniform (strong) version:

Does there exist an oracle machine $M$ such that for every predicting oracle $O$, when $M$ operates on $O$, the result computes a function that dominates all (ordinarily) computable functions?

$\endgroup$
2
$\begingroup$

The uniform version is theorem 7 of the paper "Inductive inference and unsolvability" by Adleman and M. Blum. The result is for Gold's model of learnability in the limit (the oracle, instead of predicting the next bit, gives you an index of a program that computes the sequence you are trying to discover). Both models are equivalent.

The idea behind the proof is that, for every total computable function $h$ there is a total computable function $g$ whose running time dominates $h$. So, you use the oracle to, on input x, find the greatest of the running time of all functions inferable from a prefix of length $x$. In order not to run forever, you stop counting the steps of the function predicted by the oracle if you find that it will change its prediction when a finite number of 0s are appended to the prefix (this eventually happens because the oracle has to predict every finite variation of the constantly 0 function). The trick is that for every $h$ and every sufficiently large $z$, the output is at least as big as the number of steps to compute $g(z)$, for the respective $g$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy