Langton's Loops: The cellular automaton that copies itself
ฝัง
- เผยแพร่เมื่อ 22 พ.ค. 2024
- An introduction to cellular automata, including Conway's Game of Life and the self-replicating Langton's Loops. Several animations are shown, including the eventual self-destruction that would result if Langton's Loops were allowed to replicate on a large torus (where opposite sides of the grid are joined together).
Ending background music:
/ replicating-loops
If you're curious to learn more...
Tremendous set of figures (about 1500!) discovered for Conway's Game of Life:
conwaylife.com/ref/lexicon/le...
A working Turing machine in Conway's Game of Life?! Yeah:
rendell-attic.org/gol/tm.htm
Introductory information on Langton's Loops:
en.wikipedia.org/wiki/Langton...
The full rule set for Langton's Loops:
github.com/GollyGang/ruletabl...
Links to rule sets for other interesting cellular automata:
github.com/gollygang/ruletabl...
Source code for an example implementation (though not the one used in this video):
diga.me.uk/LangtonLoops.html
00:00 Introduction
00:24 Game of Life introduction
01:22 Game of Life rules
02:20 Game of Life in action
04:17 Langton's Loops introduction
05:04 Langton's Loops rules
06:33 Langton's Loops slow, small animation
07:26 Grid with wrap-around (torus)
09:04 Langton's Loops full animation
I love the style of this video. It's like an old-school educational tape. The music, the language, the pauses, the demonstrations. Everything is just right.
The sounds of the arrows at 1:00 are so reminiscent of VHS tapes
so true mason
It's why I love Boards of Canada. Just has this really comfy old analogue vibe. Edit: listen to ROYGBIV to see what I mean!
It's too bad that evoloop always evolves to be smaller and simpler in stable populations. Though you might be able to evolve evoloops of different sizes by other evolutionary pressures.
You can actually observe this in nature. In stable conditions, bacteria and especially viruses can experience a huge reduction in genes as they optimize their reproduction to be as fast and efficient as possible
@@juergenkern6763Kewl!
@@geekzombie8795bros watched a few too many South Park shorts
I would have to assume that if a Langton's Loop were to grow on a torus of just the right size, it would reach a stable state wherein it does not destroy itself. But I'd probably have to see for myself.
Why would you assume that? It seems to break whenever it comes into contact with anything other than empty space, which it inevitably will on a non-infinite board.
@@anthonymercuri8885 Because if you look at how each of the cells terminate their self replication it's by touching an already exsiting cell first. So if the grid was exactly the right size it'd be as if it had already had 4 neighbours.
Exactly as @@Hopefighter says.
Unfortunately, having just played around with this, I couldn't get it to not destroy itself, inevitably (in my testing at least), 2 loops would attempt to connect to eachother at the same time, destroying them both. Sorry to say, I was hoping they'd nicely create completed loops as well
@@Hopefightereven with 4 neighbors the center one is dead, if they all have “4 neighbors” with just the right size they’d just be dead
Great video! I had seen Conway's game of life before, but didn't realise there were more complex systems based on the same idea. You did a great job explaining how the rules work too. 8 colours and 219 rules sounds very overwhelming but with your explanation it's easier to grasp the concept!
Fantastic. Thanks for the kind words.
@@davbrdavbr what's the website name? so I can make langton's loop
Extremely fascinating. imposing constraints on the cells brings further interesting behavior, you can imagine the edge cases serving as the 'skin' of a multicellular organism with differential expression on the surface and in the bulk.
Watching the loops was like watching healthy cells encounter an illness that spread between them or like how the outer layers of skin will choose to die of in order to form a protective barrier for the ones below
Made me immediately think of cancer. "Look, the cell is just trying to do what it does. It's not smart enough to realize what it's doing is really bad."
Judging by most of the comments being somewhat recent, it looks like you just hit the algorithm, congrats!
That being said, its been a minute since you posted this, but please consider making more videos! This was really well made and interesting!!
Also the music was a great touch, it seemed to perfectly fit the animation, very early-Hayao-Miyazaki-film-esque
Yeah, it's been very surprising seeing views and comments come from nowhere after a year and a half of silence. 🙂 Glad you enjoyed the vid and the music, thanks for the comment!
@@davbrdavbr can I ask where I can find the track?? I really enjoyed it!!
it's*
@@matthewszklany101 Ending background music now available: soundcloud.com/david_broman/replicating-loops
@@davbrdavbrThe track is beautiful, by the way
4:50
I only need 2 states, and 1 rule.
"If on, all neighbours turn on"
Hence a single dot self replicates endlessly :D
simpler rule: if off, turn on
Congrats, you created cancer
sounds like cancer 😅
@@wisteria3032 Cancer is the final form of life. What is the purpose of living if not replicating and spreading? Cancer is unchecked growth. It is reproduction without limitation. One day there will be nothing left in the universe but cancer and entropy.
@@imaMONKE725 That doesn't sound self-replicating
I was hoping you would show a version where the grid size of the replicator was aligned. At a guess, there should be a size where the attempt to expand sees the opposite direction's interference as "already been here" and skips it, or perhaps concludes it doesn't need to do anymore and maybe misses some spots, but otherwise looks like the inf plane's done state.
That Langton Loop isn't sightreadable at all.
gd colon wtf did you do
what a throwback. I had a conways game of life app on my mam’s ipad as a kid and it has all these presets including loads of ones like this. was so fun to explore and build my own circuits with them
one of the coolest presets using this rule set was a read-write circuit that would sent out a red tube parallel to a line of information, then turn a corner and touch the information one at a time. it then encodes the info and sends it back to the circuit which then was converted into the DNA to go off somewhere else and build another red tunnel and place that information down and then retract the tunnel. so it copy pasted the information indefinitely
This was extremely well put together. Very clear and does not waste the viewers time. Would love to see more
Kind words, thank you!
Cellular automata are so fascinating, and they always blow me away with the patterns they make. Math is beautiful. Awesome music too! I loved it!
I'm glad you enjoyed! Thanks for the comment.
Ending background music now available: soundcloud.com/david_broman/replicating-loops
o:
There are rules in there that do not work though... at 6:37 the bottom right cyan cell has a rule of 71120 but 71120 does not exist in the rule set
Wow, someone is really paying attention! 😀 There is one thing I neglected to mention, for simplicity's sake, which is that the rule set is interpreted with 90-degree rotational symmetry. That means each rule is actually 4 rules in one, where you "rotate" the second, third, fourth, and fifth digits in all four possible configurations, while keeping the final (result) digit the same. So if
CTRLBO (center/top/right/left/bottom/output)
is a rule, then the following are rules as well:
CRLBTO
CLBTRO
CBTRLO
So while it is true there is no rule that begins with 71120, there IS a rule that would apply to that cyan square at 6:37, which is this one:
701120
@@davbrdavbr That makes much more sense thank you
F U N K Y SQAURE!
@@sharificleshow did you spot that?
@@lollol-tt3fx I was implementing Langton loops for a project so I was familiar with the rules
YT randomly deciding to suggest me this banger/ hypnotic video for no reason.
Loved it.
Glad you enjoyed!
Only 9000 views? This is extremely underrated...
cellular automata have always been really interesting to be. so many games can and have been made out of the same idea: a grid of cells with different states changing depending on some rules
Watching this has super made want to program a game of life. So interesting. Also had no idea what cellular automata were before this explanation. Great video!
I really like how you explained the cellular autonoma, and your music was excellent, especially at the end
Great video. The music changing to mirror what's being shown tickles my brain in just the right way.
Thanks, glad you enjoyed!
the algorithm has found you, my friend
That's what I said!!
so true
I honestly don't know what on earth happened the past couple of weeks. This video went from "total obscurity" to "fairly obscure" in a short amount of time. 🙂
I remember the first time I ever played the Game of Life as a child. I was messing about on my father's linux PC (KDE, I think it was?), and I found a games section, with all the classics like Tux Kart. I saw "Game of Life" and thought it was a digital implementation of the board game, which I loved so I booted it up. And then I got lost in it for hours.
Love the video!! Would definitely be interested in more neat programming/logic videos like this one :D
MAN, the music you made for it is awesome!!
Glad you enjoyed! There's a link to it in the description
No way I just watched a 12 minute video about cellular automatons, but can’t pay attention in math class 💀💀💀
Perhaps you like math more than you realized. 🙂
Will the loop tile nicely if the grid is a multiple of the loop size, or will it always corrupt at the edges?
Someone else also proposed the idea of varying the grid size. It does make me curious...
@@davbrdavbr Oh, I'm certain that it would make a significant difference! These rules are far from random; they were designed to yield exactly the results shown for an infinite surface. Significantly, they "know" when to stop reproducing gracefully when the inner portion is "full". So, if the grid is an exact multiple, one assumes that they'd bump into older structures at their "expected" locations, and thus stop reproducing as if they were in the original scenario.
It's funny; I started getting interested in this as a very young child in the early 70's, when (most) people had to draw each generation manually using grid paper. This was one of the things that got me interested in computers, as it quickly got boring to do this by hand, yet the overall ideas were exciting.
Holy shit the algorithm has blessed me
nice video cant belive it has so few views
the way people make those big moving "organisms" really reminds me of flying machines in minecraft. a bunch of tiny parts that all move and interact with each other to make the entire unit glide.
Fantastic video! I've been thinking about self-replication lately, because that must be how life started and evolved from there. Would be interesting to see if you put a tiny bit of noise around Langton's Loops if anything would evolve. Most would surely just stop replicating.
Interesting. You do get some noise already in this video (in a way, at least) as the wraparound starts to take effect, and loops on the edge collide with loops from the opposite side. And indeed, it is quite destructive.
Lore has it that men think about self-replication about every 7 seconds. (The actual average is 19 times per day)
I'll show myself out now.
oh I love cellular automata, lovely things and so entertaining to learn about. great video
Kinda sounds like a turing-machine as it can read and write values, but with the difference, that changes are applied to all memory-cells at the same time. Cool.
And, of course, someone has created a Game of Life organism that IS a Turing Machine. You can find a video of it out there somewhere, and it's amazingly intricate.
Fascinating and well-explained.
that whole thing about looping the area was unnecessary, but the rest of the video was interesting
Awesome video!! I think there's probably some subtlety in how the size of the grid is picked, no? I wonder the modulus of the grid size and the automatons periodic length has any effect on the stability/instability of the system
Did you do the music yourself ?? amazing ! It fits what's currently happening in the automaton ! great video
Yes I did, and I'm glad you enjoyed. Thanks for the comment!
@@davbrdavbris it programmatically generated? It really is very good!
Ending background music now available: soundcloud.com/david_broman/replicating-loops
@@julian1000 No, the music was composed the old fashioned way (by a human). 🙂
Now add decay. Any block left unchanged for x amount of evolutions dies. Then the surrounding blocks can change it again.
Beautiful patterns
You are one of the best engineering educators on this platform. what is your Patreon?
Thank you very much! No Patreon, just glad you enjoyed.
criminally underrated
I'm really curious to see how different grid sizes change the way the program halts or gets stuck in a loop. Maybe there's a grid size which lets the square generators recycle some material instead of just crashing.
This was a really cool video!!! Thanks so much!!
Bro, I watched this a while ago and didn’t comment, but i checked my liked list and I found this vid. Nice to see it got a big bump in views. It’s nice to see the algorithm boosting good vids.
Thank you for mentioning! No idea what happened with the algorithm. You'd think after a year goes by the algorithm is no longer interested in experimenting with pushing a video. But I guess not.
The loop getting corrupted when it meets itself gives me a weird icky feeling
Factory must grow
if you make the screen size any amount divisible by 11 on both sides i think the result might become a bit more tame
I'd assume so, yeah. That way the squares wouldn't crash into each other.
A couple others have also proposed varying the grid size. It does make me curious to see!
@1:01 whoa, did you really use the _Rugrats_ theme song for the "numbering" of the 'alive' squares? Was that on purpose, or just random chance?
Either way, I love it 😂
Never watched Rugrats, so I had to listen to see what you're talking about. And yeah, the instrument and the use of thirds are similar. Pretty funny coincidence!
I can create a self-replicating pattern with just two states and one rule!
"If at least one neighbor is alive, a dead cell becomes alive."
The starting pattern is a single live cell.
I doubt that a growing cross is what mathematicians studying cellular automatons call a "replicating pattern".
How can your rule work if the starting pattern is a single living cell when it looks for a living neighbour.
@@Dj2xPhe didnt say a live cell becomes dead if no neighbouring cells are alive
that would be the most uninteresting pattern
@@Dj2xPthe dead cells around the living cell find a living cell, become alive, and then that keeps happening
I would love to see the idea of decay, as suggested by Dusty_Moonpie, but I'd also like to see just how many rules and colours you'd need to have the loops, when they come together, instead of killing each other, rather reforming and creating a double, triple, etc, loop
I am now utterly fascinated by cellular automata.
Wow this is very interesting! Althiugh i feel like the issues with this when the edges are connected could be prevented if the pixels had conciousness, but knowing that it'll prob never be made as its nearly impossible
I loved this. This video made my brain tingle haha
cool! thanks for sharing. nice vid
Can you please tell me where did you get the music from? I love it and was wondering weather its yours or just where is it from.
Please its such a banger!!
It is mine, glad you liked! I've gotten enough comments on it that I'll try to make it available.
Ending background music now available: soundcloud.com/david_broman/replicating-loops
Great video! Inspired me to recreate it in Python!
Where can I get the soundtrack? 😊
The soundtrack is just some music I put together for this video, so you won't find it anywhere else, at least for now. Hope you enjoyed!
Ending background music now available: soundcloud.com/david_broman/replicating-loops
incredible
What happens when you vary the grid size by 1? Is it something interesting? Or have you already tried and tested very option < the loop width + padding?
I expect that if the pattern is a correct multiple of the cell size it would tile correctly
This is a great idea for something to try. Maybe someday...
You don't have to do a full scale simulation with a 100x100 grid like you did in the video. A 5x5 should be big enough. At it should run 400x faster per frame and probably 20x less frames. So 8000x less time than the full grid, assuming you use the CPU @@davbrdavbr
abiogenesis, embryology, growth of the body, cellular replacement, stunted development, cancer, old age. this loop explains it all. it even occurs in the same order in which it happens in humans! dude did langton just solve all of these riddles???? why am i just now hearing about this loop a year after this video was posted
So if during their division or post-division regeneration, the cells get interrupted, they get corrupted. What would happen if at the end you put some corrupted mass in the center of the cellular tissue (i.e. replaced some fragment of it)? Would only the closely-affected cells get corrupted, containing the intrusion/protecting other ones OR would the infection spread to the vast majority of cells?
what if you make the grid fit exactly? do all of them become stable and blue?
Pro tip: When programming simulators for Conway's game of life or any grid-based game like this, I find it easiest to make the grid data structure one unit larger on both sides and set the border values to 0xFF or something like that. This is essentially a 3rd state that tells the algorithm "Treat me as a dead neighbor but don't bring me to life"
I would love to see this run with random mutations or some simple algorithm to induce a subtle but expected change
I can make a 1d cellular automata that is self replicating with only 2 states. If a dead cell is next to a live cell it turns live, it infinitely makes the same pattern of one live cell.
To make a musical composition based on the 'dance' of the automaton was a really nice touch :)
Thanks! 🙂
The glider factory was always my favorite.
explaination from another universe
Thank you for share!
i love the music
Thank you! Ending background music now available: soundcloud.com/david_broman/replicating-loops
Is it possible to fix the area at 8:02 in width and height? That it is maybe W:44 H:44
starting point (of your figure) would be with:
- 6 empty pixels from left
- 17 empty pixel from the top
What would it end up than?
Can you please try this for me?
great music
It seems we need more rules to account for this. Or at the very least, a kill switch. This sort of thing is a very dangerous concept when applied to AGI.
That smoke alarm beep in the music hurt my ears
You gotta upload that music, i love it
Thanks! In the description there's a link to the ending song on SoundCloud.
Did you make the background music? I love it!
I did, thank you! I just made it available here: soundcloud.com/david_broman/replicating-loops
I really liked this video :)
can you make the backround ending music but on youtube pls
nice
could i get the source code used by you in this video?
The music is really good, is there a full list?
Thanks! The music is just stuff I wrote for this video. Only the ending music was long enough to publish as its own thing (link in the description). The rest was just too short to be worth it.
On an unrelated note, can you provide links to background music used in the video, please?
Thanks for asking! I made the music especially for this video, and never uploaded it anywhere else. Since a few have asked about it, I may eventually try to dig it up and publish somewhere.
Ending background music now available: soundcloud.com/david_broman/replicating-loops
Great content! Well done!!
So perhaps analogous of stem cells growing/dividing into a defined cell based on DNA boundaries?
8:50 i think it matters how many cells you have in x and y size, if i did not miscalculate you had at least 41 cells in diameter. Perhaps try to increase decrease the size. Will it be possible to bring it to a nicer halt this way?
what's the update order of the grid?
Ahh yess...
the Magical battery that allows one to make a superheated Lazer on paintool
There is more water in this video than in my cup of tea. Ah, yes, 12:00 duration, the minimal required to to enable monetization
Cell Machine too!
Very cool
what would a "super-GOL" look like? instead of looking at the 8 neighbors around it, you look at the 8 neighbors AND the next layer with 16 squares, and you just scale the GOL rules proportionately
Is this music written for the video? It fits too well!
Yes it is!
this is good
The skin cells in my body trying desperately to stop me from pouring sulphuric acid on me
RIP Dr. Conway
Getting some Rugrats vibes from your sound effects lol
Might be a way to build dense microprocessors
This makes me think about how this could apply to the real world, with things like cancer and things like war
Now we just need to ontroduce the chance of an error in the rules and see what happens.
the outcome of the failure state might be highly dependent on the offset at which opposite sides hit. too bad we only got to see a few examples when there are 11 different possibilities for the x- and 7 for the y-offset! maybe there are other oscillating "alive" states left to discover.
Cell Machine on crack: