- A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Classification of repeating patterns

For general discussion about Conway's Game of Life.

Classification of repeating patterns

Postby itaibn » December 6th, 2015, 3:45 pm

Inspired by this thread, I was thinking about how to classify all patterns that after enough time become entirely predictable. This most clearly includes oscillators and spaceships, but also includes more complicated patterns such as puffers, and wickstretchers and even breeders. I came up with a system that I think is very elegant:

A 2-dimensional pattern, also called an agar, is a pattern that is periodic in every direction as well as being periodic in time.

A 1-dimensional pattern, also called a moving wick, consists two agars separated by a linear pattern of finite thickness, and which is periodic in one direction, and such that after a finite amount of time it evolves it to some translation of itself. If the pattern does not move in time it may be called a wick. Note that unlike in the conventional GoL definition of a wick, the components of a wick do not need to interact with one another; for instance, a glider stream and the debris of a puffer are both 1-dimensional patterns according to this definition.

A 0-dimensional pattern is a pattern which after a certain number of steps evolves into some translation of itself, and such far enough away from some "center", the pattern consists entirely of a finite number agars and moving wicks. We say that the pattern is supported by these agars and wicks.

0-dimensional patterns include oscillators and spaceships, which is supported by one agar and zero wicks. Wickstretchers and gliderless puffers are also 0-dimensional patterns which are supported by one agar and one wick. 0-dimensional patterns also include supported spaceships and rakes such the 17/45c patterns that underly the caterpillar.

In fact, even breeders can be classified as 0-dimensional patterns. A classical glider-gun-producing breeder is a 0-dimensional pattern supported by two agars, the blank agars and the glider-filled agar, as well as two moving wicks, the array of glider guns produced by the breeder and the glider terminus.

Already this system seems very powerful, but we can extend it even further:

A (-1)-dimensional pattern, also called a reaction, is pattern which consists of a finite number of {0,1,2}-dimensional patterns, which can be extrapolated infinitely to the past without the components colliding with one another, and such after a finite amount of time the pattern evolves into another set of {0,1,2}-dimensional patterns which will never collide with one another.

Actually, these definitions as I have stated them are slightly flawed. My definition of a (-1)-dimensional pattern also includes in it 1-dimensional reactions, such as when two parallel moving wicks collide. These should be grouped in the same category as 0-dimensional patterns. Also, it's probably more sensible to re-index these as {0-3}-dimensional patterns rather than {(-1)-2}-dimensional patterns.
Posts: 11
Joined: October 31st, 2013, 8:45 am

Return to General Discussion

Who is online

Users browsing this forum: No registered users and 3 guests