Booth Id:
CS085
Category:
Earth and Environmental Sciences
Year:
2014
Finalist Names:
Lackas, Jessica
Abstract:
This project investigates an obvious similarity between the labyrinth-like patterns produced by the fully asynchronous version of John H. Conway's Game of Life on the one hand, and those formed by the solutions to the so called maximum-density-still-life problem on the other hand. It turns out that the asynchronous version can be interpreted as a variant of the minconflicts-algorithm, a heuristic to solve constraint satisfaction problems. At every step, this algorithm selects a variable and chooses a least conflicting value for it. Thus, it tries to solve conflicts locally, and in many cases is able to produce a global stationary configuration. With two minor changes, which do not change the underlying idea of this algorithm, the asynchronous updating and the steps of the min-conflicts-algorithm are exactly alike. This result can be generalized to the wider world of cellular automata. Therefore, any asynchronous updating of a cellular automaton is an attempt to find a stable configuration of this automaton and consequently of its synchronous counterpart at the same time.