23
Views
1
CrossRef citations to date
0
Altmetric
Original Articles

Tight Bounds on Periodic Cell Configurations in Life

&
Pages 221-241 | Published online: 03 Apr 2012
 

Abstract

Periodic configurations, or oscillators, occur in many cellular automata. In an oscillator, repeated applications of the automaton rules eventually restore the configuration to its initial state. This paper considers oscillators in Conway's Life; analogous techniques should apply to other rules. Three explicit methods are presented to construct oscillators in Life while guaranteeing certain complexity bounds, leading to the existence of

an infinite sequence Kn of oscillators of periods n = 58, 59, 60, … and uniformly bounded population, and

an infinite sequence Dn of oscillators of periods n = 58, 59, 60, … and diameter bounded by b√log n, where b is a uniform constant.

The proofs make use of the first explicit example of a stable glider reflector in Life, solving a longstanding open question about this cellular automaton.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.