Game of Life referenced in "intelligent design" paper

[pcallahan]

I was chagrined to find Game of Life used in this paper by Winston Ewert, William Dembski, and Robert J. Marks, II purporting to show a metric that could "differentiate patterns designed by programmers from those originating by chance." This sort of claim is one of the rallying cries of the "intelligent design" movement, particularly those offering supposed mathematical arguments against evolution.

But without politicizing this, I think it is safe to say the authors' method is insufficient to accomplish their goal. Considering it's a published paper it might be worth publishing a refutation. Their measure is based on "ASC", which seems to me to be no more than a measure of pattern compressibility: the difference between number of bits in a direct representation of a pattern and the number of bits in a compressed form (using an ad hoc language provided in the paper).

The paper provides numbers for a few specific examples, but I'm not sure it gives enough detail to reproduce them. On a second reading, I think it's not that hard and might be worth a shot. One operator they provide is effectively "run the pattern for n generations." I believe that small infinite growth patterns provide a way to generate arbitrarily compressible patterns this way. Just compare the representation of "run P for n generations" with the resulting pattern (a million steps into a glider producing switch engine for instance). Even Methuselahs might work for this, starting small and generating something big.

Stable ash fields are also fairly compressible relative to size, just owing to their sparsity. While it is not hard to tell by eye that such a pattern is not designed but "originating by chance" I do not think it could be distinguished from a designed pattern on compressibility criteria alone.

I would be interested in any experts here at least taking a look at the paper. Whatever you think of the ultimate aim of the authors, I believe it fails as a research result (disagreement welcome of course). If so, it should not be left to stand in the peer-reviewed literature without comment.

Oh, one other funny thing. Literally the last sentence of the paper is incorrect.

Consequently there is a finite number of interesting patterns for a given number of living cells, and we can number them.

At least, if I understand the 35-glider result , a pattern with 175 cells could be anything that's glider constructible (though one glider would need to be extremely far away and it would take exponential time to complete the synthesis). This claim is in no way crucial to the paper, but it suggests a rudimentary understanding in my view. (Update: Rereading I see that they make this claim relative to largest number of generations used in a ⊕ operation. Fair enough, but the number could be made quite large with a small representation, e.g. using repeated squaring.)

Taking the paper on its own terms, I should probably address this statement:

We have demonstrated the ability to describe functional Game of Life pattern using a mathematical formulation. This allows us in principle to compress Game of Life patterns which exhibit some functionality. Thus, ASC has the ability to measure meaningful functionality

Their compression scheme makes an attempt to capture "meaningful functionality" by providing expressions for objects like "the smallest oscillator of period 32." However, in the interest of completeness, it includes other operators that may really be more useful for producing a compressed pattern.

They in no way demonstrate that the description in terms of "meaningful functionality" is the smallest description. I suspect in most cases it is not. The other problem is that their notation only helps with patterns exhibiting periodicity. It is unclear how it would produce a small description for "binary ripple adder" or "toggle flip flop" (realized quite naturally by the snake bit). Whether by intent or misunderstanding, they are conflating "maximum compressibility" with "maximum compressibility in terms of meaningful function". Whatever the latter entails, it is not the same as the former.

[dvgrn]

I was chagrined to find Game of Life used in this paper by Winston Ewert, William Dembski, and Robert J. Marks, II purporting to show a metric that could "differentiate patterns designed by programmers from those originating by chance." This sort of claim is one of the rallying cries of the "intelligent design" movement, particularly those offering supposed mathematical arguments against evolution.

But without politicizing this, I think it is safe to say the authors' method is insufficient to accomplish their goal. Considering it's a published paper it might be worth publishing a refutation. Their measure is based on "ASC", which seems to me to be no more than a measure of pattern compressibility: the difference between number of bits in a direct representation of a pattern and the number of bits in a compressed form (using an ad hoc language provided in the paper).

Hmm, I'm not entirely sure that it makes sense to try to refute that paper. Sometimes publishing a rebuttal just has the effect of giving the original paper some credibility that it wouldn't otherwise have.

Intelligent Design proponents have gotten very good at making mountains out of molehills. It would be easy for someone to produce a response criticizing the real or imagined weaknesses and biases of the rebuttal -- thus purporting to show that "The Controversy" is still a controversy, rather than just a series of profound mathematical misunderstandings obscured by a lot of confusing noise.

Stable ash fields are also fairly compressible relative to size, just owing to their sparsity. While it is not hard to tell by eye that such a pattern is not designed but "originating by chance" I do not think it could be distinguished from a designed pattern on compressibility criteria alone.

It's also fairly straightforward, though a bit tedious, to design an apparent ash field that can't be distinguished by eye or by any chosen-in-advance statistical test from one originating by chance ... but if a single cell or glider or other active pattern is included in the right place, the ash field eventually resolves into a glider construction of something extraordinarily unlikely -- a high-period oscillator or quadratic growth pattern or glider-constructible spaceship or what have you.

So I think it's probably possible to come up with counterexamples in all possible directions: Life patterns with a high ASC score that were not designed, maybe like the 9307907th generation of this symmetric soup... and Life patterns with a low ASC score that were designed -- maybe like a sidesnagger or a spacefiller? I'm not clear what example to choose, because it seems to be necessary to apply quite a bit of intelligence to come up with a "best" representation of a given pattern, before the ASC calculation can be done.

The definition of ASC is fluid enough that it could be adjusted, with hindsight, to give a better result for any specific counterexample we might come up with. The paper hints at this with regard to an array of a billion blinkers, for example, which would need a "looping or REPEAT command" that's not currently present in Table II. I think we'd always be able to come up with more counterexamples for the adjusted system, but it's not clear that jumping into this particular rabbit hole is really a very interesting exercise.

I would be interested in any experts here at least taking a look at the paper. Whatever you think of the ultimate aim of the authors, I believe it fails as a research result (disagreement welcome of course). If so, it should not be left to stand in the peer-reviewed literature without comment.

The Introduction section of the paper says that the ASC metric, "Algorithmic Specified Complexity", is a variant of specified complexity introduced in William Dembski's 1998 book The Design Inference: Eliminating Chance through Small Probabilities. This is fairly old stuff. Dembski's earlier work seems to have used a slightly different acronym, CSI, "complex specified information", but the "C" and the "S" mean the same thing as in ASC. An associated Law of Conservation of Information was thoroughly rebutted in 2002, for example:

The actual validity and utility of Dembski's proposed law are uncertain; it is neither widely used by the scientific community nor cited in mainstream scientific literature. A 2002 essay by Erik Tellgren provided a mathematical rebuttal of Dembski's law and concludes that it is "mathematically unsubstantiated."

There are a lot of similar rebuttals and responses in the Reception section of the Design Inference article on Wikipedia. At least on a first reading, I can't seem to find anything new and interesting in that 2015 paper that would justify a new response.

[pcallahan]

Hmm, I'm not entirely sure that it makes sense to try to refute that paper. Sometimes publishing a rebuttal just has the effect of giving the original paper some credibility that it wouldn't otherwise have.

