Can Life generate any disconnected fractal?

For discussion directly related to ConwayLife.com, such as requesting changes to how the forums or home page function.
Post Reply
Koiti Kimura
Posts: 24
Joined: October 13th, 2017, 2:14 am

Can Life generate any disconnected fractal?

Post by Koiti Kimura » October 18th, 2017, 8:53 pm

1. Can Life produce or imitate Sierpinski carpet or something which has disconnected parts?
2. If it can, does that mean all fractals are some kinds of chaotic attractors, namely, the trajectories of Life movements/actions?

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Can Life generate any disconnected fractal?

Post by dvgrn » October 18th, 2017, 9:50 pm

Koiti Kimura wrote:1. Can Life produce or imitate Sierpinski carpet or something which has disconnected parts?
By "Life" do you mean B3/S23 -- Conway's Life -- or any CA? If B3/S23, then yes because Life has been proven to be universal and can therefore do anything you can program a computer to do.

More or less.

Sometimes painfully, and/or by analogy.

The lowest-level pixels in the Sierpinski carpet might have to be some kind of metapixel structure. It seems quite likely that some size of the simplest bitmap version of a Sierpinski carpet is a Garden of Eden, and thus can't be produced at T>0 in B3/S23 after all. But we could make a pattern that lays down a pattern of blocks that matches the ON/OFF pixels in a Sierpinski carpet, or something like that.

If other rules, especially multistate rules, are allowed, then it might be easier to come up with something that works on the single-pixel level.

... Also, Sierpinski carpets don't seem to me to have any disconnected parts, though the inverse of a Sierpinski carpet obviously would -- it's all different sized disconnected holes, like a Cantor dust except less dusty.
Koiti Kimura wrote:2. If it can, does that mean all fractals are some kinds of chaotic attractors, namely, the trajectories of Life movements/actions?
I probably don't really understand the question, but I don't think there's necessarily a natural mapping from an arbitrarily chosen fractal to a CA rule, or vice versa.

Some fractals show up naturally in CAs. There are Sierpinski triangles all over the place, for example, pretty much always due to some variant of the same mechanism, where you only need to know the states of immediate neighbors in one dimension to calculate out the next neighbor's state in the perpendicular direction.

But there are lots of fractals where if you mapped them onto a cellular automaton, a given cell might have to know about the state of another cell arbitrarily far away. Robert Ammann's golden-b tiling might be an example. It's kind of a rectilinear analogue of Penrose tilings. You could map a three-coloring of an infinitely inflated golden-b tile onto a square grid, but it would (I think) be very tricky to generate that coloring with a CA, because you'd have to make coordinated decisions at larger and larger distances -- knowing what color your neighbors are isn't nearly good enough.

Koiti Kimura
Posts: 24
Joined: October 13th, 2017, 2:14 am

Re: Can Life generate any disconnected fractal?

Post by Koiti Kimura » October 18th, 2017, 10:11 pm

By "Life" do you mean B3/S23 -- Conway's Life -- or any CA? If B3/S23, then yes because Life has been proven to be universal and can therefore do anything you can program a computer to do.
Can "Life" mean/refer_to "any CA"? Then what do you say about my last comment on "Life Imitates Sierpinski" topic? Did I make any mistake(s) there again?

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Can Life generate any disconnected fractal?

Post by dvgrn » October 18th, 2017, 10:17 pm

Koiti Kimura wrote:Can "Life" mean/refer_to "any CA"? Then what do you say about my last comment on "Life Imitates Sierpinski" topic? Did I make any mistake(s) there again?
No, no particular mistakes I think. Just thought you might be using "Life" in the sense of "Life-like", or an even wider class of rules -- sometimes people do over-generalize like that.

In any case, any non-totalistic MAP rule is presumably fair game -- if you're willing to accept Life metacells as the substrate for your fractals,

Koiti Kimura
Posts: 24
Joined: October 13th, 2017, 2:14 am

Re: Can Life generate any disconnected fractal?

Post by Koiti Kimura » October 19th, 2017, 12:45 am

Then let me re-formulate my question: can all the finite-distance/area/radius-neighborhooded CAs handle all the finite-sized fractals unlike golden-b tilings? Namely, can you reduce/attribute all the finite chaos theory to the finite fractal theory as the finite chaos world lines theory or vice versa?

