Introduction to a Unified Model of Cellular Automata

Hi, I'm Rodrigo Ovando. I'm a professor at Columbus State University and I am presenting Introduction to a Unified Model of Cellular Automata. All right, thank you for coming to my talk. Introduction to a Unified Model of Cellular Automata. I uploaded the file so it should be available for you. And here there's talks about all the different things that I want to talk about. So let me go ahead also talk. You know, thanks to Bob and Todd and some other people. I was, you know, I have a packlet that I uploaded yesterday, so it's available now if you, if you're interested in looking at all this. So basically what I'm going to do today is just start with a little bit of the theory, not much, but then highlight some of the functions that are available in the packlet. Let me start with also the detail. The theory of this is actually going to be hopefully working right now with an editor in a journal of cellular automata with a, you know, a paper where it actually goes a little bit deeper into all this theory. And it's about a 30 page paper. So I'm not going to do that here. All right. So at the very heart of the model lies the decomposition of cellular automata rules into gene functions and simply rules. You know, each cellular automata rule can be decomposed into K number of genes, where K is the number of values in the cells of the cellular automata. For the case of k equal to 2, which is actually being some familiar with, we may express the function that describes the cellular automata like in here. This is F of a sub zero. A sub zero is the central cell. And then we have a sub zero, not g sub zero plus a sub zero g sub one, where G sub zero and G sub one are the gene functions. So any of the rules in particular For K equal to 2 can be expressed this way. And all the functions we normally deal with just the entire function, we in fact are interested more in the output of that. And that's how we work with decades. We just looked at the integer, that's the integer that give us the rule. And that's about it. So what I did is I split it. And the reason behind this is that I can actually decompose that in such a way that when and I can have a G sub 0 and G sub 1, two different functions. And I say when the cell is sub 0 is 0, there is one gene that is active. When a sub 0 is 1, there is another gene that is active. So I can split it. Now to generalize that. I actually did that using the Kronecker delta. And for k values greater than 2, then of course, now that becomes a summation of those using the Kronecker Delta, like this. And this is the basis for the start for all this work. So when I did that, then we actually had each one of those functions, what I call Genesis. We can start with R equal to zero, the neighborhood where zero means no neighborhood, it's just the cell in the middle. So the genes that you have available are just constants 0 and 1. There are no input whatsoever except for 0 and 1, which is a sub zero. But when you go to R equal to half, which is one cell to the left, this is customary, then we actually the following genes, which is 0 and a 1 and a minus 1, sub naught and a minus 1. And then if we continue for the next neighborhood, which will be cell to the left, cell to the right, then we now have 16 genes, 16 different functions that we can use. And this in fact, is the genes for creation of the eca, or the cellular. The cellular automata, the elementary cellular automata. Now, using that, we can then have a different way of displaying the set of rules, which is by using a table where the dimensions of the table will be the sets, you know, these gene sets. So, for instance, for R equal to zero, this the only four cellular automata that can be created. And I know that, you know, in general, they are not really interesting. You know, these are things that we haven't seen. We know that the minimum neighborhood that you need to create something that is interesting, you know, that would have complexity or, or some other interesting behavior, is actually R equal to one. But I looked at it. So this actually works from zero all the way to whatever number you want. So this over here is the set of rules for r equal to 0. If we make r equal to 1/2, this is the set of rules. And as you can see, you have up here you have the actual functions, and here you have the numbers associated with those functions. The same thing that we have down here, these are the functions and these are the numbers. Now, what you will notice though, is that in terms of the functions, we find that these four functions, of course they still exist in here, and they are in the relative same position, relatively the same position in the corners. So everything else that is new is actually showed up inside. The problem is that when we refer to those, when we're looking to the integers, the integers are different. Five is not one, 10 is not two. Because we are expressing those numbers according to the rule space that we are, that we're working on. So, but this arrangement, you know, there's a. I'm not going to go into the details for that. There is actually a permutation that actually allows me to keep each one of those functions in the same place. Excuse me. So when we do something like this, and then we now express each one of the rules, we can actually create a vector space. And then instead of just having the individual integers, now I have a vector. And the vector will have the genes of 0 and the genes of 1 into. Into the vector. So these 2 will make up 110, 6, 3 will make up 3, 36, 6 will make a 90, which is, that's interesting because 90 is a symmetric rule, you know, actually has both genes are exactly the same. And we can do that also for, you know, this is an R equal to K equal to three, where you have, you know, a different, you know, a much bigger space. This is 7 trillion space. So these are the ones that we have in here, and these are the genes. So now for this, k equal to 3. Excuse me, you have three genes. If you go to k equal to 5, you have five genes. So this is, you know, the generalization from this. So there is also, you know, this is, by the way, this is the function, you know, the function rule genes actually splits. This is in the packlet, it splits the rules into its genes. And there is the, the opposite function which actually takes genes and it gives you back the rule. So if you provide 10, 7, it will give you 1, 10. If you provide these three genes under k equal to 3, r equal to 1, it will give you back this rule. So we can go back and forth in between. And that's at the heart of the whole thing. After that, I use these two functions to split them, work with them, put them back together, et cetera. So when I realized that I could create this transformation, and then I make sure that the functions remain exactly in the same place, relative, same space. It doesn't matter how big the space is, the functions that are in one space, they will show up exactly on the same relative space on the next one. So I use that and said, okay, I can use that position and divide it by the number of rules that I have, that in this case the primitives. And then I can get a normalized vector instead of just the other one. So in the case of 110, 30 and 90 and 45, you know, these are the normalized vectors. So that gives you the position within the hyperscube you know, so it's actually a hypercube. And when you go over here, you know, this, this function is just to normal space. You will take the rule and put it into, into this normalized space. Then you can take those normalized vectors and you actually get the rules back. So, so this, this, these rules that are actually in R equal to one, they also exist in R equal to three and a half, three halves, excuse me, but they do have a different number, as we saw before, because every time that you move to another space, another neighborhood, the rule number changes. So instead, what I can do with this because they are maintaining the same normalized vector, then I can, if I want to know what is the rule in the bigger space, you know, a rule that I'm looking at in R equal to one, I want to look at it at, I don't know, r equal to 5 or 7 or whatever. All I had to do is move this into the normal space and bring it back on the new R. And here it is, excuse me. This is a table for the 110, 30, 90 and 45. And all I'm doing is converting it to the normal space and bring it back under three halves or bring it back under two. And these are the numbers. Of course, if I take those and I grab the, you know, convert it back to the normal space, they will give me the same number because effectively it is the same function. But we never seen them that way. When we treat them just as integers, they are just different integers. But by using this normalization now, they remain in the same place. Now I can say, instead of, I tell you, say, you know about that Rule 110? And said, yeah, I know, I've heard of it. Yeah, okay. You know, have you heard of the 28,270? No, I never heard of that one. Well, it's the same thing, you know, it's just in the, just in the next space. Well, instead I can just say, do you know about the 1/5 on a 15th? Well, that's in the quiz at the end, by the way. But you know, if you, if you know about that one, you know what that is? And this one is unique. You know, this identifies that function that, that cellular automata, regardless of the neighborhood. And that to me was actually very useful. So that then allows us to, to define what we call the canonical rule. The canonical basically says what is the minimum range value of R under which we can realize a particular normalized rule. So in the case of this, when you take, you know, this one, you Take this one to normal space, you know, it's just of course 110. We make it here in R. We then take the canonical rule and it gives me is a 110 K21. So I can identify that. So if you find an interesting rule in some space, you say canonical rule, and they will actually give you what is the minimum space where that rule exists. Where did it show up first time as you're going up? So in this case, the minimum value of R for the rule, whatever, 1 billion, et cetera, et cetera, and K2, R2, you know, it's actually 110, you know, and I chose that, you know, because I knew what it was going to be. But you can do this with any of those. And then you'll be able to know, you know, what is the minimum, minimum value of R. So this one is another one. I just selected this one. And then you say that three and one, this is the normalized rule. And then it gives you back the same rule, which means this is the minimum value of R under which this particular rule exists. Excuse me. So also that allows us to create what is called a symmetry index. Back when we started working on this, I think it's talking about probably the 90s when they started discussing these things. For k equal to 2 and r equal to 1, we defined symmetric rules. You know, they were perfectly symmetric. We also defined semisymmetric, which is sort of, you know, one side was symmetric and the other side was not. And then totally, you know, asymmetric. So there was no symmetry at all. Now when we work with rules for decay is greater than 2, we end up having that. This characterization is too broad because now the part that is semi symmetric rules are much wider and there are different levels of semi symmetry. And what I define is that, okay, we define a symmetry index sigma for sig, where it's S over K, where S is the number of symmetric genes in the rule divided by the number by K, which is the number of genes or in this case, the number of values in the rule. So we have this, you know, so there's the function that says the symmetric index. We just take, you know, different, different rules under the, you know, we find the symmetric index for each one of those. And I even tried to. This one, this is in, in K plus 7 in R1, you know, that's a little bit bigger. I did a memoir, I said I tried, but. So here we have. This is the symmetry index. You know, for instance, 110 is 1/2 that's semi symmetric. 30 is also 1/2, 90 is totally symmetric. Symmetry index is 1 for this other 1 is also 1 for the next 1 is half, 1/3, 2/3, et cetera. So this particular concept that actually made it to me easier to then generate random rules of various levels of symmetry because all I have to do now is I work for the genes and I make sure that I create or find genes that are symmetric or not symmetric. And I said I need three out of five that will give me a three over five symmetry index. And then I can do something like that. So these functions are in there. So if you want a random symmetric rule and whatever K with whatever R, you just ask for it and then it will give it to you. And you want an asymmetric rule, the same thing. You want a semi asymmetric rule, it will do that as well. Okay, so there is something also that I found. I'm not going to go into the details for this, but there is a way that you find equivalency between two different rules. And these two rules are actually they are equivalent to each other, except that they are shifted, right? The colors are shifted, the output is shifted. And then this particular property, we normally know it as a complement rules in the k equal to 2. So for instance, we can find the modular additive equivalent rule for 110. And this is a 1. This is the shifted is shifted by 1 which is 137 for 30 is 135 for 90 is 165. So this is what we normally see in that as a complement. So 110 is actually 135 as a complement. Or in my case is the modular additive equivalent rule. Why is it that I call it that way is because when you go for K greater than 2, you no longer just have the flipping of the colors, but you actually have the shifting of the colors, which happens to of course the, the, the. The subset of that is the complement in k equal to 2. So this rule, for instance, with respect to this rule over here is every cell, every output is just shifted by one, but they are identical. And this one here, this is separated by one. This is separated by two. And you can do that in any other. In any other space. You can find you say, oh, this is an interesting rule. So what is this one shifted to? This is in the paper. I have it defined as a C modular additive equivalence. So it is equivalent by shifting by a C by a c value. So the interesting thing is that in order for me to do this and Actually find the shifter rule. All I have to do is take the rule from the normal space, move it over to the normalized space, rotate the values of the vector and bring it back to normal space and voila, that's the shifter rule. So there are many operations that actually become easier to do on the normalized space that were kind of hassle when you work on the regular space. All right, so that also allowed me to then start creating some other things. And I was having so much fun when trees became available, because before that I was doing some other ones that it didn't look as pretty. So I created something that I called the genetic trees that basically take a rule, split it into the genes, and then those genes will be also into genes, et cetera. Because remember that since one space is contained on the next bigger space and the next bigger space, etc. So if you take any of the rules from any of these spaces, the genes will actually be functions of the previous or the smaller space, so on and so forth until you get all the way to the end. So in this case you can see that a genetic tree for 110 again is 10 7. And each one of those genes is actually composed of in this case, constants, zero or no, not constants. There is a constant, but there's another one that is not. And this is rule 30, which is six three, this is 90, which is symmetric. Remember, you know, this gives you the Sierpinski triangles. It's actually composed of exactly the same genes, you know, those sides. And then this is the generic, the generic tree for 75, which if you see the, this is just the swapping of the two genes in here, you know, but then that not only allow me to do that. Well, I can do that of course in a genetic tree for a bigger rule, but I didn't want to put another one that was much bigger because I can, I've. I tried this with k equal to 23 and that they're just huge trees. So along the same lines, you know, I actually created the, the equation trees. The equation truth trees is simply using the genetic trees and I'm using some of the functions in trees that you can actually, I can apply a function to the entire tree and it will apply to all the nodes. So here's the equation tree for 110. These are the equations that are actually used for this for each one of these. Again, here's the same equations for these two, etc. This is one for equation three for this one, which is much bigger and the way that this works, I'm just taking the genetic tree and then I apply, you know, the rule equations and gene equations. And I can get those. On top of that I got another one which is the CA evolution tree. And this is for 110. This is the evolution of 110, but this is the evolution of its genes. And each one of those, unfortunately. And I need, I think I need to find the new functionality in terms of the trees because they are getting to be too big. You know, whenever I actually call them, they are all clustered together and I need them to be a little bit more separated. So on top of that there are also canonical trees, normal trees, monotone Q trees, and symmetric index trees. Then there are all kinds of special functions. Identity rule. You can actually get the identity rule in any of the spaces. So this is for 2, 1, 2 3, 31 and 4 and half. And these are the different identity rules that you can realize in the different spaces. The gene rule, that's another one of the rules that I have in here. Gene rule, simply what it does, it takes a gene and it places it in a particular gene of a rule. And then you can indicate that right in here. You say I want 13 to be placed on the gene number 1 for 3, 1. And then it gives you that. If I actually do the normal space of that, you can see that the other parts is zero. But this one here has that gene. 13 is actually 1213 in the normalized space. So as you can see, identity rule in this normalized space is 0000. The vector 0 is always the. It gives you the identity rule when you bring it back to normalized space. The reflect rule. Actually if you have a rule, basically what it does, it takes the rule, then it gives you the reflection of the rule. There are also test functions, can test for monotonicity, symmetry, reversibility test, reflection test, etc. There are some other various functions, such as Langton's lambda parameter. There is also a new parameter that I call delta. There is a rule splice in which you can take a rule from one space and splice it into a bigger rule. And so in this case, what I'm taking is I'm taking Rule 110 and I'm placing it under the. In the identity so that that's the only thing that it has. But in k equal to 3. And then I just, I just show it in here. And as you can see, it looks just like what it is. It's 110, but realized in a bigger space. And of course, the part. The other part. And this other rule is inert. It's not doing anything. So this is the splicing. Splicing of genes from one one space into another space. And actually done this, I put 1, 110 on one side and then I have the reflected on the other side. Then I can actually use the additive equivalent, you know, and then modularity equivalence. Then I can actually have the two rules in the same rule. I've done that for the. With the space of k equal to 4. So that I can put all the two side by side. As you can see here, this is the equation for that. This is the equation without, you know, doing it in through Boolean function, which is in. In. In. In Wolfram, you know, welcome language. And these are the two equations for that. They don't look anything alike, but they actually behave the same. So anyway, the conclusion is, I think I'm providing a sort of organized way of actually exploring cellular automata in a way that I don't think that we've done in the past. Providing a uniform and unified model where we can now move things into a normalized space, do all kinds of operations there, bring them back, which makes it a little bit easier. That's, I think all I have, the time and the packlet will be updated. It doesn't have a lot of documentation, but I will be doing that as soon as I can. Thank you very much.