Can Life generate any disconnected fractal?

 Posts: 24
 Joined: October 13th, 2017, 2:14 am
Can Life generate any disconnected fractal?
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?
2. If it can, does that mean all fractals are some kinds of chaotic attractors, namely, the trajectories of Life movements/actions?
Re: Can Life generate any disconnected fractal?
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.Koiti Kimura wrote:1. Can Life produce or imitate Sierpinski carpet or something which has disconnected parts?
More or less.
Sometimes painfully, and/or by analogy.
The lowestlevel 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 singlepixel 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.
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.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?
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 goldenb tiling might be an example. It's kind of a rectilinear analogue of Penrose tilings. You could map a threecoloring of an infinitely inflated goldenb 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.

 Posts: 24
 Joined: October 13th, 2017, 2:14 am
Re: Can Life generate any disconnected fractal?
[/quote]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.[/quote]
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?
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?
Re: Can Life generate any disconnected fractal?
No, no particular mistakes I think. Just thought you might be using "Life" in the sense of "Lifelike", or an even wider class of rules  sometimes people do overgeneralize like that.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?
In any case, any nontotalistic MAP rule is presumably fair game  if you're willing to accept Life metacells as the substrate for your fractals,

 Posts: 24
 Joined: October 13th, 2017, 2:14 am
Re: Can Life generate any disconnected fractal?
Then let me reformulate my question: can all the finitedistance/area/radiusneighborhooded CAs handle all the finitesized fractals unlike goldenb 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?
Re: Can Life generate any disconnected fractal?
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.Koiti Kimura wrote:Then let me reformulate my question: can all the finitedistance/area/radiusneighborhooded CAs handle all the finitesized fractals unlike goldenb 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?
CAs can "naturally" produce some interesting fractal patterns, but for many others you'd have to fall back on the old strained and awkward catchall argument  that many CAs are universal, so therefore you could do an incredible amount of work to mathematically model any chosen finitesized 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 selfsimilar 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 nonempty background of logiccircuit tiles or what have you. (Matthew Cook's proof of the universality of Rule 110 requires an infinite nonempty 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 CAcompatible 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.
Re: Can Life generate any disconnected fractal?
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_{n1}) 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 spiralgrowth pattern.
Specifically, if (1, c_1, c_2, ..., c_n) are the nonzero cells, in spiral order from the origin, then it attempts the following:
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 / nonhead) 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 2state patterns, P0 <= P1 <= P2 <= P3 <= ... such that the limit of the P_i's (scaled to have constant width) is a selfsimilar 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.

Firstly, I've realised that it's possible to elegantly convert any set of n Wang tiles (W_0, W_1, ..., W_{n1}) 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 spiralgrowth pattern.
Specifically, if (1, c_1, c_2, ..., c_n) are the nonzero 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.
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 / nonhead) 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 2state patterns, P0 <= P1 <= P2 <= P3 <= ... such that the limit of the P_i's (scaled to have constant width) is a selfsimilar 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 monoclinic!