You may be right. It seems like a judgment call. Letting it stand unchallenged (and making its way into further citations) runs the risk of someone claiming "Conway's Game of Life disproves evolution." I have to admit this kind of thing rankles. There are few enough publications at all about cellular automata, and most are just repeats of old themes from a naive start. This is even worse in that it ties a subject I find intriguing to one that as far as I can tell makes no sense at all.

As I said, I think it did help me understand the specific fallacy they are falling prey to (generously assuming honest error). They seem to assume that a description in terms of "meaningful function" is minimal. I think that is often incorrect both in terms of CGOL and other things. The description of "How to Build It" may often be significantly more concise than "What It Does." (An example I like right now from both CGOL and digital design: a binary ripple counter is surely easier to describe as a series of identical toggle flip-flops than as its "meaningful" specification as a binary counter, and obviously there are a lot of examples).

I think, though it may not be worth an attempt at a peer reviewed publication, it may be worth reverse-engineering their calculation of ASC to the point where it looks close enough to their tabular results and then demonstrating a class of "chance" patterns with high ASC. I realize that Dembski has been pounding this drum for over 20 years but I wish he'd stay away from CGOL. (I think an entire randomly defined class with high probability of being indistinguishable from "design" makes it very hard to repair the metric as a single counterexample would.)

It's also fairly straightforward, though a bit tedious, to design an apparent ash field that can't be distinguished by eye or by any chosen-in-advance statistical test from one originating by chance ... but if a single cell or glider or other active pattern is included in the right place, the ash field eventually resolves into a glider construction of something extraordinarily unlikely -- a high-period oscillator or quadratic growth pattern or glider-constructible spaceship or what have you.

On a happier note, can you link to an example of this or ideally script to generate them? (I think I have seen this with objects with known turning properties, but they are still visually distinguishable from a natural ash field.)

[dvgrn]

Conway's Life happens to be a rule where it's very difficult for large-scale functional structures to evolve -- "functional" meaning we're excluding things like puffer debris or methuselah ash that just sits there. You could say that a line puffer "evolves" a repetitive orbit, for example, but that's about as interesting as evolved structures get in Life. Patterns like the primers have interesting output, but they just do what they were designed to do, they don't evolve naturally to do something different.

This is true at least until you build a self-replicator that supports "safe" mutations of its program. Imagine something 0E0P-metacell-like, but that uses presence or absence of neighbors to add pseudo-random mutations to the part of its program code that tells it which direction to attempt the next replication cycle. That might allow for all kinds of interesting evolved behavior, while avoiding any possibility of catastrophic chaotic failures. But that just comes from Life supporting universal computation and construction; we could build an equivalent structure in any other universal rule, and get precisely the same behavior.

So ultimately the fact that Life can do this isn't too interesting -- and in fact, if we want to get to the interesting stuff, we'll skip the Life self-replicator stage and simulate the higher-level behavior directly, millions of times faster! At which point we might have invented a system vaguely along the lines Tierra or Avida or other more recent Artificial Life models.

-- I guess Catagolue has by far the biggest and most impressive collection of things that legitimately evolved from random initial conditions. There are certainly some impressive oscillators and still lifes in there, but no guns yet except for the "almost-natural" period 156 glider gun.

Conway's Life might be the wrong rule to look at
In B3/S23 it's perfectly true that a lot of big engineered patterns are very delicately balanced, and it's generally very easy to tell that they were (intelligently? or just obsessively?) designed rather than evolved. Any small mutation will destroy the entire pattern. So in some ways, Conway's Life is an ID advocate's dream rule: you really can tell (usually) when a pattern has a designer.

This is not true for all CA rules, though. ZombieLife comes to mind as a rule with impressively large and apparently very complex spaceships, where mutations usually spontaneously heal themselves, or occasionally settle into a new orbit and make another similarly robust spaceship. Only a few cells at the front of the ship are usually vulnerable to mutations. An ASC-type approach doesn't seem very useful for something like this ZombieLife ship, for example:

Code: Select all

