How are massive cellular automata simulated?

Question

Take the redstone from Minecraft as an example - it's basically a 15 state cellular automata with the following base rule:

Redstone -> Redstone, powered of level Max(neighbours)-1

and additional rules for various connected elements

Repeater, inactive -> Repeater, active, level 2 if its input is powered
Repeater, active, level 2 -> Repeater, active, level 1
Repeater, active, level 1 -> Repeater, inactive
Redstone, unpowered -> Redstone, powered if there is a neighbouring Repeater, level 1 or another source

(I've written more about how Minecraft stuff can be implemented using CAs: http://madflame991.blogspot.com/2011/10/cellular-automata-in-minecraft.html)

Now, my questions are: How would the game manage to update HUGE redstone contraptions? What data structure does it use? Is it really implemented as a cellular automata? If not, then what's your best guess?

P.S. I'm not asking anyone to take a peek at the actual source code, but just to speculate on how this technical thingie is achieved. ...and I'm posting this here, on SO, and not on gamedev because it's a CA question and not a gamedev related question.

Answer 1

Another possible approach to simulate mind-boggingly massive cellular automata (e.g. Game of Life in Game of Life) is to detect patterns (glider, glider generator, etc.) and to predict their future evolution and only compute the parts that are unknown (glider evolution).

Answer 2

Hashlife (1) can be what you are looking for by accelerating computations over really huge spaces.