You may enjoy the science fiction book Permutation City
ftp://ftp.idsia.ch/pub/juergen/zuserechnenderraum.pdf
http://www.mathrix.org/zenil/ZuseCalculatingSpace-GermanZeni...
Read his book 'Our mathematical Universe', he explains there why these are actual separate multiverses.
I agree it's somewhat a matter of interpretation whether it's truly "multi" or a single entity. But if the domains are separate enough, it's probably best to think of them as different universes.
Thanks for the link.
EDIT: Nope guess not now I'm knee deep in this thing :P
So this theorem gives you a property of the result (the result is larger than some number) without you having to calculate the result (sum the numbers) explicitly.
The Hashlife algorithm mentioned in this thread is another case, basically it's an algorithm to prove certain "theorems" about the Game of Life and applying those theorems to speed it up.
I yet to have read this essay, but I had two thoughts:
1. Similar to Turing completeness, actual physical reality might not matter for the internal observer. All Turing-complete machines can calculate same things and observer from the inside of the machine cannot determine on what hardware the machine is implemented. Similarly, this can be case for observers within our universe (humans). So maybe there is, at a high enough level of abstraction, only one mathematically possible universe.
2. The mathematical theorems are shortcuts to computation. For example, I can add two numbers on a computer, or I can use a theorem, which will tell me only some property of the result, but avoids having to do the actual calculation. So if universe is just a computation, one could avoid actually computing it in certain cases by having a theorem that would tell them enough information they need. In other words, you don't actually need to simulate anything in order for objects in simulation to "exist". So there is no need for actual hardware on which the universe runs to exist.
Addendum: So I read the essay, and I disagree that the multiverse is necessary. As I already stated in point 1, it can be the case that all possible mathematical realities are the same at high enough level of abstraction.