fairfolio
Saved Projects

Conway's Labyrinth

ISEF · 2014 Earth and Environmental Sciences

Lackas, Jessica

Is this your project?

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.

Working on something like this? See what's been done and what's still open.

Competition history

  • ISEF 2014 Earth and Environmental Sciences · Entry CS085 Affiliated fair in Germany

Resources

Related projects

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

Browse more like this

Report a problem

Source: Regeneron International Science and Engineering Fair

Save projects to your library

Sign in with Google to keep track of projects you find interesting, organized into folders. An account also raises your daily allowance for “Has this been done?”, and lets you create a key for the MCP server with a much higher limit than anonymous use. Browsing stays public.

Continue with Google