5
$\begingroup$

Is there any relationship between the bounding box and the period of an oscillator in the Conway's Game of Life?

In particular I am interested in this case: what is the maximum period for an oscillator contained in a bounding box of area $A$?

  • 0
    @Matt Hello, how much is small vs large? I am thinking of boxes about 150x150.2012-04-21

1 Answers 1

2

The only way to be sure what types of patterns exist at some given size is to try them all. This is impractical above extremely small sizes, and at larger sizes, it is theoretically undecidable even to determine whether a pattern is an oscillator. In practice, people use a combination of computer searches and ingenuity to create oscillators or other interesting patterns.

Some examples of small oscillators can be found here: periods 10-25, periods 26-50, periods 52-168.

To get a high-period oscillator in a small bounding box, you can combine several smaller oscillators having relatively prime periods. Or you could take another approach, like adding an eater to turn this period 149730 gun into an oscillator.

If you have a lot more space, you can implement a Turing machine and then write a Turing machine program to count up to some large number before getting back to the initial state, achieving a periodicity which is exponential in the bounding box size. Since only exponentially many patterns exist, there cannot be a super-exponential period.

  • 0
    Clarification: It's only undecidable if the pattern is allowed to (temporarily) extend beyond its bounding box, so the claim of undecidability depends on whether your bounding box is for the first frame or for all frames. The lack of super-exponential period on the other hand is for the case where all frames are bounded.2012-11-30