A New Kind of Science: The NKS Forum > Pure NKS > CA three dimensions
Author
M.Abdeldjalil

Registered: Nov 2008
Posts: 39

CA three dimensions

Please i'm interesseted to three dimensions CA, are there explanations in NKS other in the page 182,183?

And about the image recognition with CA.

Report this post to a moderator | IP: Logged

03-14-2009 02:56 PM
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

I'll answer the 3D question first; it is simpler.

There are a few notes in the back of the NKS book, page 929 e.g., but not a lot of additional analysis. It is obviously harder to depict the evolution of 3D CAs because the space-time evolution is 4 dimensional. Even using e.g. a movie of a changing 3D object can be problematic, because it is hard to see the features buried in the interior of that object. In current Mathematica, the Opacity option for graphics can help somewhat, but even the wire frames left can get incomprehensible to our eyes once they get at all large or intricate. Wolfram's scheme for showing them as shaded grey-level projections "in plan" may be better for some purposes. Of course, it is also straightforward to make 2D projections ("slices") in multiple planes, and with modern Mathematica one can then readily "scan" through the object in layers of those successive slices using Manipulate.

All of that is about visualization. The actual evaluation of 3D CAs is straightforward, once one faces up to a few complexity-space size issues and decides how to deal with them. I'll explain.

A normal 1D CA with range 1 has 256 possible rules because the colors (2) must be raised to a power equal to the number of distinct possible patterns in the neighborhood, which is all possible Tuples of 0-1 bits, 3 long. Thus 2^2^3 = 2^8 = 256 possible rules. With a 3D CA in which corners are allowed as adjacent in all dimensions, and the exact pattern matters, the only change in that formula is that the "3" for cells that matter for the next step, becomes a 3*3*3 = 27.

That means there are 2^27 cases in the rule table, and 2^2^27 distinct possible rules. 2^27 is 134 million. The correction for the base 2 vs. a base of 10 is .3 times, meaning there are 10^(40 million) possible rules of this kind. There are about 10^90 particles in the universe, and 10^60 planck times since the universe began. If every particle in the universe gets ten billion different versions its own rule number flashing by in each planck-time, the universe has to go on 250,000 times as long as it has so far to get through them all. All the stars will have gone out before you'd get through 3% of them - not that anyone has every particle in the universe trying out ten billion of them every smallest-physically-real fraction of a second.

In other words, you are not going to try out general 3D cellular automata, with corners counted and all possible neighborhood configurations mattering. There are simply too many of them to even try. Even with just the 6-neighborhood (plus center cell makes 7), if all possible patterns matter there are 3.4x10^38 possible rules, not yet managable. Just as with totalistic and outer totalistic schemes in 2D, we have to look at simpler cases.

The two Wolfram looked at for the book are (1) totalistic CAs with only 6 neighbors (top and bottom plus the usual 2D four) and (2) totalistic CAs with all 27 neighbors. There are only 2^8 = 256 of the former, no problem at all. There are a more abundant but still managable 2^28 of the latter, which is a rule-space of 268 million rules. That is a size one can explore computationally with random samples etc. The other class that makes sense to look at would be outer totalistic with only top and bottom neighbors. Those have 2^14 possible rules, 16384 all told, to good size to explore.

So you first have to decide which of those simplifications you'll make. It makes sense to go in the size order, starting with 6 neighbors and fully totalistic, then 6 neighbors and outer totalistic, and finally looking at the monster case of all 27 neighbors and fully totalistic. The next one, outer totalistic all 27 neighbors - there are 18 quadrillion rules. You could instead try 3 color with 6 neighbors if you want to push onward.

How do you evaluate them? No different from the 2D case, except now your local neighborhood partition needs to be moving 3D blocks. By staying totalistic or outer totalistic most of the extra geometry can be ignored - you just Flatten the neighbor values into one list and count 1s, perhaps first Extract ing the center cell in the outer totalistic case. The data needs to be stored as a list of 3D objects, one for each step. All straightforward.

Next come the challenges of visualization of the results, alluded to in the opening paragraph above. My own recommendation is to use Mathematica and a Manipulate function with 2 sliders, one for the time step and one for the vertical "height" of your slice through the data, and then just use ArrayPlot for each of those slices. Much simpler to understand and easier to "see through" than Map -ping Cuboid objects over data-generated locations in a Graphics3D object. I mean, you can do the second, we've had several people at NKS summer programs who've done it. (Architects, several of them, by the way). But the view "in plan" with 2 different slider controls, one for the "floor" of your CA "tower" and the other for the step number, is much easier to work with.

I hope this helps.

Report this post to a moderator | IP: Logged

03-16-2009 06:00 AM
M.Abdeldjalil

Registered: Nov 2008
Posts: 39

Hi,

Can you explain me how we can desing the 27neighbors. And in this case, the cell must be a cube?

Report this post to a moderator | IP: Logged

03-20-2009 11:20 AM
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

Sure, it is a 3 by 3 by 3 cube. The first 9 locations are on the plane one cell "above" the center cell, the next 9 are on the same plane (including the center cell itself), and next 9 are on the plane one cell "below" the center cell. Within each of those, they are numbered the same way as the 2D case. If you need to number them, that is - for a totalistic or outer totalistic rule is suffices to add up cell values in that neighborhood. That works just like the 2D case.

Report this post to a moderator | IP: Logged

03-20-2009 02:55 PM

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us