Conway's Labyrinth

Overview

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.

Competition history

• ISEF 2014 Earth and Environmental Sciences · Entry CS085

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.