I think, Tegmark does not talk about computations per se because the hypothesis is agnostic about what kind of computer our universe is. It could, for example, be a geometric computer in which the position of objects can be determined with infinite precision (i.e. using the real numbers). Such a computer would be strictly more powerful than a Turing machine or equivalent (i.e. all computational models that can be described and run inside a Turing machine). Enumerating the space of all formalisms (i.e. the domain of mathematics) is as agnostic as you can be.
That is, to me, a weird mixing of scales. The universe only seems complex to us because of the scale at which we experience it in terms of time and physical extent as well as the convoluted way our own systems of understanding developed and then were later mutated and stretched into different forms to be better suited, etc. By definition the universe itself can't really be more or less complex than anything. At least not anything we can experience.
The idea of a geometric computer is surprisingly close to things I've been considering recently, but 'position of objects can be determined with infinite precision' seems strange. It may be just that I don't understand what is fully meant when you say 'geometric computer' but I would expect 'position' would be mostly meaningless in that space except as an emergent/illusory 'property'... and I don't think arbitrary precision would necessarily be implied either.
The question, in my mind at least, is how to show that the quantum understanding leads, on the macro scale, to the emergent phenomena we observe and once thought unitary. That's a great degree of precision and division between entities to arise out of the nonlinear interactions of bunches of 'particles'. And given the scale on which such things emerged (the universal one), clearly a proper system of understanding would make the emergence of things like atoms, molecules, chemistry, astronomy, geologies, planets, solar systems, galaxies, stars, and all those things self-evident. But... save for a few exceptions (more all the time though which is encouraging!) we rarely even look at things en-masse. It's all well and good to know how 2 bodies interact under gravitation. But when your system falls apart with 3, and you really need to be able to toss in a trillion with dozens of other nonlinear relationships... It really ought to be more obvious, I would think, that we're missing something.
IIRC there are no arguments about computation or what underlying medium(s) are involved, it seems like a separate question.
These are actually related by Goedel's incompleteness theorems and the Curry-Howard isomorphism. Computation and mathematics are inextricably linked.
The Computable Universe is a necessary restriction on the mathematical universe hypothesis to avoid accepting inconsistent universes.