[How to find the rule(s) of a CA looking image ?] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


How to find the rule(s) of a CA looking image ?

(Click here to view the original thread with full colors/images)


Posted by: janos

Subject says it all. But to re-phrase, the question is: If I have an image which looks like a CA and I know nothing about it, how can I find out what rule or set of rules were used to create the image if it is a CA ? Here is a teaser attached.

I looked the Book, but found no reference to this question.


Posted by: Adam B.

Hi Janos,



First, a binary counting example. If we have a number in binary, we calculate what its value in base-10 is by going from right to left. For example, 11101 is:

1 * (2^0)

+

0 * (2^1)

+

1 * (2^2)

+

1 * (2^3)

+

1 * (2^4)

= 29

The power for each "digit" in the binary (base-2) location of that digit. The rightmost digit is in position 0, the the second to the rightmost digit is in position 1, and so on:

1 1 1 0 1
4 3 2 1 0

If the image is in fact the result of a one dimensional cellular automata rule, then you just need to examine the image:

Let the black cells be 1.
Let the white cells be 0.

Now find the resulting output of all 8 possible 3-cell combinations (i.e., 000 through 111 in binary, or 0 through 7 in base-10) by sampling at random from the picture.


For your teaser example, here are the results:


// if a white cell has two white neighbors, then that cell's result will be black (1) on the next row

000
1

// if a white cell has a white neighbor on the left and a black neighbor on the right, then that cell's result will be white on the next row

001
0

[...]

010
1


011
1

100
0

101
1

110
1

111
0


So if you put the partial results in order (from right-to-left, remember, because we are talking binary), you get:

0110110

This number, assuming I have not made any mistakes, is 54 in base-10. So, assuming I have not made mistakes, your rule number is 54.

In order to *know* that the picture is in fact the result of a cellular automata rule, you need to make sure that the rule (the composition of all eight of the combinations) applies for the entire image. So, for example, you should verify that all rows that have a string of 111 (black-black-black), have a 0 (white) below the middle 1 (black) in 111.

Now, if you examine rule 54 in the book, it will look nothing like the picture you showed. That is because Wolfram only shows the rules where the first row is seeded with one black cell. The picture you attached is most likely the result of a randomly seeded row.

Hope this helps.


Posted by: janos

Hi Adam,

You are right on target. I think you just missed the very first digit, and I think it should be counted from left to right. If follow what you did then I will get these pairs:

000 -> 1
001 -> 0
010 -> 1
011 -> 1
100 -> 0
101 -> 1
110 -> 1
111 -> 0

if I read this from "bottom to up" and lay it down from left to right, then I get a binary of:

01101101

and that is 1+4+8+32+64 = 109

Here is the little program I used to create it:

In[1]:=
k = 2
r = 1
steps = 50

In[6]:=
cafl = Table[
CellularAutomaton[
{i, k, r}, Flatten[
Table[Random[Integer,
{0, 1}], {l, 0,
steps/2}]], steps],
{i, 1, 255}];

To display them with their rule number

In[7]:=
Table[ArrayPlot[cafl[[i]],
DisplayFunction ->
$DisplayFunction,
PlotLabel -> {i}],
{i, 1, 255}];

and I did get the picture for my second run.
Thanks a lot,

J‡nos
P.S. So it looks to me that in case if the elementary CA and for the combinations of elementary CAs a procedure should be something like this:
Partition the picture into 2x3 pixel plocks /3 in a row, 2 in a column/ and look for all possible occurances. If they do fall cleanly into distinct categories, then we have the one rule case and the rule can be deciphered easily. I think there is some text in the Book indicating how far the initial conditions last, so we should do this outside of that range. If they do not fall cleanly into distinct categories outside of the initial conditions influence sphera, then we have the case of mixed rules, that is at some steps the rules were changed. Then we should look into if they fall into cleanly separated categories along the evolution line, that is if its evolution can be divided into distinct epochs. If yes, then we have the cases of mixed rules who run their courses in their epoch time. If such categorisation is impossible, then the rules were probably randomly mixed at every step.


Posted by: Adam B.

You're right, I did miss the first digit. I apologize for the confusion.

Could you please clarify your statement, "If such categorisation is impossible, then the rules were probably randomly mixed at every step"? Do you define an epoch as minimally two steps of evolution?

I imagine you are talking about the circumstance where say row 1 runs on rule 100, and then row 2 runs on rule 105, and then row 3 runs on rule 88, and so on in a random fashion. I think that in certain circumstances, particularly in the case of some simple encryption systems, you can probably still at least extrapolate what rule set was used at each step, at least on a sufficiently wide CA . . . And if you can do that, then you can probably figure out what underlying "randomness" model was used to determine which rule to apply at each step, or at lest you should be able to classify what category of randomness model was applied if you cannot figure out the actual one used. The ability to break down patterns of rule changes here depends largely on the number of steps of evolution that you have for analysis and how many computers you can cluster together.

In the case where people switch things up in a random fashion for every cell at every step of the evolution, using, for example, some kind of sophisticated random number generator, finding regularities seems to me to be a much more difficult task, at least in terms of number of computations required! One characteristic of these types of systems, at least from my experience, is that they will have a lot of perceived noise, which is pretty common when people inject randomness at every point.

