I was failing miserably to explain this idea to someone a while back. Partly because I didn't have it in any order in my head but mostly because the other person was getting that look in their eyes which means "Abort! Abort!". So here's a (hopefully) better attempt to explain it so that I'm ready next time.
(Andre: This is the idea in Permutation City, but I don't actually think that Greg Egan explains it terribly well there - read his short stories. And should Andre have an é at the end?)
Firstly, if you're a dualist give up now. (And if, when you read `dualist', you're thinking of two people, back to back, with pistols then you probably are ).
Ok, if you're still with me I can create a cellular automaton in some Turing Machine with some set of rules and let it progress till I have a conscious life form in it which has deduced the existence of rice pudding and income tax. (Absolutely, this would take some time. But if you accept that it is possible then you accept that I could do it so assume that I have)
Now my Turing machine is executing this universe and I can half its speed and it makes no difference to the being in the universe; it doesn't perceive that anything is different. I can start doing lots of other calculations on the side and it still makes no difference so long as we calculate another iteration once in a while. So we can do anything in the middle and our life form is still happy, eating rice pudding.
Now we start generating sequential CA universes. Ignore the ruleset, just set each cell to a bit from a huge counter, over the whole size of the (I assume finite) universe. In the process we will, at some point, generate the next iteration of our rice pudding monster. Thus we are still generating iterations, just doing other stuff in between, thus our conscious rice pudding monster is unaffected. Right?
Now once we've generated every possible CA universe. What's left to do? You might think that the CA monster is now frozen. But what more could we do? We could calculate the `next' iteration of his universe, but it already exists in memory. Is the act of actually calculating magical? Or, in fact, is every possible conscious being `living' in our memory; their patterns finding themselves in the dust?
In fact, every possible rule of physics exists now. Any rule based progression is already there. Time is an illusion caused by the existence of memory. At each step, the entire universe (including all of the rice pudding monster's memories) exist fully formed (as does every other universe). Why should it be surprised that whatever laws of physics it believes in are precisely correct to allow it's existence? When everything exists, nothing is surprising.
(You should, of course, be putting yourself in the place of the rice pudding monster at the moment and wondering why you're so special that you're not just patterns in the dust.)