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.