x = 464, y = 59, rule = B3-nqy4aqz5cn6n8/S2-i3-a4inqz7c8
300bo$300bo2$297b2obo$298bo2bo2$142b2o10b2o3b2o137bobo$141bob2o8bobo3b
obo65b3o9b3o56b2o$140b3o9b2o7b2o63bo3bo7bo3bo42b3o$141bo5bo5bobo2b2obo
64b2ob2o7b2ob2o41bo2bo26b3obo$143bobobo6b2o2bobo71b2ob2o47bo3bo25b2obo
84b3o$142bobo12b2o74bobo48bo2bo25bo2b2o68bo13bo3bo$141bo15b2obo71b2ob
2o48b3o24bobo26b3o41b3o11bo4bo$140bo12b2o3b4o22bo41b2o13b2o70bobo2bo
22bo3bo38bo2b2o10bo3b2o$3bo2bo13bo2bo89bo26bo3bo2b2o3bobo3bob3o20b6o
33b2o2bo15bo71bo4b2o20bo3b2o36bo2b2o11bo3b2o$2b2o2bo2b2o5b2o2bo2b2o88b
o26b2o2bobobo2b2o5b2obo20bo2b3o33bobobob2obobo3bobob2o73bo2bobo17b3o5b
2o37bo14b4o$bobo3bo11bo3bobo88bo27b3ob3o3bo2bo2b3o21b4obo31b3o8b3o3b3o
15b2o61bo2bo17bo7b3o53bo42b2o10b3o$2o3bo3b2o5b2o3bo3b2o85b2obo27b4o5bo
2bo29bobobo28b3o5bo26bo2bo2bo57b3o18b3o3bo2bo18b3o4bo71b3o8bo2bo$2o2b
3o13b3o2b2o86bobo37b3o30bo2bo27b2ob3obo3b5o3b3o14bo2bobo37b3o3b3o41bo
4b2ob2o9bo2bo2b2ob2o6b2o42b2o28bobo2b2o$2obo5bo7bo5bob2o87bo73b2o3b2o
26b4obo2b2obo3bobob2o11b2obo2bo36b3o3b3o40bo4b2o3b2o8bo2bo6b2o5b3o37b
2ob2ob2o13b2o11b2ob2ob2o$2b3o2b4o5b4o2b3o157b2ob2obo3bobo31bo2bo12bo
11b2obo37bo3bobo3bo45b2ob2o9b2ob2ob5o45bo5bo2bo12b2o13bo2b2o$2b3o2bo2b
o5bo2bo2b3o157bo3bo4bo19b3o13bo13b2o12bo3bo3b2o30b2ob2ob2ob2o15b2o3b2o
39bo3bo49bo2b2obo2bo13bo$7bobo7bobo163b3o6bobo16bobo18b2ob2o19b2obo3bo
bo53b2obo3bob2o43b2o47bo2bo4bo25b7o$7b2o9b2o164bo8b2o16bobo9bo9bobo21b
3o5bo53b2o7b2o42b3o48b3o21bo3bo3bo2b2o2bo$57b3o3b3o152b2obo10b2ob2o26b
obo24b3o26b2obo3bob2o21b2ob2o31b2o57bob2o4b4o2b3o$56bo2bo2bo3bo144bobo
4b2o6b2ob2o7b2ob2o20b2o25b3o8b2ob2o15b2o3b2o22b2o3b2o20b2ob2ob2o2bobo
39b3o15bo7bob2o$56bo3bob2ob2o109b2o32b2obo12bo3bo7bo3bo46bo5b3o3bo3bo
45b2ob2o20bo4bobo6bo40bo15bo8b3o$56b3o6bo110b2o33b2o14b3o9b3o47b2o4bo
3bob4o69b5ob2ob2o2bobo18b3o3b3o10bo2bo26bo$66b2o160bo61bo4bo3b2ob3o68b
ob3o9b2o19b3o3b3o11b3o15bo$7b2o9b2o46bo2bo228bob2o72b2o31bo3bobo3bo$7b
obo7bobo41bo4bo3bo32bo26bo11bo22b3o97bobo22bo6bo55b3o19b3o29b2ob2ob2ob
2o3bo$2b3o2bo2bo5bo2bo2b3o36b4obo3bo30b4o24b3o9b3o20bo2bo23bo3bo13b3o
50b3o25b2o7bo4bo48bo2bo18bobo23b3o16bobo$2b3o2b4o5b4o2b3o39bobob3o34bo
23bobo2b2ob2o2bobo19b4o21bobo5bo3b2o7bo35bo16bo2bo25b3o2bo2bo5bo47bo2b
o17bo25b2o2bo14bo3bo$2obo5bo7bo5bob2o38b2o36bobo29bobo12b2o11bo2b2o16b
o2bo2bobobobo3bob2o6bo3bo7b4o18b2o16b2obo28b3o7b2o48b3o18b2o22b2obo2bo
13b2ob2o$2o2b3o13b3o2b2o37b3o37b2o23bobo2b2ob2o2bobo4bobobo11bo5b2o4bo
9bo13bo9bo9b4o3bo15b2o2b2o13bo32bo103bo3b5o2b2ob2ob2o$2o3bo3b2o5b2o3bo
3b2o37b2o39bo23b3o9b3o3bo5bo8b2ob2o3b3o2b2o7bob2o3bo3bo8bo7bo3bo27bobo
bo12bo2bo132b2o3b2ob2o4bobo3bo35b2o$bobo3bo11bo3bobo79b2o23bo11bo4b2ob
4o13bo2bo4bo9bo3b2o5b6o2bo9b2o6b2o4b2o15b4o3b2o3b2o3bo133b2o3b2o4b4o3b
3o35b2o2bo$2b2o2bo2b2o5b2o2bo2b2o78b2o2b2o23bobo3bobo9b2o15b2o3b2o2bo
5b3o2b2o9b4o2bo16bo3b2o2bo16bo3b2obo3bob2o2b4o22b2ob2o7b2ob2o74b3o12b
2o3bo7b3o3b3o14bo19b2o4bo$3bo2bo13bo2bo81b3o24b3o3b3o26bobo3b2o7bo3bo
15b2o10bo7b2o4bob2o18b2o7b2o3bo24bo3bo7bo3bo74bobo12bobob2o18b2ob2o6bo
bo19bo4bo$106bo63bo3bo2bo5bo2bo25bo2bo4bobobo5b2o18b2obo3bob2o29b3o9b
3o53bo21bobo12bo2b2o22b2o4b3ob3o18b5o$132b3o3b3o24b3o2bo4b3o7bo26bo2bo
14b2o20b2o3b2o31b3o9b3o52b3o21bo14b3o20b3o6bo3bo$132bobo3bobo24bo2bo5b
obo35b2o15bo127bob2o59bo7bo6bo4b2o11bo2b2o$130bo11bo22b2o4b2o3bo50b2o
25bobo54b2o3b2o5b2o3b2o25b2o2bo60b2o7b3obo4b2ob2o8b2ob2ob2o$129b3o9b3o
25bobo3bo78b3o53bobo3bobo3bobo3bobo23b3ob2o56bo4bo2bo6b3o4bo2bo9bobo2b
2o$129bobo2b2ob2o2bobo23b2o3b3o134bo21bo22bobob2o10b3o46b3o2bo16bo9bo
2bo$135bobo103bo7b3o2b3o53bobo5bo3bo5bobo22bo2bo2bo11b2o6b2o41b2o3bo
11b2o11b3o$129bobo2b2ob2o2bobo95b3o6b2obo2bobo54b2o5b2ob2o5b2o24bo24bo
47bo11bo$129b3o9b3o95bo7bo2b2o67bobo33bo2bo4bo58b2o3bo$130bo11bo95b2ob
o5b4o6b2o54bobo2b2ob2o2bobo27b3o4b2o61b2o$238b3ob2ob2o3bo6bob2o52b3o9b
3o34b2o57bo2b2o$242bo6b2o8b2o160bo$241b2o7bob2o3bob2o52b3o9b3o95bo$
242bo6b2ob2o3b2o54bobo2b2ob2o2bobo$242bob4obo69bobo$244bob3o62b2o5b2ob
2o5b2o$241b2obo2bo62bobo5bo3bo5bobo$242b3o64bo21bo$243bo66bobo3bobo3bo
bo3bobo$311b2o3b2o5b2o3b2o!

... unless whoever is doing the ASC encoding figures out that it all comes from this small seed, I suppose:

Code: Select all

x = 9, y = 26, rule = B3-nqy4aqz5cn6n8/S2-i3-a4inqz7c8
6b2o$7b2o$6b2o2$5b3o$7bo$5b3o12$bo$2bo$2bo$3o2$b2o$2b2o$b2o!

What might be other good examples of a lot of apparent complexity spontaneously appearing from simple initial conditions? Are there cases where the generating seed is much harder to find than with these ZombieLife spaceships? And would these make good counterexamples for this ASC approach, or am I just going off on a tangent here?

(Or both. Could be both, I suppose.)

[dvgrn]

On a happier note, can you link to an example of this or ideally script to generate them? (I think I have seen this with objects with known turning properties, but they are still visually distinguishable from a natural ash field.)

Well, we usually use our old familiar boats and eaters and toads and so on to do turns with, just because they're familiar. But there are hundreds of thousands of random-looking constellations inside 20x20 that can manage a one-time glider turn equally well.

There aren't any automatic generators for this kind of thing, though there is a GOL-destroy search program by simeks that could probably be adapted to assist. It's definitely more of an art than a science. It doesn't take long to throw together something like this with the Seeds of Destruction Game, though:

Code: Select all