Are you doing some applied work in pattern recognition by any chance?


Posted by: janos

"Do you define an epoch as minimally two steps of evolution?"

I am thinking of an epoch as the range of the evolution where the rule was the same. For example if I have a case where the first 5 rows - from an initial condition - were created by rule x and the remaining rows after row 5 were created by rule y, then I say that there was two epochs of evolution here, one is characterized by rule x and the other is by rule y. I also realize that I can have a mixed rule situation where the "rule" is that rule x was running for 5 steps and rule y for another 5 steps and they did it N times, so then the question is what is more conveniant. I can look at it based upon my saying above that it has two epochs and the two epochs are "oscillating" with steps 5 length, or I can say that there is just one compaund rule and the compaund rule is that for 5 steps I use rule x and for another 5 steps I use rule y and I repeat it N times. I do not have a good grasp on how such compaund rule can be used with CellularAutomation, but if it can, then the next thing to check is the situation when I say that my new compaund rule is suchs that I select between rule x and rule y by a coin toss. Then my epochs again can be the decomposed epochs strickly obeying the two, the distinct lengths of rule x or rule y employed, or I can say that i have here a compaund epoch obeying the compaund rule where the elements of outer randomness are creeped in. Probably it is harder to handle this last case if I want to know the exact bounday of the epoch changes f rule x and rule y, but on the same time it might be more adventagous if I just want to know what kind of evolution do I get "in general".

Let me try to "cut" it from anoter angle. If I look the evolution of a CA with a rule, neigbourhood, color, and initial conditions, then I can say that the rule, neigbourhood, color and the conditions describe the "genotype" of the CA. If let say I fix the rule, the neigbourhood, the color and vary the initial conditions, then I can have different pictures of the evolution - after some steps -, where the pictures, can be the same, somewhat different or totally different. I would call these pictures of evolutions "phenotypes". Then immediatelly I can have some quick questions asked.

1, What are those rules, neighbourhoods, colors, where the varying of initial conditions gives me always the same phenotype with translation, rotation or mirrorring symmetry.

2, What are those rules, neighbourhoods, colors, where the varying of initial conditions gives me different phenotypes, that they cannot be brought to overlap each other with translation, rotation or mirroring.

3, What kind of phenotypes do I get if I apply some functions to the CAs ?

For example here is a small program:

<< DiscreteMath`GraphPlot`
k = 2
r = 1
step = 100

Off[General::Spell]
Off[General::Spell1]

ca = Table[CellularAutomaton[{i, k, r}, Join[Table[0, {l, 1, step/2}], {1}, Table[0, {l, 1, step/2}]], step], {i, 1, 255}];

ArrayPlot[ca[[11]]];

See ca11.pf attached

Then let's see what do we get if we create a different kind of graphics from ca.

lp = Table[Map[N[Log[FromDigits[Reverse[#]]]] &, ca[[i]] ], {i, 255}];

tp = Table[Map[N[Log[
FromDigits[Reverse[#]]]] &, Transpose[ca[[i]] ]], {i, 255}];

tl = Table[Thread[List[lp[[i]], tp[[i]]] ], {i, 255}];

That is in lp I have a table of numbers I get when I create a number by taking the black and white cells as 1's an 0's and look at it as a number in base 2 and taking its logarithm and do it for every CA. Similarly in tp I convert every columns - the evolution of a cell along the time axis - and convert it to a number and do it for every cell and for every CA. Then in tl I thread them together, so I have pairs of numbers and then:

tlgp = Table[Map[#[[1]] -> #[[2]] &, Partition[tl[[i]], 2, 1]], {i, 255}];

I want to see them as graphs by GraphPlot. Here it is a 3D plot of tlgp[[11]]

GraphPlot3D[tlgp[[11]], "RootPosition" -> Center, Method -> "Automatic"]

See tlgp11.pdf.

It looks interesting. Then my forth question might be: how similar these graphs are if I print them all by varying the initial conditions, let say I move the initial black dot from left to right along the 100 cell wide lattice. Interestingly the answer is that they are just "somewhat" similar and they can be classified into separate groups even for a givven CA, like ca[[11]]. I can look at them as my new "phenotypes". More interesting, that accross CAs if I vary the initial conditions I will get similar new phenotypes at different initial conditions. Then I might do my classifications of the CAs differently. I might create first all the new phenotypes for all k=2 colors and r=1 neighbours and reorder the CAs based upon how they are clustering according to the new phenotypes. Then I might re-define my epoch and will say that an evoluton of a CA is falling into the same epoch regardless to the initial condition if it can be classified into the same kind of new phenotype cluster.

What do you think ?

No, I am not working on pattern recognition. I just got fascinited by these graphplots and try to use them to model genotype <--> phenotype relations with them. /Of course I am also NOT a biologist of any sort :)/

J‡nos
P.S. Well, I do not know how to upload more files, so I just select tlgp11.pdf here. I guess you can look up ca[[11]] online in the NKS book. Sorry...




Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings