×

Tight bounds on periodic cell configurations in life. (English) Zbl 1002.92501

Summary: 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 \(K_n\) of oscillators of periods \(n= 58,59,60,\dots\) and uniformly bounded population, and an finite sequence \(D_n\) of oscillators of periods \(n= 58,59,60,\dots\) and diameter bounded by \(b\sqrt{\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.

MSC:

92B20 Neural networks for/in biological studies, artificial life and related topics
68Q80 Cellular automata (computational aspects)
PDF BibTeX XML Cite
Full Text: DOI Euclid EuDML EMIS

References:

[1] Bell D., ”Life search” (1994)
[2] Berlekamp E. R., Winning ways for your mathematical plays (1982) · Zbl 0485.00025
[3] Buckingham D. J., Byte 3 (12) pp 54– (1978)
[4] Buckingham D. J., ”My experience with B-heptominos in oscillators” (1996)
[5] Callahan P. B., ”Conway’s life miscellany web page” (1997)
[6] Gardner M., Wheels, life, and other mathematical amusements (1983) · Zbl 0537.00002
[7] Hensel A., ”Life pattern archive” (1995)
[8] Hickerson, D. 1997. [Hickerson 1997], Personal communication
[9] Leithner, D. 1997. [Leithner 1997], Personal communication
[10] McIntosh H. V., ”Linear cellular automata via de Bruijn diagrams” (1991)
[11] Moore E. F., Mathematical problems in the biological sciences pp 17– (1962)
[12] von Neumann J., Theory of self-reproducing automata (1966)
[13] Poundstone W., The recursive universe (1985) · Zbl 1209.91011
[14] Schroeppel, R. 1994. [Schroeppel 1994], Personal communication
[15] Silver, S. 1997. [Silver 1997], Personal communication
[16] Wakerly, J. F. 1994. Englewood Cliffs, NJ: Prentice-Hall. [Wakerly 1994]
[17] Wolfram S., Phys. D 10 (1) pp 1– (1984)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.