x = 143, y = 122, rule = B3/S23
62bo$61bobo$61bobo$62bo2$57b2o7b2o$56bo2bo5bo2bo$57b2o7b2o2$62bo40b3o$
61bobo$61bobo37bo5bo$62bo38bo5bo$101bo5bo$78bo$77bobo23b3o$78bobo$79b
2o$84b2o$60bo22bo2bo$59bobo21bo2bo$59b2o23b2o4$56bo45bo$55bobo13b2o28b
obo$56b2o13b2o8b2o18b2o$82bo31b2o$82bobo28bo2bo$56bo26b2o28bo2bo$55bob
o56b2o$56b2o63b2o$109bo11b2o$79b2o27bobo$79b2o18b2o7bobo$99b2o8bo4$61b
2o39bo$61b2o38bobo$97b2o3b2o$46bo4bo45b2o7b2o$45bobo2bobo52bo2bo$46b2o
3b2o53bobo$71bo35bo$70bobo20b2o17b2o$30bo40bo21b2o16bobo$29bobo79b2o6b
o$9b2o19b2o28b2o56bobo$9b2o49b2o56bobo4b2o$119bo5bobo$107bo18bo$17b2o
87bobo$16bo2bo52b2o33b2o$16bobo35b2o15bo2bo45b2o$17bo35bo2bo15b2o45bo
2bo$45b2o6bo2bo30b2o31b2o$2o42bo2bo6b2o31b2o$2o42bo2bo60b2o$45b2o61b2o
2$91b2o$4b2o73b2o10b2o21b2o$4b2o73b2o33b2o$73bo$43bo28bobo$37bo4bobo
27bobo$36bobo3b2o29bo$37bobo$38b2o6b2o$45bobo$15b2o29bo91bo$14bobo109b
2o9bobo$15bo63b2o45b2o9b2o$79b2o$97b2o$97b2o$74b2o54b2o$74b2o54b2o5$
32bo108b2o$31bobo107b2o$23bo7bobo76b2o$22bobo7bo39b3o35b2o$22bobo$23bo
3b2o7b2o32bo5bo60b2o$26bo2bo5bo2bo31bo5bo60b2o$27b2o7b2o32bo5bo$107bo$
32bo26bo12b3o32bo$31bobo24bobo46bo$31bobo24bobo37b2o$32bo26bo38b2o3b3o
3b3o2$54b2o7b2o9b3o30bo$53bo2bo5bo2bo41bo$54b2o7b2o7bo5bo28bo$72bo5bo$
59bo12bo5bo$58bobo36b2o$58bobo13b3o19bobo$59bo36b2o$63b2o$63b2o5$77b2o
$76bo2bo$77bobo$78bo3$106b2o$106bobo$107bo!
#C [[ THUMBNAIL THUMBSIZE 2 ZOOM 4 HEIGHT 520 ]]

If you're an old hand with this kind of thing, you might certainly spot the signs that there's something fishy about this pattern. But if I said it was ash from a 16x16 Catagolue soup, I doubt anyone would give it a second glance.

It would be easy to replace one of the two identical pairs of boats with something else, swap out a few more of the two-block turners, and then add even more clutter to hide the remaining visible chains of turners. Then you'd have a _really_ tough time coming up with the pair of gliders that changes the above into a Highly Meaningful Pattern:

Code: Select all

x = 242, y = 165, rule = B3/S23
129bo$128bobo$128bobo$129bo2$124b2o7b2o$123bo2bo5bo2bo$124b2o7b2o2$
129bo40b3o$128bobo$128bobo37bo5bo$129bo38bo5bo$168bo5bo$145bo$144bobo
23b3o$145bobo$146b2o$151b2o$127bo22bo2bo$126bobo21bo2bo$126b2o23b2o4$
123bo45bo$122bobo13b2o28bobo$123b2o13b2o8b2o18b2o$149bo31b2o$149bobo
28bo2bo$123bo26b2o28bo2bo$122bobo56b2o$123b2o63b2o$176bo11b2o$146b2o
27bobo$146b2o18b2o7bobo$166b2o8bo4$128b2o39bo$128b2o38bobo$164b2o3b2o$
113bo4bo45b2o7b2o$112bobo2bobo52bo2bo$113b2o3b2o53bobo$138bo35bo$137bo
bo20b2o17b2o$97bo40bo21b2o16bobo$96bobo79b2o6bo$76b2o19b2o28b2o56bobo$
76b2o49b2o56bobo4b2o$186bo5bobo$174bo18bo$84b2o87bobo$83bo2bo52b2o33b
2o$83bobo35b2o15bo2bo45b2o$84bo35bo2bo15b2o45bo2bo$112b2o6bo2bo30b2o
31b2o$67b2o42bo2bo6b2o31b2o$67b2o42bo2bo60b2o$112b2o61b2o2$158b2o$71b
2o73b2o10b2o21b2o$71b2o73b2o33b2o$140bo$110bo28bobo$104bo4bobo27bobo$
103bobo3b2o29bo$104bobo$105b2o6b2o$112bobo$82b2o29bo91bo$81bobo109b2o
9bobo$82bo63b2o45b2o9b2o$146b2o$164b2o$164b2o$141b2o54b2o$141b2o54b2o
5$99bo108b2o$98bobo107b2o$90bo7bobo76b2o$89bobo7bo39b3o35b2o$89bobo$
90bo3b2o7b2o32bo5bo60b2o$93bo2bo5bo2bo31bo5bo60b2o$94b2o7b2o32bo5bo$
174bo$99bo26bo12b3o32bo$98bobo24bobo46bo$98bobo24bobo37b2o$99bo26bo38b
2o3b3o3b3o2$121b2o7b2o9b3o30bo$120bo2bo5bo2bo41bo$121b2o7b2o7bo5bo28bo
$139bo5bo$126bo12bo5bo$125bobo36b2o$125bobo13b3o19bobo$126bo36b2o$130b
2o$130b2o5$144b2o$143bo2bo$144bobo$145bo3$173b2o$173bobo$174bo13$239b
3o$239bo$240bo26$3o$2bo$bo!

[pcallahan]

I agree that Life is not a great platform for watching spontaneous evolution. There is still something very remarkable about the rare patterns that do exist just far enough out in the search space to make it both a challenge and a reward to search for them. Is something like the snail spaceship an example of emergence? It may never show up in a soup, but the mechanisms by which it operates aren't something the programmer coded in. Maybe we need to delineate different kinds of emergence.

For purposes of addressing Dembski (which I agree may not be a worthwhile goal) it probably doesn't help to move to a more congenial CA. One of his old standbys has been that people observing emergent behavior have really "smuggled" it into their rules, whatever way he wants to define that. So my thought (and probably a foolish one) is how to respond to the paper on its own terms.

When you cut through the thicket of needless mathematical formalism, the result can I think be summarized as saying that most oscillators (and spaceships, guns, puffers) take up more space to write out as a bitmap than as a certain equation they solve, written in the author's preferred notation. This seems true and unsurprising, at which point it becomes a tautological conclusion to identify the oscillators that are smaller to write out in full as "natural" (e.g. gliders) and those are smaller to write as equations as "designed."

There are a couple of problems with this. First, most of the spaceships identified as "complex designs" are in fact the result of searches. While these searches were not emergent, evolutionary processes, neither were they designs in the sense of applying known principles according to a plan. The solutions to the oscillator/spaceship equations obviously come out of a well-defined enumerative process, though it may be infeasible beyond a certain point to carry out. In some cases, high-ish period oscillators may emerge from soup. E.g. tumbler and pentadecathlon, which are conspicuous by their absence in the paper.

But what we can usually say is that if the smallest realization of a particular oscillator period requires a large bitmap, then it is unlikely to show up spontaneously in a soup. There's no reason why a particular one might not (and if Life were like your Zombies example, then it might be more common). In general though, the bigger the pattern, the less frequent you'd expect it all other things equal, though some big patterns may emerge (e.g., the trail of either switch engine stabilization). I am trying to think if there's any general principle here. A lot of it is just about CGOL. There can be rules in which large oscillators are a lot more frequent.

