This is a linkpost for https://www.sciencedirect.com/science/article/pii/S0890540126000738
I'm not an AI researcher, and I haven't studied AIXI, but I have read part of Hutter's Universal Artificial Intelligence, enough to cover Solomonoff induction. Yet I'm feeling kind of lost as to the context where you would want to know where a function is in this hierarchy. Is it... like... when you do Solomonoff induction but the environment is something quantitative like physics?
Oh, I see you cite this paper called "On the computability of Solomonoff induction and AIXI". So I shouldn't be thinking of "a function such as one used in Solomonoff induction's environment", I should be thinking of "a function such as Solomonoff induction"? But Solomonoff induction maps binary strings to rational probabilities... so should I be thinking of something like Solomonoff induction but getting real numbers as input? Oh, no, we want to characterize whether Solomonoff induction is computable assuming we have oracles for certain types of functions in this hierarchy. Right?
Solomonoff induction (e.g. next-bit conditional probabilities of the universal distribution) is a function of discrete domain and real codomain. We sometimes want to compose SI with real domain operations (e.g. in order to calculate a value function we take products and sums). But usually the real domain operations live lower in the hierarchy, so in some sense you're right that studying real domain hypercomputability is overkill. Most of the results in the paper hold for both discrete and real domain, sometimes discrete domain is nicer.
Okay. I'm just trying to get a sense of what kind of questions all of this is meant to answer. It sounds like we start with "SI is uncomputable, but is computable relative to some oracle". Now we want to say "this machine I have built out of SI is still computable relative to that same oracle". That kind of thing? And you're saying here that while the machine built out of SI is not a function from reals to reals, we can prove these statements by classifying functions from reals to reals involved in its construction.
Admittedly haven't read in detail, but doesn't the arithmetic hierarchy already define real numbers via a bijection with P(N)? And the real numbers are themselves in bijections with the functions from N->R? Would the corresponding hierarchy of functions N->R be different than the hierarchy here?
I wrote a fairly accessible introduction to real hypercomputation with Marcus Hutter. The focus is on enabling applications to algorithmic information theory. This project was intended to build my technical foundations for studying AIXI, but took me a bit further afield and down some rabbit holes. In the future I will prefer to focus more tightly on AI safety.
Feedback would be appreciated. In particular, I needed to introduce an extra extensionality assumption for the real domain case, which I am still not sure is necessary.
Errata: The diagram of results currently has theorems misnumbered due to a typographical error.
Thanks to the LTFF for supporting my work over most of the research process.