Become a Creator today!Start creating today - Share your story with the world!
Start for free
00:00:00
00:00:01
27: Peer Pressure (Cellular Automata)
457 Plays6 years ago
The fabric of the natural world is an issue of no small contention: philosophers and truth-seekers universally debate about and study the nature of reality, and exist as long as there are observers in that reality. One topic that has grown from a curiosity to a branch of mathematics within the last century is the topic of cellular automata. Cellular automata are named as such for the simple reason that they involve discrete cells (which hold a (usually finite and countable) range of values) and the cells, over some field we designate as "time", propagate to simple automatic rules. So what can cellular automata do? What have we learned from them? And how could they be involved in the future of the way we view the world?
Recommended
Transcript
Introduction to the Mad Scientist Podcast
00:00:00
Speaker
Real quick, before we get started, we'd like to talk to you about another podcast. It's called the Mad Scientist podcast. And Chris Cogswell was actually on one of the Breaking Math group episodes, BFNB1, if you want to look it up. And they do episodes on a lot of weird paranormal phenomena and how they relate to science.
00:00:22
Speaker
They do episodes, for example, on the color blue, water fluoridation, magical clothing, flat earth theory, even chemtrails. So if you'd like to learn something while learning about these topics that you're going to have to learn about anyway, please check out the Mad Scientist podcast where podcasts are found. And now, time for your feature presentation.
Exploring Cellular Automata
00:00:44
Speaker
The fabric of the natural world is an issue of no small contention. Philosophers and truth seekers universally debate about and study the nature of reality, and exist as long as there are observers in that reality. One topic that has grown from a curiosity to a branch of mathematics within the last century is the topic of cellular automata. Cellular automata are named as such for the simple reason that they involve discrete cells, which hold a usually finite and countable range of values, such as on or off, or a, b, and c.
00:01:12
Speaker
and the cells, over some field we designate as time, propagate using simple automatic rules. So what can cellular automata do? What do we learn from them? And how could they be involved in the future of the way we view the world? All this and more on this episode of Breaking Math.
Meet Chris Burnett from 10 Drink Minimum
00:01:27
Speaker
Episode 27, peer pressure.
00:01:35
Speaker
I'm Jonathan. And I'm Gabriel. And you can find us on Facebook at Breaking Math Podcast, gmail at breakingmathpodcast at gmail.com. Or you could go to our website at breakingmathpodcast.com or you could visit our Twitter at Breaking Math Pod. And with us on today we have... I'm Chris Burnett from the 10 Drink Minimum podcast. Now real quick, how did the podcast get started and what's it all about?
00:02:00
Speaker
Uh, it started about 11 years ago. I was, uh, mowing lawns for a job that I had. And, uh, it's very boring. So I would listen to music on my iPod and after a while I kind of got tired of the music I was listening to. So I went on iTunes and I was just checking things out, you know, and I saw something called podcasts.
00:02:17
Speaker
Is that the era where it was Ricky Gervais show and things like that? Yeah. Uh, uh, Keith and the girl, um, what was the, that was a big one. Um, Dawn and drew those were big ones. And so I started listening to these shows and I was like, well, Hey, these are people doing a radio show from their home.
00:02:33
Speaker
I was like, I could do that. And so, you know, went to Radio Shack and then rest is history. Uh, pretty much I would characterize our show as kind of a beer and lifestyle show. Um, we talk about a lot of craft beer, um, uh, and then just kind of, you know, it's like your friends sitting around after having a couple of beers, just, you know, talking about life in general and everyday things that happen to them. So, and that can be found anywhere podcasts are found. And that again is 10 drink minimum. And you just heard Chris Burnett.
00:03:02
Speaker
I'd also like to mention that 10 Drink Minimum and Breaking Math are both native podcasts from Albuquerque, New Mexico in the United States of America, of course, which is pretty cool. They've been around for quite some time, 11 years, and we just passed our first birthday, so it's pretty cool.
Podcasting in Albuquerque
00:03:20
Speaker
Happy birthday. Yeah, thank you so much. Thank you so much. Yeah, that was back in, well, a little ways, a little while ago, back in February.
00:03:27
Speaker
But I'm very impressed with the podcast scene. It's so cool. There's so many diverse interests, including a podcast about beer and culture, and of course podcasts about math and... Which one's that? Oh, the math one. Crystal math, I think. I'm just kidding. Breaking math. So yeah, we're very glad to have you as a veteran podcast. We're honored to have you on our show. Thanks for showing up. Glad to be here. Now, since you're an honored guest, we're going to give you a chore.
Einstein's View on Time
00:03:53
Speaker
Could you read the Ask Math question, which was submitted by a friend of the show?
00:03:57
Speaker
Okay. Uh, hello, Jonathan and Gabriel. I'm a longtime listener and a big fan of the show. This is my first time sending in a question. I'm curious about a quote from Einstein. Einstein famously had said something along the lines of, despite persistent illusion to the contrary, the dividing line between the past, present and future is an illusion. My question is if time is an illusion, does this violate causality? Thank you very much. And I look forward to your answer.
00:04:25
Speaker
Yeah, it's interesting that this person's writing style is almost exactly like Gabriel's, but I digress. I think that there's two ways to answer the question, the not so fun way and the fun way. The not so fun way says that Einstein was literally just talking about relativity and the non simultaneity of events. Essentially, that's the fact that if you're going very quickly,
00:04:48
Speaker
And let's say you're going very quickly, you get a lot shorter as you go quickly. So if your car is 10 feet long and you're going very close to the speed of light, it might be one foot long. So let's say you see this one foot long car driving along at almost the speed of light, and it enters a garage that's two feet long. And this garage has two garage doors. When it's in the middle of the garage doors, the garage doors close, trapping the car in the garage and then open again, and then the car goes on its way.
00:05:16
Speaker
Now the question is, what would that look like for the people in the car? Because the car is 10 feet long. It doesn't fit in a two foot long garage. So the solution is that it would look like the garage door in front was closing, then opening, then it would go through and the garage door behind it was closing and opening. So events that used to be simultaneous in a different frame of reference are not simultaneous.
00:05:40
Speaker
Fascinating. Yeah, that's fascinating. So basically, as you just said, we're talking about relativity. Now, I think that this writer who, my goodness, you're right, we do have a very similar writing style. I think what also inspired this is when you talk about time and you talk about perspective,
00:06:00
Speaker
From our perspective, we can talk about our past events and every choice that we made and things like, you know, if you chose to go down one hallway and not the other, that has already been done. So, you know, if you were to line up all of the events of your entire life and look at all of them, you would see a clear path. And, you know, this is from a perspective of, let's just say outside of time and looking at what has already happened. The thing is, though,
00:06:25
Speaker
when you are from a given point in a time frame, in a time duration, if you look at the future that hasn't happened yet, you haven't made certain choices yet. So you haven't chosen if you're going to, you know, go one direction or the other. So from that perspective, you can't talk about stepping outside of time because it simply doesn't exist.
00:06:48
Speaker
Now what you're saying is true if you assume one universal frame of reference or time, but as we've seen time and time again, time is not, that was not a purpose. It's not a universal
Mathematics Across Universes
00:07:05
Speaker
thing. Every frame of reference has its own time. So we can see that time is illusory in that sense, but we could go even a little bit further.
00:07:13
Speaker
if we see the history of the universe starting from the big bang at one end of a string and the string curls around does a bunch of loops and stuff and at the end we have the end of the universe we can imagine a slightly more complicated string and a slightly less complicated string and if you listen to our last episode you'll know that things go from less complicated to the more complicated disorder increases so we can imagine this string that represents all of time warping in a new time dimension so
00:07:40
Speaker
I guess the answer is it doesn't violate causality, it appends to it, and it, yeah, I mean, I think that answers their question.
00:07:49
Speaker
Yeah. Hopefully, perhaps we'll hear from this. We'll hear back from this listener again and we'll see if that answers satisfactory. What do you think, Chris? I think you did it well. I don't know. I don't know what you said. I'm like, wow. Well, let's break it down then. Do you have any questions about what I said? Probably about a thousand. Okay. Or again, not to spend a whole lot of time, but just in terms of the original question, how do you feel about the original question and
00:08:15
Speaker
How do you feel about the quote that Einstein quote. Wow, I don't even know how to answer that. Despite the time is an illusion. I, you know, I don't, I don't, you know, have not very good at mathematics I didn't you know I failed algebra so
00:08:31
Speaker
When talking about philosophical things like time is an illusion, for me, that's a very abstract construct that I'm just like, okay, well, okay, I believe you. I don't know how to break it down.
00:08:45
Speaker
Yeah, and what sense is it illusory? I mean, illusions is usually a deviation from the senses. And it's, it's very philosophical. So I see your point. Well, yeah, I mean, you know, from a mathematical perspective, time exists, you know, I mean, this time, you know, the clock on the wall, is it, you know, we get older, we get, you know, passage of time, as in, you know, we see it on our body, we see it on the earth, you know, I don't know, you know,
00:09:13
Speaker
And actually, we have our first real, not that the other one wasn't real, ask math question. And Gabriel can be here to record this because he has a mouthful of food right now. And it goes, hello, I understand that in a multiverse, different universes would obey different laws of physics. Question, would all universes in a multiverse obey the same laws of mathematics? And that was sent in by Pablo C. Now, real quick,
00:09:40
Speaker
The laws of physics would be different. That is true. Although as far as we can tell, they would follow certain systems of laws. For example, the fine structure constant relates different physical constants and how they interact. If we change the fine structure constant, those would interact in a very specific way.
00:10:03
Speaker
It's possible to imagine even more exotic universes and that is true. However, it's almost impossible to imagine different types of mathematics because everything that we can imagine is imagined in a brain that was generated by this universe. So it's very hard to even fathom the question in a meaningful way. I use logic just like everyone else.
00:10:26
Speaker
So I think it is almost imperative to say that this and this question does not have an answer in our universe. Good question, though. And if you want to ask us a question on Ask Math, you could send it to anywhere, Facebook, Gmail or our Twitter. Yeah.
Cellular Automata: Components and Predictability
00:10:47
Speaker
We're going to start with the definition of cellular automata. Next, we're going to talk about grid based cellular automata.
00:10:55
Speaker
And we're going to finish off with a section on John von Neumann's work on cellular automata. So a cellular automata has to have a few different components, and one of those is a topology. Now the word topology to some people reminds them of the fact that a donut and a coffee cup are topologically identical. Have you heard of that, Chris? Yeah, they're both round when you look from the top.
00:11:20
Speaker
Well, not necessarily like that. It's because if you made a donut out of clay, you could deform the clay into the shape of a mug without poking holes in it. And that's what they're topologically identical. Oh, I see. But what we're talking about is a very different type of topology and it's graph-based topology. And a graph is a set of nodes connected by arrows or lines.
00:11:46
Speaker
So a grid is an example of a topology because if you at the intersection of every cross, if you put a point there, then you have points connected by lines, right? Right. Another topology might be hexagons. Another topology might just be a random like bunch of stuff. You can have fractal topologies, but it just has to have a definition. Okay.
00:12:06
Speaker
And usually the topology is infinite or unbounded but finite, meaning that it doesn't have edges that some things just disappear off of. It goes forever. Next, there's a set of possible values.
00:12:23
Speaker
So each dot on this topology on this graph has a possible value. Maybe those values are A, B, and C. Maybe they're on and off, but it has to have a set of possible values. So am I making it clear that there's a different value at every intersection on a grid or something like that? Like telling it what to do.
00:12:47
Speaker
Well, not necessarily what to do, what to be. Because what to do is the next part. Because you need two sets of rules. Given any node, you have to figure out which nodes are important to that node.
00:12:59
Speaker
So in a grid, it might be the eight neighbors of the point, the top, bottom, left, right, and the four diagonals. And other topologies might have different rules. But then you have to have a rule for generating new values from those nodes' values. So if I tell you that the neighbors are A, B, C, B, B, and A, we have to have a rule that says, oh, yeah, next time it's going to be B. Does that make sense?
00:13:26
Speaker
Yeah. Okay. Yeah. So essentially the components of cellular automata include the first thing is a typology, which is just talking about the shapes of the cells. The second thing is a set of possible values for each of the cells. And lastly, you need a set of rules for describing how the cells interact with their neighbors. And in this case, it's just their immediate neighbors. I don't think they're concerned with cells that are further away, not adjacent.
00:13:54
Speaker
Now, what you've described is a most cellular automata does follow those rules that you just laid out where you were. It was the nearest neighbors. The neighbors literally touching the thing and the topology is based on the shape of the cells. But the topology doesn't have to be based on the shape of the cells unless they tessellate it or fit together on a plane. What was that one?
00:14:17
Speaker
Yeah, tessellate, like, you know, like, um, let you ever play like, with like those little, um, like squares and triangles as a kid, and you put them into weird patterns, that's tessellation. Okay. And, uh, so that's how most of them work, but you could have a topology that's, for example, non-euclidean hyperbolic, where it doesn't fit onto a grid. It maybe fits onto a sphere.
00:14:36
Speaker
Would it still have to, by the way, just for our listeners sake, I am very much new to this area. So I hope that my clarifying questions are helpful for those who are not as familiar with cellular automata. So in the case of a hyperbolic cellular automata, would they still have to be touching just in a different way? Like not on a flat plane, but on a
00:15:00
Speaker
On a hyperbolic surface, they could still be touching. There are ways to tessellate things in a hyperbolic space with seven sides. We're not going to go into that because it's complicated. But Escher used that in his paintings. You ever seen the painting where it's like a circle and it gets smaller and smaller towards the edges? That's a hyperbolic space.
00:15:22
Speaker
What I'm hearing correct in the sense that basically the idea that I'm trying to get around is that for the math to work or for the functions to work in a cellular automata program, they don't necessarily have to touch. They just have to have the right rules that describe the behavior. Describe their relationships between the cells. Okay. So I mean, it could be, it could be like, for example, a tree structure that could be the topology for cellular automata.
00:15:50
Speaker
Okay, now in the example of let's just say chess, if you were to describe how a pawn takes out an opponent, that does require them to be tangential, but also at the diagonal, which I guess... Yeah, and in that case, if you just imagine the grid,
00:16:11
Speaker
Just put diagonals in the grid. So across every box, draw an X in every box. Got it. That's the topology for what's called the game of life that we'll go over in two sections from now. OK. I think I'm following. I think I'm following.
00:16:28
Speaker
And weirdly importantly, but it's, it seems obvious, but, and that's why I left till the end is that you have to have a starting position or arrangement. So that's where you assign a different value to every node in the topology. This reminds me a lot of our evolutionary algorithm that we programmed last year or other similar programs. And it makes me wonder what would happen if, if every single value was, it was identical at the beginning of a cellular automata.
00:16:56
Speaker
Actually, that's pretty interesting because if you look at, if you go to our episode TMI about information theory, you'll see that a set of ones and a set of zeros are just equally uninteresting. It kind of works the same way in cellular automata. There's actually a lot to do with chaos and randomness, but really the starting positions for interesting cellular automata have to be themselves interesting.
00:17:20
Speaker
Okay. So in other words, you wouldn't want all the same starting position. You would want a little bit of chaos. That's why in some example, like if we wrote a program here where, you know, we had Chris, uh, I guess draw his name, Chris, where it basically, uh, where it marked those squares were darkened, uh, that added some change, some entropy to it.
00:17:41
Speaker
Yeah, and I wouldn't say that you need to start out with chaos. You need to start off with structure. But yeah, that's what you need for cellular automata. But one thing that I really want to stress about cellular automata is that they're 100% predictable. There's no such thing. I mean, okay, there are cellular automata that have random rules, but those are a different thing entirely. They're usually a strict set of rules. They're like chess, not like poker.
00:18:07
Speaker
So what you're saying is what looks like chaos actually isn't chaos. You know where it's actually going to go if you really broke down and got into it and did the actual, you know.
00:18:17
Speaker
What's weird is that chaos and what I said actually do work simultaneously because chaos has to do more with sensitivity to initial conditions. So for example, as we'll see in a bit, some very smart cellular automata. And if you imagine these like a person reading a sentence, if I read the sentence, the blue sheep went to the store, it's a different sentence than the sheep went to the store.
00:18:46
Speaker
So the understanding will be different and the whole thought process or chaotic process where you want to call it will be different. I like your analogy of a sheep going to the store. How'd you come up with that? Because I went to the store the other day and I tried to imagine something that could be blue. And for some reason my mind came up with sheep. I thought you were going to say you went to the store and there was a blue sheep there. And I was like, wow, what story? The sheep store.
00:19:13
Speaker
For this next part of the podcast, we're going to talk about a researcher who is quite famous called Dr.
Dr. Steven Wolfram's Contributions
00:19:20
Speaker
Steven Wolfram. He's a very interesting guy. He actually wrote a paper when he was 18 on corks, which has been very, very hot.
00:19:28
Speaker
highly cited. And for those who may or may not be aware, quarks are the subatomic particles that make up protons and neutrons. So that's what I was wondering. I was like, what are quarks? Yeah. Yeah. Very, very interesting stuff. We should do an episode on quarks because then you can do, you know, we can talk about, well, what are quarks? We can then talk about what are quarks made out of and that gets very interesting. So yeah. So Dr. Steven Wolfram wrote about quarks when he was very young. He also developed the program Mathematica.
00:19:55
Speaker
There's also an online version of Mathematica or like Mathematica Lite called Wolfram Alpha, which you may have used. And it's really cool. Gabriel, if you type in the sentence ratio between population of Albuquerque and population of Denver into Wolfram Alpha, go there, do that real quick. Cool. I've done that. So it says that the result is for the ratio between the population of Albuquerque and the population of Denver is 0.807.
00:20:23
Speaker
And if you look at the next thing, it's like graph of the popular of the ratio. So it'll tell it like it does the stuff on the fly. It's really goodness. Yeah. It shows from even before 1995 up until the end of the graph is actually about 2016 looks like it doesn't show how much better our green chili is than theirs. It doesn't show that at all.
00:20:41
Speaker
They don't have green chili. You know what? For all of our listeners, green chili from New Mexico is superb. It's a little spicy, but you put green chili on your hamburgers or on your scrambled eggs. They think they do. Yeah. It's phenomenal. And recently, Colorado has been growing some green chili. They've been doing it wrong because they're not us. Exactly. Exactly.
00:20:59
Speaker
But essentially, yeah, so he's a researcher, and one of the things that he researched a lot of was cellular automata. And he did a lot of research, and he wrote a book. This episode is all about cellular automata, which is a field of discrete math. To get you ready for this kind of math, our partner, billion.org, has a course on number theory, which will help you learn things like modular arithmetic and factorization, which have close analogs in cellular automata.
00:21:27
Speaker
Actively working through these problems is sure to get you up to speed. To support your educational journey in math, go to brilliant.org slash breaking math and sign up for free. The first 200 breaking math listeners get 20% off the annual subscription, which we've been using. And now back to the episode. That's right. The book was called a new kind of science. And in that book, in that book, basically he talked a lot about cellular autonomy and his work, right?
00:21:52
Speaker
Yeah. And one of the things from the book is that he separates all cellular automata into four different classes based on their long-term behavior. And in a new kind of science, he talks about different classes of cellular automata and he breaks them into four different classes. That's right. The first class of cellular automata that he talks about is a type that settles down into a homogeneous state, which is much like a pond where you throw in some stones and eventually it turns into a flat surface.
00:22:22
Speaker
These are the least interesting cellular automata. They basically don't have any interesting behavior and they don't have any long-term behavior.
00:22:28
Speaker
But it is a cellular automata in the sense that the ripple spreads in all of the cells or all the water molecules at the surface. Oh yeah, you can model that as a cellular automata where maybe like the height is the value that the cells have, the height of the water. Interesting. Chris, do you want to read our next class? Some randomness stays and the structures that developed are either stable or oscillate. This is like throwing a bomb to a guard tower where the guards are given orders to stay calm and be routine.
00:22:55
Speaker
Were you inspired by playing Call of Duty? It was actually inspired by Wolfenstein. What's that movie about the orcs and all that? Lord of the Rings. Where they have a battle at one point and they light stuff and everybody does chaotic stuff but then they form a new structure entirely.
00:23:17
Speaker
And that's what happens with these. There's some oscillators, which means that maybe some guards are walking around a perimeter. There's some stable structures, which might be like a phalanx. So that's what the solar automata are. And then obviously, and again, I realize this is a bit of a cryptic example here, but in the example where there's a bomb and probably anybody who is in the proximity, the bomb would be running away from it. Like in other words, breaking order.
00:23:42
Speaker
Oh yeah, the bomb represents more in this case, in this analogy, a source of information, a source of randomness or entropy. Okay, nice, interesting.
00:23:55
Speaker
So then there's a third one, where most patterns behave chaotically, and the whole structure tends to be more or less sensitive to initial conditions equally. So these are really chaotic ones, and nearly all patterns evolve in a pseudo-random manner. And I say pseudo-random because there is some predictability to some of these patterns, but more often than not they're unpredictable.
00:24:17
Speaker
So this brings me back to our second episode ever of Breaking Math, Reaking Chaos. So when we talk about just a chaotic system, you mean something like weather? Oh yeah, something like weather where the flap of butterflies wings will change the order of tornadoes in the world. They won't change how many tornadoes are, but it'll change when they happen. Okay. Now, and again, what I'm trying to do is be clear about what differentiation is this third class from the previous class.
00:24:44
Speaker
This one is different because it's literally like in the last class, the guards after a while, they go, they, they settle into a new routine, right? Okay. Okay. But in this one, local changes to the pattern tend to spread indefinitely. Okay. So it's like running through a group of pigeons. The pigeons affect other pigeons and then it just spreads chaotically.
00:25:02
Speaker
Okay. Okay. And again, again, I fully realize this is a dark example, but this would be like if there are maybe multiple grenades hurled into the guard tower over time. Uh, gosh, I need a, I need a less dark example here. I think the guard example is better for number two because the guards have their orders and they know how to reorder themselves. And this one it's that I choose chose pigeons because it was a, because they're dumb animals. No offense pigeons.
00:25:28
Speaker
For our last class, I'd also like to hand that off to our guest. Number four, less random than number three, and conjectured to be capable of universal computation. These patterns from the most interesting, if lengthy, long-term behavior. This is like the universe. Wow, sorry. This is like the all-encompassing class. I could easily have read that and thought, what did I just read? Yeah, that's kind of what I'm at.
00:25:55
Speaker
Now, basically what universal computation is, it's the principle that no computer can do something that another computer cannot do. Every computer can simulate every other computer if it has enough memory. And in these patterns, if you put the right cells on or off or change them to AB in the right order, you could basically build a computer within the simulation. And you could actually simulate the simulation within the simulation.
00:26:23
Speaker
Okay, so this is actually applicable to some of the recent, if perhaps outlandish things said by Elon Musk, where he talks about our universe actually being a simulation. Or maybe another example would be the phenomenal episode of Rick and Morty in which he makes a car battery that's actually a small universe. And in that universe, they produce energy.
00:26:42
Speaker
A little bit, but in that case, he had an accelerated unbounded vacuum. In this case, it would get slower technically each time. Of course. Of course. How did I overlook that? So what you're saying is like, if you have a computer, then you could virtually inside that computer build another computer.
00:26:57
Speaker
Yeah, and you could build the same computer, but it would be a little slower, right? Right, of course. Because you're simulating the wires of the computer already has with fake wires. Right. And you can imagine simulating that computer on itself like a third layer, right? Right. Wow. You could do that infinitely. It would get slower every time.
00:27:15
Speaker
Yeah. And the thing is about these though, is that they're not that common, these patterns. Most are one, two, and three. Number four has that we still don't know what characterizes these. Um, we just, uh, we don't even know if they're all capable of universal computation, but Stephen Wolfram thinks so. And, uh, I happen to think so. So those are the four, um, classes of cellular automata. Man, I want to, I actually sincerely would like to go into Photoshop and make examples of all four of those. Maybe I will.
00:27:43
Speaker
And again, so since I see these, these grids and you know, this kind of behavior, I think of even things like rashes on your skin. Could that be considered cellular at Hama?
00:27:51
Speaker
In that case, I mean, I'll just build a quick cellular automata that you might be able to simulate. Imagine you just put a bunch of dots on your skin, connect them with lines. If more than a third of the dots connected to a line are infected, then that dot becomes infected. But if it's infected for more than three generations, it starts to heal.
00:28:15
Speaker
I didn't make that rigorous, that's an exercise left to the reader, but that's an example of the cellular automata that simulates that kind of system. I love to leave exercises to the reader. They're such a, reminds me of my old math textbooks. If you have a game of life pattern that simulates a computer, let's say you just kind of like throw a wrench in the pattern, like you turn the cell off that was on or A that was B in the wrong place, that has a potential to destroy the entire computation slowly.
00:28:43
Speaker
like from the inside out. So that would be more of a flaw in a pattern in the cellular automata. But there's really cool things you could do with them, as we'll see in the next section. Crazy.
00:28:56
Speaker
All right, now we're going to talk about grid-based cellular automata.
Grid-Based Cellular Automata Models
00:29:01
Speaker
We went over what it would look like in two dimensions, but we're going to go even simpler. We're going to do one-dimensional cellular automata, where time is more of a spatial dimension. So an example of a cellular automata that you can generate is the Sierpinski triangle. Chris, are you familiar? I've never heard of it.
00:29:22
Speaker
The Sierpinski triangle, you ever draw a triangle and then you draw an upside down triangle that divides into four different triangles? Yes. And then you keep going that with the. Yeah. Like the tri force, right? Yeah. Like that's, that's, this generates a Sierpinski triangle rule 22 is what it's called. And it's called 22 because if you look at this, if you look at the neighbors of a cell and the cell itself, there's three different cells there, right? Yes. And the cell can either be on or off in these, uh, binary grid based cellular automata that we're talking about.
00:29:52
Speaker
So what you have to do is if you imagine time as being like the vertical axis, you could just say that every time there's a new generation, you just add a new row. So what you do for every square is you look at the one above it, the one to up into the right and the one up into the left.
00:30:12
Speaker
And if all three are one, which is the binary number seven, then it's off. If it's one, one, zero, it's zero, et cetera. And the pattern is zero, zero, zero, one, zero, one, one, zero. Now that sounded like gibberish, obviously. So I'm going to break that down.
00:30:31
Speaker
In this case, what it means is that if the one up and to the left is on and the other two are off, then the cell is on. If the cell is on itself and the other two are off, then the one below it just turns on the same way. And if only the one to the right is on, then it turns on, but otherwise it's off. Interesting. So what I was trying to follow along, and I kind of lost you just a little bit. I was trying to think about the rule, like the AND and OR, like are these AND or ORs?
00:31:00
Speaker
Um, in this case, it would be a variant on an exclusive or gate, I think. Okay. Okay. Um, yeah. Uh, because what I was thinking of based on, you know, if it's triangular based on the location, it would have two, I guess you'd call them parents. Well, it's not triangular. It's a grid, but each one is based on the one above it, the one to the up and to the left and the one up and to the right. Okay. Okay. Got it. Got it. If you draw a dots, then because the one, then the next row will be three dots. Okay.
00:31:27
Speaker
and then it'll grow into a Sierpinski triangle. Okay. Okay. I got it. Cool. Cool. So yeah. And as you said earlier, this, this basically can be summarized as, uh, you said earlier these zero, zero, zero, one, zero, one, one, zero, which in binary is 22. Yay. Awesome. Okay. Yeah. That makes sense.
00:31:43
Speaker
The rule 22 would be an example of a rule of a class two automata, because if you have kind of a random starting position, you'll have like things that look like Serpitsky triangle stuff, but it's going to look a little random. So the random is kind of stays the amount of information stays. It doesn't dissipate. It doesn't turn to nothing. Okay.
00:32:04
Speaker
And that's in contrast to a Rule 3 cellular automata. Remember Rule 3 is chaotic, almost pure chaotic behavior. And if you're near a computer, just search the term Rule 30.
00:32:17
Speaker
Okay. Interesting. Of course, as we said earlier from the, from the president rule 30 probably has a representation in binary. And I'm sorry, did you see that rule 30 corresponds with class three, class three. Okay. Okay. No, Chris, you have a picture of rule 30 in front of you. Yes. Um, what, what, what, what can you describe it to the listeners?
00:32:34
Speaker
It is a triangle that's kind of bisected down the middle. On one side it looks like there's a pattern going one direction and then on the other side the pattern is very chaotic.
00:32:49
Speaker
Yeah. That's why I see it. I don't know. It's very chaotic. So, to me, this almost looks like as Chris exactly said. So, yeah, the left side to me, it looks like tire tracks where everything is in one direction like like one tire drove over the whole thing and you got all these. Yeah. And on the right side, it's just gravel almost but but but when you look up, when you zoom in, it's a bunch of
00:33:06
Speaker
triangles of varying sizes. Yes. Yes. And a random places too. Right. Yeah. Yes. And what's interesting about this pattern is that for a while it was conjecture that it could be used as a random number generator. Okay. After a while it turned out that that was wrong. Oh, interesting. Yeah. There are patterns that could be found very wrong. Okay. So, so here's my question tonight. Is it, is it more random than pseudo random? Cause I know that pseudo random that our computers use isn't really random either.
00:33:31
Speaker
Oh, you know, this is completely deterministic, so it's just as pseudo-random. Okay, interesting. And this pattern is actually found in nature, in the Conestexteela mollusc shell. The Conestexteela mollusc grows in a spiral shape, so it has generations that go down, and you have a picture of the mollusc in front of you.
00:33:52
Speaker
Yeah. It is pretty much that. Yeah. Yeah. You see the same triangles and everything. So with this mollusk shell, clearly, as we've all seen with shells, especially seashells, they are based on a certain repeating spiral. I've seen in the past, I think a lot of folks are familiar with the Fibonacci spirals, which this may, may or may not be. I don't know. It's not really Fibonacci. It's a very random pattern. Okay. It just happened to show up one place in nature.
00:34:18
Speaker
Okay. Oh, and I was in that case, I was talking more about the physical shape of the shell, not the pattern on the shell. Oh, I see. Yeah, the pattern on the physical shape of the shell is very predictable, but the pattern on top of it is very chaotic. Okay. Yeah, that's that's interesting. So yeah, it's like if you were to turn this into pixels, then you have either a rule 20 or a rule 30 or some other rule and you get this crazy pattern, which is it. Heck, it is cool. It's it's pretty.
00:34:45
Speaker
Yeah, that's very interesting how, you know, there is some, it looks like there's a pattern, but it's not like you'll have like the larger triangles, but then there's like a line of triangles that kind of go up at an angle. And then there's just places where there aren't any at all. That's very interesting. Oh, yeah, for sure. And I want you to do something real quick. Do you have a sheet of paper or two credit cards with you? No, the credit card here. I will loan you my credit cards here. Is this a wise move? Is this a wise move? Let me just log in Amazon real quick.
00:35:12
Speaker
Now put one credit card on the class 30 rule and put it on the random side of the screen. And what's funny is I'm completely cognizant of the fact that we're doing a very visual concept on an auditory podcast. Yeah, just put it on the screen and then put the next credit card next to it so that there's about one pixel of separation.
00:35:34
Speaker
you'll notice that there's no pattern, no discernible pattern in a strip of this pattern. Oh, okay. So with the two credit, I see what you're doing. Two credit cards, put them together. So you only see one single strip and we're looking for a pattern in there. What do you see? Um, I don't know. Can they read your fortune if you interpret?
00:35:50
Speaker
I mean, I don't really see a pattern in it. Yeah, there's no pattern. Yeah. So even though the triangles look like they're kind of forming a pattern, really, if you look at the way this is distributed, it's totally random. I see. Yeah. Kind of same thing with like reading tea leaves, right? A little bit. Yeah.
00:36:05
Speaker
Hey, that's real, man. Reading. We should do that. Wouldn't it be horrible if somebody decided to make a fortune teller app that was just cellular autonomous? I bet there are some. I'm sure there are. Okay. Okay. And then say vague things like you will experience a surprise today. When will it come? It's a surprise. And then so we have now two dimensional cellular automata. And one of the most famous ones is the game of life.
John Conway's Game of Life
00:36:32
Speaker
This is so fascinating. I love the term the game of life because I've seen this before and it is a cellular time. And I think that the idea here is that this can arguably simulate all of life, right? Yeah. It is a class four pattern. It's capable of universal computation. So anything that could be computed on a computer like the universe, arguably. Yes.
00:36:56
Speaker
um can be simulated in the game of life that might be troubling you know depending on how you look at it just just this whole argument that all of life and all of its complexities and relationships and changes can be broken down so so is this i mean like i guess my my question is um
00:37:12
Speaker
Is it arguable that this like is it tongue-in-cheek game of life or are people saying it? Well, the reason why it's called the game of life is because it was originally Designed as instead of those cells being on and off. We're gonna call them living and dead. Okay. Okay. I see Okay, this isn't some existential spiral No, okay. Okay when Conway came up with it. He didn't know that it was capable of universal computation He just thought it was cool. Okay, okay
00:37:38
Speaker
So, so, so in this case, strictly speaking, to clarify my previous question, this is called the game of life because the cells are not zeros and ones, but rather they're called living and dead. Yeah. That's essentially it. It's just, uh, I mean, he could have called it, um, you could have called it like super Moss or awaken asleep or something. Yep. Okay. And, but we're going to use alive and dead. So every, so just imagine an infinite grid and every cell has eight neighbors, right?
00:38:06
Speaker
So if it's eight neighbors, then, uh, is an individual cell, then it's not going to be a square. It's going to be a, uh, no, it's a square, but it could go diagonal too. Got it. Okay. So the diagonals do count then. So yes. Okay.
00:38:18
Speaker
And so if a cell has less than two living neighbors, it dies because it goes extinct. It's underpopulated. Okay. So it's, it's lonely and it's depressed and it dies. If it has two, uh, oh, sorry, two or under, or is it under two? So, so if it's one or less, I understand. Yes. If it has more than three, so four or more living cells, then it dies in the next generation because of overcrowding or because it was already dead.
00:38:48
Speaker
Oh, okay. Got it. Okay. If it has exactly three neighbors, though, no matter if it's alive or dead, it becomes alive in the next generation or stays alive. Sorry. If it, if it has, Oh, so in this game of life, dead things can come back to life.
00:39:02
Speaker
Yeah. And that's kind of like breeding, like almost. Okay. Okay. I got it. So, and you're saying is, uh, if a cell has exactly three neighbors that are alive. Yeah. Understood. And if it has exactly two neighbors that are alive, there's no change in the state. It, um, if alive cells stay alive and dead cells stay dead, but there's not anything we really care about. Wow. That does sound pretty crazy. So obviously we can't do an infinite grid. We can only do a finite grid, but I, this still has me very curious as to what it would look like if we,
00:39:31
Speaker
Well, we could see, we can simulate an infinite grid because we only have to keep track of the cells that are on and their coordinates. And as long as we don't have an infinitely large pattern that has infinite information, we could simulate it on an infinite grid. Okay. Very good. Well, we have that opportunity. Yeah, totally. We're going to do that in just a second. And, but first I think we should tell the listeners how to play the game of life on a checkers board. Like some of the original people did this.
00:39:59
Speaker
Okay, very good, very good. So if you don't have a fancy, schmancy computer that all the kids have these days. So you start with two different markers, let's say, beans and pennies. And then, let's say we have a pattern on the board with just pennies, where pennies represent live cells.
00:40:15
Speaker
So this is your starting or current position. And then what you do is you put two beans on the cells, which will be alive in the next generation and one bean on the cell that will be dead in the next generation.
00:40:30
Speaker
So now I know which cells you visited and which ones you haven't because the ones that you haven't that you have visited all have beans. Okay, then all you do is you go out you you go through and you take off all the all the pennies and then you take off one bean of each cell and you repeat this.
00:40:47
Speaker
Yeah. And then that's how you play it at home. Yep. Are you going to go home and do this? No, Chris. It takes an absurd amount of patience to do this by hand. It took me like a week to figure out how to find. I had like a like a bunch of graph paper that was just scribbles because I was trying to figure out life patterns without a computer.
00:41:06
Speaker
So, so you, so, so this is the kind of thing that Jonathan does in his free time, in case you're wondering, he tries to do his secular autonomous on his own. Awesome. Very, very glad that people like you do this. We will take your live vicariously through you. Take your word for it. Yeah. Don't take my word for it. Try it at home, but if you're babysitting and you want to occupy your kids for a while.
00:41:27
Speaker
And it was invented by John Conway, who's a mathematician. As I recall, he's done some work in group theory that might not be correct, but this is a major contribution of his that
00:41:43
Speaker
He seems to be a little bit, um, a little bit annoyed that it got so big. I mean, interviews, he seems a little annoyed to me. Well, he's annoyed that sailor autonomous. So the game of life, because he didn't invent solar autonomous. He just invented the game of life. Okay. Okay. Okay. I kind of took on a life of its own. Yep. If you model the popularity of the game of life using cellular sailor autonomous.
00:42:04
Speaker
So just to show you the kind of cool things that exist in the game of life, there's a whole vocabulary that is sprung up and communities that have sprung up about the game of life. And there are things called still lifes. And these have the property that in the next generation, they stay exactly the same as they were before.
00:42:26
Speaker
They have fun names like the loaf, or the tub, or the boat. And these are very simple patterns. They're just a few live cells, but they have the property that they stay that way. They do, yeah. A loaf, like a loaf of bread? Yeah, it kind of looks like a loaf of bread. Interesting. So I'm looking at pictures here of these still lives. These are just like, what is this grid? Like a six by six grid, and you just have a few of them shaded in. So you've got like a, looks like a crooked smiley face or something. Yeah.
00:42:56
Speaker
Or even an old Atari Asteroids. Yeah, Asteroids ship or something.
00:43:02
Speaker
Okay. Then there's what are called Gardens of Eden. And they have the property that they're impossible to generate from a previous pattern. They're called that because only God, which is the person making the patterns, could have designed them. That's kind of cool. That sounds powerful. So this tells us real quick about this simulation that it might be infinitely, potentially complex, but it's not all-encompassing. You can't generate every single pattern using the game of life.
00:43:31
Speaker
some patterns are impossible to generate from others. Interesting, interesting. And then there's also a pattern here I'm reading called oscillators. And I think that breaks down into two subcategories. There's a category here called oscillators. For example, there are blinkers, which have a period of two, which means that they go from one state to the next one and then back again. So it goes dun, dun, dun, dun.
00:43:55
Speaker
Oh, like blink, like, yeah, they blink. They just blink. Yeah, they blink. And then there's another kind of oscillator here called a pentadecath... I'm sorry, what? Pentadecathlon. Pentadecathlon, which is not a dinosaur. It has a period of 15. Yeah, which means that it takes 15 generations to get back to its original form. And that can be said of any of the forms within it. Interesting. So as an oscillator, though, it always returns back to its original form.
00:44:22
Speaker
Yeah, exactly. Back to its original form. Unlike Pokemon, but perhaps like, like the Incredible Hulk, maybe. I don't know. Not familiar enough with the Hulk. He can go back to human after a while. Oh, like that. Okay. Yeah, I get it now. Okay. And then there's, uh, there's other examples here. One of them here is called, uh, looks like spaceships.
00:44:43
Speaker
And these are oscillators where when it gets back to its original state, it's displaced. So it might be like one cell up into the right or one cell down to the left. They basically move. The pattern moves over time. We've got a few examples of spaceships. You want to read those, Chris? A glider and a LWSS or lightweight spaceship.
00:45:02
Speaker
And these are small patterns. They actually kind of form spontaneously. I bet that, man, this is cool. I kind of want to be part of the culture of the game of life. That would be fun. And Minecraft. I wonder how many, how much game of life you could do with Minecraft. Is that possible? Oh yeah. I hate that I know this, but you just need a lot of redstone.
00:45:21
Speaker
So very good. Now we're going to open up the game of life and do a quick simulation, uh, open up your game of life and delete everything. Sure. Absolutely. Okay. So I have a game of life right here. I'm going to walk my audience through it. Um, so I've opened it and what's the delete all, uh, just, uh, control and then delete. Okay. So I've got this game of life simulation pulled open.
00:45:45
Speaker
So the pattern we're going to be exploring is called the arpentomino. And it encapsulates a lot about the game of life itself. OK, so here we go. And I've got the pencil. So two across, two down. OK.
00:45:57
Speaker
Now what's cool about this pattern is that it's a very simple starting pattern, but it has very chaotic behavior that stabilizes after a while. It starts with five cells, hence the name pentomino, and it ends with 1103 different cells. So why don't you press play on the simulation?
00:46:19
Speaker
Okay. Um, never tried to teach your aunt or grandma how to use the Facebook. It's like, okay, where's play here? Whoa. It's like, almost looks like explosions all over the place. Yeah. And then there's the little gliders that are flying off the bottom and one off the top.
00:46:35
Speaker
Yeah. So you see these stuff from spontaneously. I think all of our listeners, let me tell you with full enthusiasm, get yourself a game of cellular autonomous and bring it to your next Tinder date. It's Epic. Yeah. Okay. So I misspoke earlier. It has a 11,103 generations until it stabilizes with the final population of 116, not 103. So yeah, it's kind of stopped. It's not doing a whole lot now. Yeah. So it's stabilized. Yep, exactly.
00:47:01
Speaker
Now, um, if you'd like to see, um, the game of life, either go to breaking math podcast.com slash game of life.html. Um, or you could go download a program called golly and that'll allow you to do your own patterns. Yes. That's a golly as in what you would hear your grandma say when she drops her tea.
00:47:23
Speaker
Yeah, and the goal uses algorithm called hash life, which can simulate very large things. You could simulate literally, I think one time I simulated one to the 120 generations of this one pattern. It's a very efficient algorithm. But as soon as you throw a wrench into it, as soon as it gets more interesting, it slows down. Wow.
00:47:49
Speaker
So it's a very conservative algorithm, but it's a lot about that. And we don't have time to go into it because it's a very complicated algorithm. But if you are algorithmically inclined, check out HashLife. Asmostar. Nice. Awesome. Now the last thing we're going to talk about is a really cool cellular automata.
Von Neumann's Universal Replicator
00:48:08
Speaker
It's one of the first ones ever made. It was made in the 40s by John von Neumann. And instead of having two states on and off, it had 29 different states.
00:48:16
Speaker
uh, depending on the function of the cell. Um, and each, and each one had like complex rules. It was a very, it's a very complicated thing. Um, but it's, it's, uh, capable of universal replication. And he did this without a computer. He used graph paper to design this incredibly complex system. I bet his wife love that. What's that? I bet his wife love that. I'm not sure if you're married now. Okay. Yeah.
00:48:43
Speaker
Now, the way that the universal replicator works, and any universal replicator, including ones that do exist within the game of life and actually are preloaded into GALI, work on the principle of quines. And we've talked about quines before. An example of a quine is yields the sentence when preceded by its quotation.
00:49:02
Speaker
So a quotation is just quoting something, it turns anything into a noun. But hello in quotes is a different word than hello, because hello in quotes is a reference. So that's what quoting is, and it's integral to this. And the reason why it works is because he basically just made a machine that could generate any pattern that could be generated using a tape. And the tape had a pattern for the original thing, including the pattern for the tape.
00:49:27
Speaker
And so this, this will make a copy of itself and a copy of the copy and it will keep making infinite copies of itself. Wow. Can I feel like once again, Godel Escherbach, you know, rears its head. Like these, these concepts are everywhere. Oh yeah. He talks extensively about coins. That's right. And then they also have a strange loop representation.
00:49:45
Speaker
Yeah, because yeah, Quine is also the type of computer program that could output its own code. And you always have to kind of like an internal machine that generates written code and what I call a strange loop representation, which is basically you have to represent the code within the code and it's very tricky. It's a good exercise for aspiring computer scientists though.
00:50:09
Speaker
Cellular automata, as we've shown, have the potential for very simple behavior, but also very complex behavior, that emerges from very simple rules. This is why cellular automata have been conjectured by some to be integral to the structure of the universe. Whether this is true or not, the field, like many we cover here on Breaking Math, is very new and very fertile, and there's a lot of research going on even at the amateur level. I'm Jonathan. And I'm Gabriel. And this has been Breaking Math. Today we head on
00:50:38
Speaker
Chris Burnett. And Chris, do you want to plug your show again? Yeah, my show's 10 Drink Minimum. We're on any kind of podcast catcher, iTunes, Facebook, all the cool social media sites.
00:50:50
Speaker
I gotta say something. What I found just really, really fun is when you actually go on, in this case, probably YouTube or Facebook, and you watch your live stream, you can interact with Chris and ask him questions live. It's exciting. There's something exciting about seeing someone on TV responding to your questions. And we try to make it very audience-based. Nice. And how often do you come up with new shows?
00:51:14
Speaker
We try to do at least four shows a month. And we do at least usually about once a month. We're out and about somewhere, whether it's a brewery or a festival or something. Nice. So watch out for 10 drink minimum and listen to them. They're great. And if you are interested in Conway's Game of Life, then just go to Conwaylife.com and you'll find a wiki, a whole community dedicated to the Game of Life. Yeah. Cool, man.
00:51:42
Speaker
Awesome. I know I'm dedicated to the game of life. That sounds like a cult. Are you dedicated? Are you dedicated?