Tautologically speaking, rare patterns will occur with low probability, and if that is the result, I concur. If there's some other result, I'm struggling to get it.

My other problem is that while the notation suffices to capture oscillators and a few other types as equations, it doesn't capture any other patterns such as a prime number enumerator (for example) which is clearly designed. So the methodology really doesn't even capture the concept of "designer's intent" except in an extremely limited domain.

(Oh, and thanks for ash-field example. I'm not sure that design camouflaged as nature really refutes anything, but it is fun.)

But there are hundreds of thousands of random-looking constellations inside 20x20 that can manage a one-time glider turn equally well.

Oh, right. I remember doing searches for these kinds of reactions a while back (though if I recall correctly, I was hoping they would leave some debris behind for a later collision).

[pcallahan]

One other thing (and typical of creationist apologetics), Ewert, Dembski, Marks vastly underestimate the probability of Gosper's glider gun (their most prominent example of a pattern "designed by programmers") arising by chance. Though it is rather improbable, and we know it was designed because Bill Gosper claimed credit, there are many precursors other than the live cells being chosen randomly (even accounting for sparsity as the authors do, to their credit).

I did a quick survey and I believe that 24 out of 2^16 4x4 patterns eventually generate an unstabilized queen bee shuttle (verification welcome). That's quite a high frequency. Of course, you still need a stabilizer at one end for it to be half of a gun. I am curious now what's the smallest precursor (by bounding box) to a half-stabilized queen bee. Achim Flammenkamp's census shows two forms of stabilized queen bees both with 1/5.7*10^8 frequency. A ballpark estimate then might have a Gosper glider gun showing up around 1/10^18 or more frequently, which would certainly assign a higher probability than bounded in the paper (about 2^-192, no greater than 10^-57).

I can probably do a lot better if I have some idea of the probability of half-stabilized queen bees and the number of ways to get the empty space in between (other than starting with all empty cells).

This is probably not worth a peer-reviewed publication, but maybe I can write an invited article on an evolution blog. The nice thing about Game of Life is that when they make bogus probability estimates, they can be refuted very convincingly.

[dvgrn]

Achim Flammenkamp's census shows two forms of stabilized queen bees both with 1/5.7*10^8 frequency. A ballpark estimate then might have a Gosper glider gun showing up around 1/10^18 or more frequently, which would certainly assign a higher probability than bounded in the paper (about 2^-192, no greater than 10^-57).

You might get some useful ballpark data from the C1 xp30 census on Catagolue, and also the G1 xp30 census, though of course those only record queen bees stabilized on both sides. Maybe don't worry about the G1 census, since I think it discards boring soups in a way that may be confusing for statistics-making... don't quite remember the details.

I can probably do a lot better if I have some idea of the probability of half-stabilized queen bees and the number of ways to get the empty space in between (other than starting with all empty cells).

Hmm, I don't quite know where to start on the "ways to get the empty space" question. There are umpteen-cubed ways to do it by leaving scattered junk where a QB-generated beehive will interact with it. That somewhat extends the allowable elapsed time between the creation of the two half-stabilized beehives. But ultimately they'll still have to show up in a very restricted set of relative spacetime locations.

There are a big pile of ways for two queen bees to interact that do not produce gliders, so we should expect to see a large number of these in the C1 xp30 census before we see a Gosper glider gun. A glider gun is most likely to appear in the middle of a mess of ash, and the majority of guns that appear will probably hit something with their gliders that destroys the gun, rather than drilling a clean hole through the ash. A destroyed gun won't show up in a Catagolue census ... so assuming that each of the non-gun 2QB p30 oscillators is roughly equally likely to appear as a classic Gosper gun, and significantly less likely to be destroyed, they're very very likely to show up first in the census.

Code: Select all

#C one of dozens (hundreds?) of non-gun P30s,
#C   even if you don't count different stabilizations of the same QB position
x = 21, y = 25, rule = B3/S23
3b2o$3b2o8$2b3o$bo3bo$o5bo$2obob2o6$11bo$11bobo$12bobo$12bo2bo3b2o$12b
obo4b2o$11bobo$11bo!

So the main thing we know it the moment is that Catagolue's run so far of 2.2*10^13 C1 soups seems to be not anywhere near enough. We haven't even seen one 2QB oscillator yet, and we should probably be expecting to see dozens of them before an actual 2QB gun. It seems as if 10^18 might be too optimistic for the number of soups we'll have to run -- let alone the number of objects we'll have to census from soups. Catagolue has already counted very nearly 5*10^14 objects without getting into the 2QB zone at all.

[Kazyan]

This isn't particularly the point, but a two-queen-bee oscillator has indeed shown up, "Berger's p30". In fact, a second instance of it appeared recently. http://gol.hatsya.co.uk/object/xp30_w33 ... cx33/b3s23

[pcallahan]

Without doing an exhaustive survey, I did find one 5x5 precursor to a half-stabilized queen bee. Here it is with a block for the other half.

Code: Select all

x = 20, y = 5, rule = B3/S23
15b2obo$2o13bo2b2o$2o13b5o$15bobo$16b4o!

I can't combine two of them into a gun because the phase would be wrong. The way I found the half-stabilizer pattern was just to filter for 29-cell ash in a 24x27 bounding box and then inspect the results visually. That limits it to a single block stabilization, but still it is clearly pretty common.

Hmm, maybe I should just go ahead with the exhaustive 5x5 enumeration.

This isn't particularly the point, but a two-queen-bee oscillator has indeed shown up

Well, it is kind of the point. As Dave Greene pointed out, the two-queen-bee oscillator is a good proxy for the glider gun. It is nearly as "improbable" by anyone's metric except for the greater multiplicities and that the gun would usually get destroyed before being identified in soup (I guess if it also had a lucky eater or boat bit it could survive).

[dvgrn]

This isn't particularly the point, but a two-queen-bee oscillator has indeed shown up, "Berger's p30". In fact, a second instance of it appeared recently. http://gol.hatsya.co.uk/object/xp30_w33 ... cx33/b3s23

Thanks -- that really does seem fairly relevant! Sorry, I had forgotten that oscillators don't have 200 items per Catagolue page, like still lifes, so I was only looking at the first ten xp30s.

Two instances of Berger's p30 certainly seems to be saying that 2*10^13 soups or 5*10^14 objects is getting into the right ballpark where a glider gun might appear -- within a few orders of magnitude, anyway. So quite possibly a 1/10^18 frequency is about right.

[calcyman]

This isn't particularly the point, but a two-queen-bee oscillator has indeed shown up, "Berger's p30". In fact, a second instance of it appeared recently. http://gol.hatsya.co.uk/object/xp30_w33 ... cx33/b3s23

Thanks -- that really does seem fairly relevant! Sorry, I had forgotten that oscillators don't have 200 items per Catagolue page, like still lifes, so I was only looking at the first ten xp30s.

Two instances of Berger's p30 certainly seems to be saying that 2*10^13 soups or 5*10^14 objects is getting into the right ballpark where a glider gun might appear -- within a few orders of magnitude, anyway. So quite possibly a 1/10^18 frequency is about right.

Well, in both cases there happened to be the same small predecessor:

Code: Select all

x = 23, y = 27, rule = B3/S23
21b2o$21b2o8$15bo$14bobo$15b2o12$11bo$b2o8bobo$obo8b3o$2o11bo!

...but anyway, I think 10^18 is rather pessimistic. I'd be surprised if we don't have a GGG within 10^15 soups.

[dvgrn]

... I think 10^18 is rather pessimistic. I'd be surprised if we don't have a GGG within 10^15 soups.

Really -- 10^15? Only one-and-two-thirds orders of magnitude from where we are right now? I'll be surprised if we do have a GGG by 10^15 soups.

I'll even bet a LifeNews article (topic to be chosen by the winner, within reason!) that no GGG will appear quite that quickly. I'm expecting to see at least a couple hundred "flightless" dual-queen-bee pairings before the first Gosper glider gun appears on the scene. After all, so far we've only even seen one out of the fifteen variants that you can get just by retiming one of the queen bees in Berger's p30... and we've seen it twice, so there's a good chance that that variant has a lucky cheap seed, and the others are significantly rarer. Exactly how much rarer, we won't know until we collect a good pile of them.

... Now, what can we do to increase the popularity of apgsearch, so that 10^15 gets here a little more quickly?

P.S. Didn't Brice Due or someone publish a big stamp collection of alternate queen bee pairings, a while back? Or was that twin-bee pairings? At the moment all I can find is this discussion, which says there are "many" 2QB pairings but only one that makes gliders that can actually escape.

(If the "non-Gosper gun" shows up instead of a proper GGG, I will still cheerfully admit defeat, of course. That's a 3QB, so I feel pretty safe. And if the gods of probability see fit to play a joke on me on this point, no problem -- we'll have a nice glider-gun soup and a new LifeNews article...)

[Sphenocorona]

If the "non-Gosper gun" shows up instead of a proper GGG, I will still cheerfully admit defeat, of course. That's a 3QB, so I feel pretty safe.

Well, Tropylium's second p30 gun in that thread does have an advantage over the regular GGG in that it can be built up one component at a time, allowing a degree of leniency in timing which the GGG does not permit:

Code: Select all

x = 79, y = 37, rule = B3/S23
74b2o$74b2o4$74bo$73b3o$72bo3bo$71bob3obo$72b5o9$2bo4bo24bo4bo24bo4bo$
2ob4ob2o20b2ob4ob2o20b2ob4ob2o$2bo4bo24bo4bo24bo4bo5$44b3o27b3o$43bo3b
o25bo3bo$42bo5bo23bo5bo$42bo5bo23bo5bo$45bo29bo$43bo3bo25bo3bo$44b3o
27b3o$45bo29bo3$45b2o28b2o$45b2o28b2o!

The greater number of components might still make it less likely than a true GGG, but I suspect that this gun has a good chance of showing up in the census before the original 3QB non-Gosper gun does.

[pcallahan]

I will have to catch up on the last few posts, but anyway after some crunching I have found three 5x5 clusters that produce queen bees half-stabilized with a block. I believe that these are the only 5x5 solutions up to rotations and flips (so for counting purposes there are 24 out of 2^25). They are all the same after one generation. The enumeration would have found anything in a smaller bounding box as well.

Code: Select all

x = 45, y = 5, rule = B3/S23
b4o16b4o16b4o$obobo15bobobo15bobobo$2o18b3o17b3o$ob3o15bob3o15bob3o$ob
2o16bob2o16bobobo!

Corrections welcome as always.

For completeness, here are two of them paired to make a complete glider gun. Since one cluster has to be out of phase by 5 generations, it no longer fits in the minimal bounding box.

Code: Select all

x = 32, y = 7, rule = B3/S23
2o$o2b2o$bobob2o20b2obo$bo25bo2b2o$2obobo21b2ob2o$3bo23bobo$28b4o!

Here's a precursor in a 2x11 box. I haven't done an exhaustive search. It's sort of uninteresting in that the block stabilizer is part of it.

Code: Select all

x = 2, y = 11, rule = B3/S23
bo$o$2o$o$bo$bo$o3$o$2o!

And a 6x6. This works in a less obvious way, but it is pretty dense. I imagine there are a lot in the 6x6 range.

Code: Select all

x = 6, y = 6, rule = B3/S23
b2obo$bo3bo$2bo2bo$4obo$obo2bo$ob2obo!

Update: I cannot find a compact cluster of 10 cells or fewer that generates the half-stabilized queen bee. There is a 10-cell precursor but it starts with 3 cells for the block offset by 2 cells.

This is mainly for gaming the meaningless "complexity" metric, but here's a Gosper glider gun starting with an initial population of 21 cells in a 36x5 bounding box. The blocks are just placed initially as 3-cell clusters. I'm sure something more clever is possible.

Code: Select all

x = 36, y = 5, rule = B3/S23
26bo$8bobo16b2ob2o2bo$2o7bo17bobo4b2o$bo4b2o$8b3o!

Alternatively, we can start with 22 cells in a 36x4 bounding box:

Code: Select all

x = 36, y = 4, rule = B3/S23
8bobo15b3o2bo2b2o$2o7bo15bobob2o4bo$bo4b2o$8b3o!

My goal is to minimize the "complexity" metric used in the paper, which is overcomplicated, but roughly the negative log of the probability of picking the pattern at random (for sparse patterns by picking a fixed numbers at random in the bounding box). For a wXh bounding bound containing n live cells, the value is: l(w) + l(h) + l(n) + log_2(wh choose n)

l(m) is the length of a Levenshtein coding which I can't find a lot about online but they use the formula l(m) = ⌈log_2 m + log_2 (m + 1)⌉ + 1 to calculate in.

The patterns above have "complexity" 118.1 and 113.4 respectively, which is significantly lower than the 192 they calculate assuming a 36x9 bounding box and population of 36. It also brings the "ASC" down significantly to where it does not meet their criteria of a designed object. This is all very silly, but I am curious how far down I can push it.

26 cells in a 36x3 bounding box.

Code: Select all

x = 36, y = 3, rule = B3/S23
26b3o2bo3bo$b4ob7o12bobob2o3b2o$o2bo2bobo!

[pcallahan]

The definition of ASC is fluid enough that it could be adjusted, with hindsight, to give a better result for any specific counterexample we might come up with. The paper hints at this with regard to an array of a billion blinkers, for example, which would need a "looping or REPEAT command" that's not currently present in Table II. I think we'd always be able to come up with more counterexamples for the adjusted system, but it's not clear that jumping into this particular rabbit hole is really a very interesting exercise.

At the risk of sounding petty (and making my own mountain out of a mole hill), it hit me that they're wrong about this too when they state

D. Computability
The contextual mathematical formulation thus far developed here for the Game of Life is less powerful than a Turing complete language. For example, there is no conditional looping mechanism. The Game of Life itself is Turing complete [48]; however, our equations using the components in Table II describing the Game of Life are not.

Of course they have REPEAT! It's where they introduce ⊕n to mean "run Life for n steps." Consider what you can do with this (probably I don't need to continue.) You could write out the RCT constructor minus the entering glider, run it for some number of steps and then ∪ the incoming glider at the right spot. Alternatively, you could just use shift by n to represent a glider at the entering position.

