Site Info

Authors
  • H.Koenig
  • Adam Goucher
  • Dave Greene

« Swimming with Switch Engines | Main | New c/5 diagonal technology »

2011 January 16

Open Problems
Is Life omniperiodic?

image
Nicolay's period-37 oscillator

image
Matthias' period-31 oscillator

A cellular automaton is said to be omniperiodic if, for every natural number n, there exists an oscillator of period n. Some cellular automata have already been proven omniperiodic, mainly by Dean Hickerson, by finding a set of components that can be composed to produce loops of arbitrarily length, and placing multiple signals in the loop at regular intervals.

In Life, this is not so easy. We do have a set of components, namely Herschel conduits, but they only facilitate periods of 62 or greater. To prove Life omniperiodic, we also require oscillators of all periods less than 62.

Nevertheless, there has been some recent progress, utilising software such as Nicolay Beluchenko's RandomAgar search. Amongst these new oscillators is a period-37 by Nicolay Beluchenko, and a period-31 by Matthias Merzenich. Matthias noted that both of these oscillators are capable of reflecting gliders by 90 degrees.

Oscillators of periods 19, 23, 34, 38, 41, 43, and 53 are yet to be found. A continually updated status page is available on Jason Summers' website.