because the runtime complexity of AIXI is astronomically larger than the universe is.

'Astronomically'? That's the first time I've seen that superlative inadequate for the job.

AIXI is computable in the mathematical sense of being written as a computer program that will provably halt in finitely many steps

AIXI's decision procedure is not computable (but AIXItl's is). (Link)

Yes, I think the term in computational complexity theory is tractability, which is the practical subset of computability.

AIXI is interesting just from a philosophical perspective, but even in the practical sense it has utility in showing what the ultimate limit is, and starting there you can find approximations and optimizations that move you into the land of the tractable.

For an example analogy, in computer graphics we have full blown particle ray tracing as the most accurate theory at the limits, and starting with that and then speeding it up with approximations that minimize the loss of accuracy is a good strategy.

The monte carlo approximation to AI is tractable and it can play small games (fairly well?).

For a more practical AGI design on a limited budget, its probably best to use hierarchical approximate simulation, more along the lines of what the mammalian cortex appears to do.