User avatar
dvgrn
Moderator
Posts: 10610
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Can Life generate any disconnected fractal?

Post by dvgrn » October 19th, 2017, 7:16 am

Koiti Kimura wrote:Then let me re-formulate my question: can all the finite-distance/area/radius-neighborhooded CAs handle all the finite-sized fractals unlike golden-b tilings? Namely, can you reduce/attribute all the finite chaos theory to the finite fractal theory as the finite chaos world lines theory or vice versa?
You'd probably have to define most of these terms for me in a lot more detail, before I'd be sure that I understand your question. And even if you did that, it seems quite possible that no one knows enough to have a definite answer for you.

CAs can "naturally" produce some interesting fractal patterns, but for many others you'd have to fall back on the old strained and awkward catch-all argument -- that many CAs are universal, so therefore you could do an incredible amount of work to mathematically model any chosen finite-sized piece of any given fractal, using a universal computer built inside that CA. That doesn't really say anything new about a connection, or lack of connection, between CAs and fractals.

One basic problem that I think you'd have to be very careful and specific about, before these kinds of questions would really make a lot of sense: fractals are supposed to be self-similar on every scale, but CAs necessarily "bottom out" at the cell level, at best -- maybe at the metacell level, as in the Sierpinski carpet case above, if you want to allow filling all of an infinite CA universe with a non-empty background of logic-circuit tiles or what have you. (Matthew Cook's proof of the universality of Rule 110 requires an infinite non-empty background, so you might say there's some precedent for this kind of special pleading.)

Anyway, it might be good to start with a suitably modified CA-compatible definition of "fractal". But I'm not sure quite what that modification would be. As you add arbitrary qualifications and exceptions, the whole idea starts to be more confusing and less interesting.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Can Life generate any disconnected fractal?

Post by calcyman » October 19th, 2017, 8:59 am

You can make the notion completely precise using aperiodic tilings.

--------

Firstly, I've realised that it's possible to elegantly convert any set of n Wang tiles (W_0, W_1, ..., W_{n-1}) into a 2D cellular automaton with An + B states (where A, B are some universal constants) where a single cell in state 1 attempts to be a spiral-growth pattern.

Specifically, if (1, c_1, c_2, ..., c_n) are the non-zero cells, in spiral order from the origin, then it attempts the following:
  • If c_n represents a Wang tile W_k which interferes with earlier Wang tiles, increment its state to W_{k+1};
  • If c_n represents a Wang tile W_n beyond the admissible range, delete it;
  • If c_n represents a Wang tile W_k which does not interfere with earlier Wang tiles, append another cell representing W_0 to the end of the spiral.
If there is no admissible Wang tiling, this will terminate in finitely many steps. If there is an admissible Wang tiling, the state of the universe will converge to the lexicographically first (in spiral order) such Wang tiling, meaning that every cell will eventually be constant and represent the correct tile. (Proof: compactness/Tychonoff)

Note that this does not contradict the undecidability result, because it's undecidable to tell whether a tile has 'stabilised' or whether the spiral will at some point backtrack and delete that tile.

Note: I think it can be done with A = 3 and relatively small B, where a cell representing a tile carries an extra trit of information (testing head / valid head / non-head) and the few states contributing to the value of B are for determining which way to turn the snake so as to trace the spiral.

--------

For the second part of the correspondence, suppose you have a sequence of nested 2-state patterns, P0 <= P1 <= P2 <= P3 <= ... such that the limit of the P_i's (scaled to have constant width) is a self-similar fractal. Then you can take the limit of the unscaled P_i's to get an infinite pattern which, in a certain sense, 'corresponds' to that fractal in the same way that the limit of several cellular automata 'corresponds' to the Sierpinski triangle.

Now, if you can find a set of Wang tiles such that every P_i is locally derivable from every admissible tiling (and at least one admissible tiling exists!), then you can construct a nice rule table in Golly which will build the lexicographically first Wang tiling, in which you can see infinitely many copies of approximations to your fractal.

You could actually use Golly's 'icons' feature to make the resulting tiling, when zoomed in, look like one of the colourful illustrations of Wang tiles on Wikipedia. It would be fun to do this explicitly for the minimal aperiodic set of Wang tiles, after dealing with the annoying extra states required to bend around corners to achieve spiral growth.
What do you do with ill crystallographers? Take them to the mono-clinic!

Post Reply