Suppose that we have an 10-by-10 lattice of 100 cells, and we have an update rule fu for every cell u. (These update rules might be the same or differ from cell to cell.) Suppose the system begins in...

Suppose that we have an 10-by-10 lattice of 100 cells, and we have an update rule fu for every cell u. (These update rules might be the same or differ from cell to cell.) Suppose the system begins in an initial configuration M0. Suppose we start the system at time t = 0 in configuration M0, and derive the configuration Mt at time t ≥ 1 by computing

Given M0 and the fu’s, we’d like to know what the long-run behavior of this system is: does it eventually converge or does it oscillate? Prove that, for a sufficiently large value of K, we have eventual convergence if and only if the following algorithm returns True. Also compute the smallest value of K for

which this algorithm is guaranteed to be correct.

• Start with M := M0 and t := 0.

• Repeat the following K times: update M to the next time step (that is, for each u compute the updated M′ (u) by evaluating fu on u’s neighbor cells in M).

• If M would be unchanged by one additional round of updates, return True. Else return False.