So they've basically written a much better compression coding language that they realize, capable of encoding anything that can be written as "run this input for this many steps" within an additive constant comprising the cost of the embedded Life interpreter.

You could specify other more interesting patterns with equations that would effectively amount to decision problems answered by any TM running for n steps.

I believe this won't quite give you Kolmogorov complexity or let you express undecidable problems because the encoding must express a fixed numeric limit on the number of steps run. Since you can construct n with variables and arithmetic operations. I think the number of steps can at least be a double exponential using repeated squaring.

Why does it matter? Hmm... well if I didn't assume the authors are disingenuous to begin with, it does show some of the hazards of stepping into recursion theory without thinking about it hard enough. And any "research program" that purports to challenge evolution using mathematics really ought to employ an understanding of the requisite math. Others have made this point (particularly with respect to abuse of probability theory) but this is another glaring deficiency.

Update: The equation language is sufficient to express the problem of stabilizing a partial oscillator. Since there is no way to bound the size of the stabilizer, it seems that with the right partial pattern and period constraint you might be able to embed a universal Wang tile problem. That would greatly expand the expressive power of the language allowing undecidable propositions to be written.

Update 2: Thinking about this a little more, the notation defines an algebra of infinite 2D bitmaps over boolean operations including a negation via set subtraction, so I believe it should be possible to implement Wang tile constraints without even invoking the ⊕ operator (generate Life rule). The limited number of variables may be an issue, but I think it's surmountable. I'm thinking: implement BitBLT Life (or any other rule since Life is there anyway) and then set up an equation to implement constraint satisfaction. To get multiple variables just use a packed representation where a single bitmap holds several, e.g. at even and odd positions.

