computing methuselahs

[ssaamm]

I've always wondered if there's a way to generate random patterns that last for a very long time, one after another, using some algorithm. I've made some observations about the average methuselah, but I just can't seem to establish something that they all have.

I have, however, made the steps I think one goes through:

1-explosion:
The parts of it grow outward chaotically. This occurs for much longer in methuselahs than in regular random patterns, though still only for a few generations.
2-diffusion:
The expanded parts die off partially, leaving a few unstable pieces scattered around
3-collision/reaction
The parts that are unstable go off in different ways and collide with each other and the resulting stable patterns for a very long time, resulting in explosion, branching, death, and all matter of unpredictability
4-death
The chaotic parts stabilize one by one, until the last one finishes, leaving a large clump of still lifes and oscillators, and plenty of gliders that go outward

[calcyman]

I've always wondered if there's a way to generate random patterns that last for a very long time, one after another, using some algorithm.

The following pseudocode will suffice:

Code: Select all

minT = 50000
maxT = 60000

for i = 1 to infinity
{
   originalpattern = GödelIntegerToPattern(i);
   pattern = originalpattern;

   for t = 1 to minT
   {
      pattern = AdvanceOneGeneration(pattern);
   }

   if Stabilised(pattern)
   {

   }
   else
   {

      for t = 1 to maxT-minT
      {
         pattern = AdvanceOneGeneration(pattern);
      }

      if Stabilised(pattern)
      {
         print originalpattern;
      }
   }
}

This will output all methuselahs with a lifespan between 50000 and 60000 generations.


It's undecidable to find the longest methuselah in a m*n box, so don't expect to be able to do that.

[Karatorian]

How is it undecidable to find the longest lifespan in an n x m box? There are only a finite (if large) number of possible configurations, so it would seem that you could in theory (if not in practice, due to a lack of computing power) simply run each one until it stabilizes.

Or is it that for some patterns, when it has stabilized is undecidable? If that's the case, I suppose it's probably got something to do with the fact that life is Turing complete and therefore subject to the halting problem (or something similar). However, I'm not exactly seeing how.

In any case, I think i know how it may be workable anyhow. Rather than run each pattern until it stabilizes (which could get you stuck on a problem pattern), you could run each one for a given number of ticks, then remove the patterns that stabilize and continue. If your stabilization detection produces no false positives (which I naively assume is possible, although I do have an possible implementation in mind), then eventually, you'll have life times for the normal patterns and only the problem patterns will be left in the pool.

Of course, knowing when you've reached that point would be undecidable. However, one could use a heuristic to decide when to stop and then examine the remaining patterns manually. (I also naively assume that manual examination can detect the problem patterns).

[calcyman]

Proving that an arbitrary pattern stabilises is equivalent to the Halting Problem: every Turing machine can be simulated by a Life pattern, and vice-versa.

Finding the longest-lived methuselah in a m*n box is thus equivalent to calculating the Busy Beaver function, which is uncomputable.

[Keiji]

In any case, I think i know how it may be workable anyhow.

What you suggest is actually something I had started implementing for a much faster way to evolve stabilizing patterns to completion and, as a result of that, to brute force pattern search. I never finished it though, due to lack of motivation.

The basic idea was to search the universe for known patterns and, rather than represent the universe as a grid of cells, represent it as a list of objects (with position and orientation), so it can jump many steps forward at once by substituting a pattern with its known future evolutions, and only have to revert an area to a grid of cells when unknown collisions occur to calculate the result of the collision.

As calcyman mentions though, the halting problem / busy beaver function problem makes completing an entire database (up to a given maximum bounding box) without manual intervention to bar certain patterns from being investigated impossible - patterns like primer could not be automatically detected as infinite growth.

However, completing a database on a toroidal universe would be possible due to its finite size. Of course, even trying to do that would still take a long time for reasonably sized universes, due to the sheer number of patterns that would need investigating.

There is still a way to run such a search even with the disadvantage of the HP - by keeping an ever-increasing number of universes running in parallel, removing the stabilizing universes from the active pool. That way, even though "problem patterns" would remain in the pool forever (or until they were removed manually), it would not stop an unbounded number of other universes from being discovered. Although the calculator would slow down as more problem patterns entered the pool, it would never stop identifying new patterns given enough time to run. In fact, the problem of slowing down can be compensated for (in part, if not in full) by assigning higher priority to run patterns of a low generation, and lower priority to patterns of a high generation.