If one could simulate a human being completely, at the level of fundamental physics, would the simulation be human in some sense? It's hard to argue otherwise without resorting to some kind of essentialism, but one obtains some disconcerting results if one follows through on such a functionalist metaphysics. If all that "matters" are fundamentally mathematical relationships, then there ceases to be any important difference between the actual and the possible. (Even if you aren't a mathematical Platonist, you can always find some collection of particles of dust to fit any required pattern. In Permutation City this is called the "logic of the dust" theory.)
In the 2050 world of Permutation City, nothing as unrealistic as physical level simulation is possible, but there are "Copies" of people. These are ad hoc simulations employing knowledge from all levels of biology — at the synapse and neurotransmitter level in the brain, but at much higher levels of abstraction for "less important" organs. These Copies are run in an environment simulated along similar lines, some of it in great detail, some of it just sketched in. Due to processing limitations they run at best at one-seventeenth of the rate of ordinary human beings and sometimes much more slowly, depending on the available processor power.
There is also something called the Autoverse, an extremely complex cellular automaton (a souped-up version of Conway's "Life") which produces a world broadly similar to ours but with different physics, chemistry, and biology. This is so computationally intensive that only simple micro-organisms have been discovered — created? — and they don't seem to evolve. As a result the Autoverse is considered more of a toy than a serious research proposition; it is just a hobby for freelance programmer Maria Deluca. Copies and the Autoverse are the technological innovations crucial to the plot, but Egan also has lots of other ideas about what the future might be like, socially as well as technologically.
Paul Durham is convinced by the "logic of the dust" theory mentioned above, and plans to run, just for a few minutes, a complex cellular automaton (Permutation City) started in a "Garden of Eden" configuration — one which isn't reachable from any other, and which therefore must have been the starting point of a simulation. This is set up to run Copies of Paul, Maria and sixteen rich Copies seeking immortality, and to expand in such a way as to provide them with effectively unlimited computing power. (In order to provide something interesting to watch, this automaton is also set up to simulate an entire Autoverse world, which is why Maria is involved.)
The idea is that the simulation need only run for a few minutes, at a slow-down of 250 to 1, and when stopped will continue ("running on the dust"), because it will be more plausible to its inhabitants that it have done so. I didn't understand the need for this elaborate set-up, but I guess it makes for a better story than "well, all possible worlds exist, and I'm going to tell you about one of them".
Part two is set entirely within the simulated Permutation City. Eventually the logic of the Autoverse (which has evolved intelligent beings who, I think rather implausibly, manage to think up a simpler explanation for the Autoverse than its original one) starts to erode the logic of the automaton simulating it, and things fall apart. I found this part was less engaging — if still interesting — and the actual ending unsatisfying. I guess it was never going to be easy ending a novel that could, without inconsistency, have had absolutely any ending (including ones where causality just goes completely haywire).
Permutation City is as good as Quarantine, and won't disappoint Egan fans. While I really enjoy the way Egan plays with philosophical ideas, I would really like to see him write a more "ordinary" science fiction novel. This would give him a chance to explore the wealth of other, less profoundly metaphysical ideas he has produced.