I had a thought this morning about Douglas Adams's explanation of flying as falling and missing the ground. Writing a formalism that is not universal (Turing complete) is a similar skill. The "gravitational pull" of universality is so strong that you have to go well out of your way to avoid it, and I'm afraid they did not.

[Sokwe]

I'd like to ignore Dave and Paul's discussion for a moment to give my personal feelings on this. I am a bit uncomfortable with the fact that my patterns were used in any way to promote wacky nonsense. I never in a million (or six thousand) years would have thought any of my work would be used in this way. Although it doesn't really matter, I'm honestly a little relieved that my name doesn't appear anywhere in the paper.

I also think they fundamentally misunderstand (or at least misstate) the nature of my patterns. They were not designed, either by me or by a program. They were discovered essentially by a search that enumerated all possibilities in a given area and discarded those that didn't work. Significant effort went into their discovery, sure, but the Higgs boson isn't "designed" just because giant particle accelerators were built to detect it.

They could just as easily describe all of my discarded almost-spaceships as "designed", but those would be indistinguishable from random junk in their scheme. I have likewise seen almost-spaceships occur from random ash that I would be unable to "design" with any currently known direct search method. One might try to claim that the final working patterns are still "designed" because I chose to record only those results that I deemed interesting, but then their ASC suffers from overfitting. They constructed their language specifically and intentionally to describe the types of patterns I and others chose to share.

[pcallahan]

I am a bit uncomfortable with the fact that my patterns were used in any way to promote wacky nonsense. I never in a million (or six thousand) years would have thought any of my work would be used in this way. Although it doesn't really matter, I'm honestly a little relieved that my name doesn't appear anywhere in the paper.

I totally understand your reaction. While I'm less surprised, I'm annoyed at seeing Conway's Game of Life used in this way. Like many ID papers they get a lot of things entirely backwards. "Designed" is whatever they want it to mean, and it is strange to apply it to the results of a search. The authors either do not know or more likely do not care about the actual provenance of any of the patterns they mischaracterize.

It also appears to be a peer-reviewed publication not specifically associated with the ID creationist movement, so it must have slipped under the radar of finding a competent referee. I suspect that is more common than ever today.

They constructed their language specifically and intentionally to describe the types of patterns I and others chose to share.

I don't think they succeeded apart from their cherrypicked examples. Is the "r-pentomino run to 1000 steps" a designed pattern? It is nearly as compact as writing a glider, and has a very high "complexity" by their metric even if you generously omit gliders from the bounding box. (And this is true of many small clusters.)

They could hypothetically raise an objection to using their language to specify a result rather than the solution to an equation. So how about "Y is a pattern that is not the same as Y after applying 20 generations. X is the pattern of interest, equal to Y after 1000 generations and equal to Y after 1002 generations." Now I've described a class of patterns X consisting of stable ash, most of it "high complexity." Are these designed patterns?

[dvgrn]

It also appears to be a peer-reviewed publication not specifically associated with the ID creationist movement, so it must have slipped under the radar of finding a competent referee. I suspect that is more common than ever today.

That might be an angle worth pursuing a little further, actually. That 2015 paper doesn't seem to have collected many citations; only four come up immediately on a Google search. One of those is a new paper from this year, just published in October, that purports to use the ASC metric for (something or other), and prove (something or other) about it:

https://www.bio-complexity.org/ojs/inde ... O-C.2019.2

Apparently there's a slot reserved for a critique of this paper, with the link pre-posted in the PDF -- that's a nice system!

The citations include some of the same cast of characters -- not surprising given the subject is ASC and OASC. Dembski and Ewert show up in the acknowledgements. There's also the following:

Thanks to Dr. Tom English and anonymous reviewers for the critical feedback that helped clarify the article.

