I'm not criticising AIXI, I'm just pointing out that calling it "constant time" is about as wrong as you can get, in the world of time complexity. Especially for AIXI, but also (less so) for an approximation like AIXItl.

Further, you can show with information theory that limiting the number of hypothesis tested or the running time does not reduce generality so long as you test up to a certain amount for a problem domain (e.g. hypothesis sizes up to the maximum representable if the causally observable universe where converted into computium, and maximum number of steps equal to the number of possible combinatorial configurations of program state).

Of course as mentioned, this gives you constant factors equal to the size of the observable universe. No one said it was practical :)

"Constant time" is still wrong even in the approximations. Constant time means O(1). But your comment already refers to a running-time complexity dependence on several parameters of the input, such as the size of the observable universe.

Size of the observable universe is constant. And maximization by exhaustive search requires touching every possible state. So yes, it is O(1). This is explained in Marcus' Ph.D. thesis, I believe.

If he says so, I should admit I'm wrong, but maybe not just yet.

This way of thinking (size of the observable universe is constant) avoids the whole question of time complexity. To actually measure the time complexity of the algorithm, you need to consider inputs of different sizes. You could run exactly the same algorithm in a different universe (that is why it's called "universal" after all) and you'd get a different running time. The time complexity is then the relationship between the two running times and the universe sizes.