Yes I think that's right. If all cells exist 2 possibilities for the generation counter is not enough, but 3 possibilities is. For example this rule works:

Yes I think that's right. If all cells exist 2 possibilities for the generation counter is not enough, but 3 possibilities is. For example this rule works: 01 -- the 0 is behind 12 -- the 1 is behind 20 -- the 2 is behind If you have non existing cells the generation counter needs to be able to go arbitrarily large (which is why it does in my program): 000 888 1 7 2 6 3 5 4444444 Lets go back to the situation where all cells exist. In the game of life cells can only have 2 states (live or dead). In the asynchronous version they have 6 states: 2 for dead/alive * 3 for the generation counter. You could view the asynchronous version as another cellular automaton (with more possible states and different update rules). I think you can write a procedure that takes the rules of a synchronous cellular automaton and returns a new cellular automaton that is the asynchronous version of the original. So you could structure the program like this: 1) A function to convert an automaton to its asynchronous version 2) An asynchronous cellular automaton simulator. Instead of updating all cells in sync it updates randomly. Edit: it's not hard actually. If the original has n states then the new one has 3n^2 states. The update rules are straightforward, but you get a huge number of them. E.g. for the game of life the original automaton has 2^9 rules (one for every possible 3x3 grid), and the asynchronous version has 12^9 rules.