Life with ordinals
1: There is a square grid of cells, and each can either be black or white.Many complex patterns arise out of these simple rules. There are oscillators, which repeat after a fixed time period. The simplest is called the blinker and is shown as follows: 0: 1: 2: (0) This keeps on repeating. However, it becomes far more complex if we allow ordinals. The first ordinal is ω and any square which is black infinitely many times in the natural number sequence is black.ω: ω+1: ω+2: ω+3: ω+4: ω+5: ω+6: ω+7: ω+8: (ω+6) ω*2+1: ... ω*3: ω*4: We can also consider patterns that are not oscillators. Basic spaceships such as the glider disappear instantly at ω. However, the Gosper glider gun is a different story. At ω it becomes an infinite diagonal stream headed by a mass of black cells where the actual gun was. This makes it more difficult to analyse. I have still not found a pattern that stabilises at ω2 or beyond. I have, however, found a class of hypothetical patterns, known as ω-spaceships. At ω they would repeat the original pattern but shifted by a few cells. These will take up to at least ω2 to stabilise. However, none are known as of yet. If you do find one, let me know. You could technically go further but it would seem completely intractable until a pattern stabilising at at least ω2. How large is it possible to get to? I conjecture strongly that the ordinal of any pattern is countable, although I do not have a proof as of yet. I also conjecture (but not as strongly) that all patterns have an ordinal below the Church-Kleene ordinal (the ordinal that, in the fast-growing hierarchy, matches the Busy Beaver function), due to Life simulating a universal Turing machine. My third conjecture is that all ordinals below the Church-Kleene ordinal (or ω1, in case my second conjecture is false) can be achieved or surpassed by a pattern.
Related entries Life | ||
Home • Contact |