Page 1 of 1

Explosivity metrics

Posted: September 18th, 2020, 9:11 am
by Moosey
based on some discussion on the discord

post/discuss metrics for measuring how explosive rules are here

here are some of mine
I wrote:moosey linear metric
> the average quantity of 16x16 soups you need to run before you find one such soup whose population is bounded above
moosey superlinear metric
> the average quantity of 16x16 soups you need to run before you find one such soup whose population does not eventually dominate all functions of the form f(x) = ax+b for constant, finite a and b
pros of these metrics:
- not relative
- tba
cons of these metrics
- not good for ltl rules or other rules where small soups don't explode. for instance, theoretically large enough life soups would spawn explosive 0E0P metacells but this would only happen for absurdly large soup size. This is why life's mlm and mslm are both barely above one (mslm is almost exactly one)

Re: Explosivity metrics

Posted: September 19th, 2020, 1:09 pm
by 400spartans
I think I remember posting something to the discord along the lines of "smallest n such that 50% of n by n soups explode." It has the benefit of distinguishing between rules that explode at different scales, but it's still kinda hard to confirm without checking a lot of soups. It's also a discrete metric, and the definition of explode is a bit vague.

The value of this metric for normal CGoL is probably something between 2^1000000 and 2^100000000 (explosive 0E0P metacell + sufficient empty space)

Re: Explosivity metrics

Posted: September 19th, 2020, 3:28 pm
by MathAndCode
I think that there are multiple factors that should be considered with judging a rule. You are correct that one should be how long the chaos lasts for. If most random soups result in expanding chaos that eventually consumes the entire screen leaving no distinct objects, then the rule is not interesting. One example is B34S346. On the other extreme, if a rule results in everything decaying to small still lives and possibly small low-period oscillators within a few generations, then the rule is not interesting. One example is B47S37. In order to be interesting, a rule must have small patterns that generate long-lasting chaos but not unlimited chaos. B3S23 (ConwayLife) is one example; small patterns, like the R-pentomino, can last for a long time but eventually die down.
However, there is at least one other factor that must be considered: How much does how chaotic a region is depend on how chaotic it was some number of generations earlier? In ConwayLife, some small patterns, like the R-pentomino, can create chaos that expands well past their original bounding box, while others, such as the phi spark, die relatively quickly. However, this is not always the case. For example, a random soup ran in B35B135 will likely create chaos that shrinks extremely slowly but eventually leaves nothing more than small still lives and small, low-period oscillators. This factor seems to be especially correlated with the existence of common spaceships. I can think of three reasons for this:
  1. The ability for chaos to spread: I shall define a region to be chaotic if at least some of its cells are neither staying in the same state nor oscillating at a low period. When a spaceship enters a previously empty region, that region becomes chaotic because cells that were previously staying in the same state are now changing to the other state. If chaos cannot spread, then regions that are not chaotic cannot become chaotic, so spaceships cannot enter regions that they were not previously in. Because spaceships, by their definition, must constantly be moving into cells that they did not previously occupy, spaceships must not exist.
  2. The existence of forward movement mechanisms: This is somewhat related to #1 but is not exactly the same. Instead, this is more focused on specific forward movement mechanisms. A good example is the switch engine. It moves forward and leaves chaos in its wake. A spaceship is merely a forward movement mechanism with the back part stabilized. One example of this is the B-heptomino. It has a forward movement mechanism and leaves chaos in its wake (which stabilizes into a block), but adding a P-pentomino to the back results in a LWSS.
  3. Collisions: If a spaceship collides with a still life, an oscillator, or another spaceship, it can create a new region of chaos far from the region of chaos that spawned the spaceship or any other regions of chaos besides the spaceship itself. For example, there are two ways to generate an R-pentomino by hitting a beehive with a glider. If a rule has one or more common spaceships, then these chaos-generating collisions become more likely, so where chaos is now is less dependent on where chaos was one or two hundred generations ago.