The important issue he discusses is reducibility - the extent to which we can make algorithms which will forecast the outcome of applying a large number of further iterations without having to compute them all.
An obvious question: what if the "value" of a cell depends not only on the cells above it (known values) but also cells alongside and below it (which are unknown values based on the examples in the video) - can we still quickly calculate them? The answer is "yes": if the rules give rise to linear relationships (which simple rules usually will) they can be resolved by solving simultaneous equations or using linear programming.
The tantalising part, which was all too short, is the discussion about reducibility (6:15 - 6:52, then what reducibility means to him emotionally at 7:42 - 8:50). We know that Turing proved that there are problems which are irreducible in 1936 in his paper that, as a side effect, defined the "Turing Machine". However, I am 100% stone cold certain that he has underestimated reducibility: around 35 years ago I was lucky enough to speak to Stephen Wolfram for several minutes. I'd like another chance for the purpose of clearing this reducibility question up.
