  How could we solve the machine learning and the artificial intelligence
problem if we had infinite computation? Solomonoff induction and the
reinforcement learning agent AIXI are proposed answers to this question. Both
are known to be incomputable. In this paper, we quantify this using the
arithmetical hierarchy, and prove upper and corresponding lower bounds for
incomputability. We show that AIXI is not limit computable, thus it cannot be
approximated using finite computation. Our main result is a limit-computable
{\epsilon}-optimal version of AIXI with infinite horizon that maximizes
expected rewards.
