Introduction to the PSK PSK Search Recent Additions CA Archive CA Links Feedback Appreciated !
Take me higher...

Lagniappe #4

The Oscillator Problem for Conway's Life

Without question the most celebrated cellular automaton is John Conway's Game of Life, a favorite of recreational scientists for more than 25 years. Remarkably, new and exciting discoveries continue to be made about this paragon of parallel computational complexity. Our aim with this page is to advertise perhaps the most amazing recent breakthrough, achieved by the collective efforts of a small cadre of zealots who pool their resources via a private email forum known as the LifeList. The Oscillator Problem, quite simply, is to find finite configurations of arbitrary period for Conway's rule. Anyone who has played with Life's sensitive dependence on initial conditions knows the challenge of 'engineering' a prescribed outcome. Nevertheless, through a combination of random and algorithmic search methods, interactive visualization, and deductive reasoning, this problem is nearly solved.

Paul Callahan's page, one of the premiere sites of our Kitchen Sink, now includes a terrific article on the Oscillator Problem, with clickable animations of all the key constructions. As he explains, there is a general method for generating an oscillator with any period greater than 60. The title image above is a cell-age rendition of the canonical period 61 configuration. Many key ideas of the general construction were developed by David Buckingham over the past ten years. Callahan links an animated version of Buckingham's description of his work, written last fall.

Of course the enormous menagerie of Life creatures assembled over the past quarter century includes a multitude of blinkers with small periods; Callahan's page collects many of these. Toward the end of his article Buckingham notes that as of October 1996, there were 18 periods less than 61 with no representative oscillator. A half a year later, three of those cases have been found, and the list is down to 15:

19, 23, 27, 31, 33, 34, 37, 38, 39, 41, 43, 49, 51, 53, 57.

The most recent discovery, with period 17, is due to Dean Hickerson:

Of course each remaining period will most likely be more difficult to exhibit than the last, but some members of the LifeList are cautiously optimistic that all instances will one day be found. I am sure that new contributions from visitors to the Kitchen would be most welcome!

Take me higher...
Introduction to the PSK PSK Search Recent Additions CA Archive CA Links Feedback Appreciated !