Will this be the fastest life engine possible? Definitely not! This problem is deeper than I'll ever know in my life time. I can only be certain that there are many more gems to be mined.
To find that next big leap we have to go beyond simply improving the the old way of doing things and challenge the most basic assumptions. For example, the change-list is a great idea but it still visits every cell that changes state for each generation. Is that really necessary?
The change-list helps because it avoids looking at every cell each generation. What if we can avoid even scanning the change-list? Or, at least, avoid scanning a big part of the change-list?
Anyone who watches a life simulation in action quickly discovers certain patterns that repeat themselves: blinkers, tumblers, gliders and many more are common enough to have been given names. If we can work at a higher level, at this abstract level of semantics, we won’t have to examine every cell. We can examine large patterns of cells and predict their next sequence of states far into the future. This could yield a dramatically faster life engine.
Adding this in a simple way isn't difficult to imagine. Other programmers have put recognizers into their simulators for the more common cases (such as the blinker) and we can fit this into Qlife too but the big win is to do this in a more general way. The problem to solve is how to recognize these patterns with enough efficiency that the overhead of recognizing them is small enough to make it work.
The goal is to reduce the change-list only to those items that can't be predicted. Uh, oh, I know where this is going. It sounds very much like the change-list is becoming just a means of encoding the results of a "life compressor." This compressor would be a mechanism that was simpler and cheaper than evaluating the entire life grid but it would trade away some accuracy. The change-list would, in effect, contain the codes that would correct for that lack of accuracy.
It's an interesting way to view the problem. I'll have to think about this some more.
I highly recommend finding the book, "The Recursive Universe." It's an old book and probably not easy to find but it does a wonderful job of describing Von Neumann's work on cellular automata and his quest for a self-replicating machine.
Back to the main page