(Tom English is an occasional contributor to the Panda's Thumb, so definitely on the ID debunker spectrum.)

One of the authors of this new paper, Eric Holloway, shows up on Uncommon Descent, where you can learn quite a lot about his background and beliefs:

https://uncommondescent.com/intelligent ... in-nature/

[pcallahan]

(Tom English is an occasional contributor to the Panda's Thumb, so definitely on the ID debunker spectrum.)

In fact, I got to the paper through a recent Panda's Thumb post by Joe Felsenstein about ASC. I thought (against my better judgment) that I might want to know the definition of ASC well enough to do more than assert that it's nonsense, and was surprised and annoyed to find Conway's Game of Life showing up in my Google results. But on the other hand, it did give me some motivation to read an otherwise pointless paper, which claims:

We have demonstrated the ability to describe functional Game of Life pattern using a mathematical formulation. This allows us in principle to compress Game of Life patterns which exhibit some functionality. Thus, ASC has the ability to measure meaningful functionality.

(emphasis mine)

Errm, no. You have demonstrated that Game of Life patterns can be expressed with an ad hoc description language, and these descriptions are sometimes larger and sometimes smaller than the same patterns expressed as bitmaps. There is absolutely no connection to "meaningful functionality" which is no more present in the description language than in the bitmaps.

[dvgrn]

But on the other hand, it did give me some motivation to read an otherwise pointless paper...

Ha, and Eric Holloway's 2019 paper at least introduced me to Chaitin's constant and prefix-free universal computable functions, which I don't recall having paid much attention to before. Clever stuff, very Gödelian. Must be in some Raymond Smullyan book somewhere.

Anyway, it seems that Holloway buys Dembski's basic argument:

Dembski proved that searching for a good search algorithm is no easier than performing the search for the primary target in the first place. The implication is that there is no shortcut for naturalistic processes to produce information from chaos, or to increase the amount of existing information, and thus a natural process such as the various versions of evolution cannot be said to create information.

It's a little hard for me to to understand how that "implication" can survive even a few minutes of playing around with cellular automata, where chaos routinely gets transformed by (what seem to me to be) "naturalistic processes", into highly structured patterns ... in an incredible variety of different ways, depending on the chosen rule.

However, the place where Holloway's 2019 paper was published was the open-access journal "BIO-Complexity", which is a pro-Intelligent-Design publication founded by Dembski and others:

"aims to be the leading forum for testing the scientific merit of the claim that intelligent design (ID) is a credible explanation for life".

So it would probably be an uphill battle, to say the least, to implement my vague idea of writing a critique of that paper and getting it made available at the link given in the paper.

[pcallahan]

It's a little hard for me to to understand how that "implication" can survive even a few minutes of playing around with cellular automata, where chaos routinely gets transformed by (what seem to me to be) "naturalistic processes", into highly structured patterns ... in an incredible variety of different ways, depending on the chosen rule.

Dembski's insistence that emergent properties were "smuggled into" the rules is somehow invulnerable to any amount of evidence. I think even he would acknowledge that Conway did not "smuggle" in an expectation of gliders, spaceships, shuttles, or the boat bit among other things when working out the rules and was genuinely surprised at first, along with everyone else, to see these. It's less of a surprise now, given experience, but I cannot even imagine what sort of smuggling is supposed to be going on.

Presented with a spontaneous toggle flip-flop in the form of the boat bit (and I've seen plenty where I didn't want them in searches for stable reflectors), an ID person will fall back on the claim that it is just a natural object explicable by chance. But this is disingenuous. The frequency of common Life objects (including those with specific interesting properties like eaters and boat-bit catalysts) is far higher than indicated by setting bitmap cells randomly. Life rules converge on certain patterns the same way other iterative systems converge on them, and by chance some of these patterns have properties that we note with interest. Occasionally, someone might "design" a pattern that turns out to be more frequent than they realize (though more likely, there is a more concise object that actually shows up in soup experiments, searches, etc. that improves on their "design" and carries out the same function.)

Tautologically, that which shows up with sufficiently high frequency in nature is natural, and that which does not is not. There are ways to look at Life patterns and speculate about their provenance (which as Sokwe points out is often search, not design), but misapplying statistics is not a fruitful approach. I had actually (optimistically) thought that Dembski was laying low these days (and maybe he is) but the misapplication of math seems to be moving ahead full blast.

[dvgrn]

Dembski's insistence that emergent properties were "smuggled into" the rules is somehow invulnerable to any amount of evidence. I think even he would acknowledge that Conway did not "smuggle" in an expectation of gliders, spaceships, shuttles, or the boat bit among other things when working out the rules and was genuinely surprised at first, along with everyone else, to see these. It's less of a surprise now, given experience, but I cannot even imagine what sort of smuggling is supposed to be going on.

Given how improbably far the chain of Conway's Life discoveries has extended in the last half century, it seems most likely that the smuggling has been done by some some Designer who has been mischievously adjusting the laws of mathematics to allow more stuff to be discovered.

Heh, they think they've found everything now, do they? Let's put in a tiny c/7! Ha, then how about a small symmetric c/10, too? That will really drive those "experts" crazy... Can't get universal construction with one stream of far-apart gliders? Hm, well, now you can... Oh, a 2-engine Cordership is too improbable to be worth looking for, is it? Let's just see about that...

The requirement for a mischievous deity means that my faith is confirmed: it must be the Flying Spaghetti Monster. May our future searches continue to be touched by Noodly Appendages on occasion.

[Sokwe]

it must be the Flying Spaghetti Monster. May our future searches continue to be touched by Noodly Appendages on occasion.

Truly, we are blessed. Indeed, some of the smallest, simplest spaceships were discovered after this paper (although loafer was found substantially before their publication). It's also funny that they used an obviously incorrect pattern in place of the lobster.

[pcallahan]

Three more thoughts. First, I think I have a Gosper glider gun with "ASC" about 4 using 26 cells in a 36x3 boxes. (The "complexity" is reduced by 81.) If I could reduce the cell count further, I might be able to get it to go negative. This is not important at all, but it's a puzzle. I would argue that a lot more "design" goes into this compaction process than in setting up the original interaction; at least I don't have an automated search for it (nor enough CPU power to see for myself if it shows up 1 in 10^18 tries.)

Code: Select all

x = 36, y = 3, rule = B3/S23
o2bo2bobo$b4ob7o12bobobo4b2o$26b3ob2o3bo!

Second, circling back to this statement from the paper (Dave Greene alluded to it):

There are concepts that cannot be described using the operations we have defined. A large array of a billion closely spaced albeit noninteracting blinkers has low KCS complexity akin to the celebrated low KCS complexity of a repetitive crystalline structure.

Uh, OK. Well... bzzzt, wrong again!

I made this point earlier in terms of a general expressive power, but actually a row of blinkers spaced 4 cells apart is remarkably easy to represent with equations using boolean expressions on infinite bitmaps with displacements. Without going into specifics of the authors' notation, we can write a short expression with XOR implemented with union ∪ intersection ∩, and set difference - as (A ∪ B) - (A ∩ B) (Update: I believe there's a simplification using just set difference, not XOR.)

• Y is a bitmap containing a blinker and another blinker 4 billion positions to the right.
• X shifted 4 right = (X∪Y)-(X∩Y)
• Let X be the minimal solution to the above.

The takeaway should not be "Whoa! Our notation works even better than we thought." but "We really ought to put more thought into things before submitting them for publication." (And for the editor: "We really need better referees.") (And if I made a mistake, please let me know. It should be fixable.) And note that the blinker row has absurdly large "ASC" by virtue of size alone (and despite all the champagne corks popped over its low KCS complexity).

For general expressive power, you should be able to embed Wang tiles as I said (even limited to one variable). I was thinking explicitly how you could implement a very long distance in the grid as the length needed to count down to 0 from a string of all one bits. It's probably not worth thinking too hard, but they're basically defining something as powerful as 2D difference equations (at least with bounded integer values) so obviously there are many things that can be expressed beyond the oscillator expressions they customized it for. (I guess some rogue editor "smuggled in" the other parts.)

Third (and sort of an afterthought). A way to remove gliders from a stable ash field that may include periods that are any factor of 12 is to run the pattern 12 steps and intersect it with itself. (Old observation, right?) Hence it is easy to express "A pattern that runs for n steps and then stabilizes, ignoring gliders." (The equation requires some care to deal with other things besides gliders that make have inadvertently been removed.) This is a methuselah for large enough n--probably a little unfortunate to have a biblical allusion in this context. I can't think of a sane person who would argue that methusalehs originating from small clusters are "designed." And also the final ash field generally does have high "complexity" based on ASC. Yet, it's not a made-up example. At least some hobbyists may note methusalehs with interest. So this is probably my favorite candidate for pointing out the utter meaningless of ASC in a CGOL context.