Langton's Loops: The cellular automaton that copies itself

Подписаться 2,2 тыс.

Просмотров 431 тыс.

0% 0

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

Опубликовано:

25 июн 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 315

@mason-pe5lk 5 месяцев назад

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.

@rojastegulu 5 месяцев назад

The sounds of the arrows at 1:00 are so reminiscent of VHS tapes

@Anohaxer 5 месяцев назад

so true mason

@madbeef. 4 месяца назад

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!

@alynnzz0491 5 месяцев назад

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.

@anthonymercuri8885 5 месяцев назад

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.

@Hopefighter 5 месяцев назад

@@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.

@alynnzz0491 4 месяца назад

Exactly as @@Hopefighter says.

@katriellesalmon7629 4 месяца назад

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

@zar1s_278 4 месяца назад

@@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

@petersmythe6462 5 месяцев назад

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.

@juergenkern6763 5 месяцев назад

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

@Kero-zc5tc 3 месяца назад

@@geekzombie8795bros watched a few too many South Park shorts

@bennetsheckells6741 27 дней назад

@@juergenkern6763oh cool.

@bowel_movement 5 месяцев назад

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!

@davbrdavbr 5 месяцев назад

Fantastic. Thanks for the kind words.

@tristan_davies10 4 месяца назад

@@davbrdavbr what's the website name? so I can make langton's loop

@MaxWeinhold 5 месяцев назад

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.

@MrZylix-6 5 месяцев назад

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

@DavidSikesII 2 месяца назад

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."

@josefinae1403 12 дней назад

Except the algorithm didn't "choose" to do anything.

@BurgerSoda 19 дней назад

When you think about it, the glider is somewhat depressing. It’s cells that reproduce to somewhere else and then die, just to move their offspring to somewhere where they too will meet the same end.

@matthewszklany101 5 месяцев назад

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

@davbrdavbr 5 месяцев назад

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!

@matthewszklany101 5 месяцев назад

@@davbrdavbr can I ask where I can find the track?? I really enjoyed it!!

@JorgetePanete 5 месяцев назад

it's*

@davbrdavbr 5 месяцев назад

@@matthewszklany101 Ending background music now available: soundcloud.com/david_broman/replicating-loops

@novarender_ 5 месяцев назад

@@davbrdavbrThe track is beautiful, by the way

@theketchupboii 4 месяца назад

That Langton Loop isn't sightreadable at all.

@ThrowableCube Месяц назад

gd colon wtf did you do

@Slicethemic 22 дня назад

Get out of my headGet out of my headGet out of my headGet out of my headGet out of my headGet out of my headGet out of my headGet out of my headGet out of my headGet out of my headGet out of my headGet out of my headGet out of my headGet out of my headGet out of my headGet out of my headGet out of my headGet out of my headGet out of my head

@star-ir6df 3 дня назад

____ | | |__ |

@fgvcosmic6752 5 месяцев назад

<a href="#" class="seekto" data-time="290">4:50</a> I only need 2 states, and 1 rule. "If on, all neighbours turn on" Hence a single dot self replicates endlessly :D

@imaMONKE725 4 месяца назад

simpler rule: if off, turn on

@TheSeptet 4 месяца назад

Congrats, you created cancer

@wisteria3032 4 месяца назад

sounds like cancer 😅

@chrismanuel9768 3 месяца назад

@@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.

@GynxShinx 2 месяца назад

@@imaMONKE725 That doesn't sound self-replicating

@Untoldanimations 5 месяцев назад

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

@matts2700 5 месяцев назад

This was extremely well put together. Very clear and does not waste the viewers time. Would love to see more

@davbrdavbr 5 месяцев назад

Kind words, thank you!

@singh.ayushman 5 месяцев назад

YT randomly deciding to suggest me this banger/ hypnotic video for no reason. Loved it.

@davbrdavbr 5 месяцев назад

Glad you enjoyed!

@QuantaBee 5 месяцев назад

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!

@davbrdavbr 5 месяцев назад

I'm glad you enjoyed! Thanks for the comment.

@davbrdavbr 5 месяцев назад

Ending background music now available: soundcloud.com/david_broman/replicating-loops

@sillypinkmoth 5 месяцев назад

@memoryleaked 5 месяцев назад

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.

@wiseSYW 5 месяцев назад

the algorithm has found you, my friend

@matthewszklany101 5 месяцев назад

That's what I said!!

@EirPlen 5 месяцев назад

so true

@davbrdavbr 5 месяцев назад

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. 🙂

@aryst0krat 5 месяцев назад

The loop getting corrupted when it meets itself gives me a weird icky feeling

@sharificles Год назад

There are rules in there that do not work though... at <a href="#" class="seekto" data-time="397">6:37</a> the bottom right cyan cell has a rule of 71120 but 71120 does not exist in the rule set

@davbrdavbr Год назад

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

@sharificles Год назад

@@davbrdavbr That makes much more sense thank you

@zekejanczewski7275 6 месяцев назад

F U N K Y SQAURE!

@lollol-tt3fx 6 месяцев назад

@@sharificleshow did you spot that?

@sharificles 6 месяцев назад

@@lollol-tt3fx I was implementing Langton loops for a project so I was familiar with the rules

@destroyerofnuggets3644 5 месяцев назад

Great video. The music changing to mirror what's being shown tickles my brain in just the right way.

@davbrdavbr 5 месяцев назад

Thanks, glad you enjoyed!

5 месяцев назад

Only 9000 views? This is extremely underrated...

@MatthewStevensOrMattDave 5 месяцев назад

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!

@goldfishglory 5 месяцев назад

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

@casualbird7671 5 месяцев назад

I really like how you explained the cellular autonoma, and your music was excellent, especially at the end

@Cyanadeo 2 месяца назад

No way I just watched a 12 minute video about cellular automatons, but can’t pay attention in math class 💀💀💀

@davbrdavbr Месяц назад

Perhaps you like math more than you realized. 🙂

@kianheus2487 5 месяцев назад

Love the video!! Would definitely be interested in more neat programming/logic videos like this one :D

@neologicalgamer3437 9 месяцев назад

Holy shit the algorithm has blessed me

@Chocomint_Queen 5 месяцев назад

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.

@Drawland2012 5 месяцев назад

MAN, the music you made for it is awesome!!

@davbrdavbr 5 месяцев назад

Glad you enjoyed! There's a link to it in the description

@duckified. 5 месяцев назад

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.

@thecloudwyrm7966 5 месяцев назад

oh I love cellular automata, lovely things and so entertaining to learn about. great video

@PepijndeVos 5 месяцев назад

Will the loop tile nicely if the grid is a multiple of the loop size, or will it always corrupt at the edges?

@davbrdavbr 5 месяцев назад

Someone else also proposed the idea of varying the grid size. It does make me curious...

@d4b 5 месяцев назад

@@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.

@Dusty_Moonpie 5 месяцев назад

Now add decay. Any block left unchanged for x amount of evolutions dies. Then the surrounding blocks can change it again.

@brandontylerburt 5 месяцев назад

Fascinating and well-explained.

@DominicGo 5 месяцев назад

criminally underrated

@il2626 Год назад

nice video cant belive it has so few views

@NoName-oz3gj 4 месяца назад

Beautiful patterns

@godlypumpkin8745 5 месяцев назад

Factory must grow

@thriller2910 5 месяцев назад

This was a really cool video!!! Thanks so much!!

@davidmartin3772 4 месяца назад

I am now utterly fascinated by cellular automata.

@roarkeburnett8208 5 месяцев назад

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

@skaleee1207 5 месяцев назад

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.

@davbrdavbr 5 месяцев назад

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.

@soupnowplease3825 5 месяцев назад

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.

@davbrdavbr 5 месяцев назад

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.

@karlkastor 5 месяцев назад

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.

@davbrdavbr 5 месяцев назад

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.

@AdelaeR 5 месяцев назад

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.

@cynabonabelle 5 месяцев назад

I loved this. This video made my brain tingle haha

@MonsieurBiga 5 месяцев назад

Did you do the music yourself ?? amazing ! It fits what's currently happening in the automaton ! great video

@davbrdavbr 5 месяцев назад

Yes I did, and I'm glad you enjoyed. Thanks for the comment!

@julian1000 5 месяцев назад

@@davbrdavbris it programmatically generated? It really is very good!

@davbrdavbr 5 месяцев назад

Ending background music now available: soundcloud.com/david_broman/replicating-loops

@davbrdavbr 5 месяцев назад

@@julian1000 No, the music was composed the old fashioned way (by a human). 🙂

@fenderrexfender 23 дня назад

I would love to see a Finished rendering of the end product but with different angled borders animated

@Hoggagf2 5 месяцев назад

if you make the screen size any amount divisible by 11 on both sides i think the result might become a bit more tame

@Sluppie 5 месяцев назад

I'd assume so, yeah. That way the squares wouldn't crash into each other.

@davbrdavbr 5 месяцев назад

A couple others have also proposed varying the grid size. It does make me curious to see!

@uplink-on-yt 5 месяцев назад

Where can I get the soundtrack? 😊

@davbrdavbr 5 месяцев назад

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!

@davbrdavbr 5 месяцев назад

Ending background music now available: soundcloud.com/david_broman/replicating-loops

@PeterSserwangaShow 2 месяца назад

You are one of the best engineering educators on this platform. what is your Patreon?

@davbrdavbr Месяц назад

Thank you very much! No Patreon, just glad you enjoyed.

@PopeGoliath 5 месяцев назад

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.

@GonogoBonobo 5 месяцев назад

I doubt that a growing cross is what mathematicians studying cellular automatons call a "replicating pattern".

@Dj2xP 5 месяцев назад

How can your rule work if the starting pattern is a single living cell when it looks for a living neighbour.

@papetoast 5 месяцев назад

@@Dj2xPhe didnt say a live cell becomes dead if no neighbouring cells are alive

@wiseSYW 5 месяцев назад

that would be the most uninteresting pattern

@DetectiveWraith 5 месяцев назад

@@Dj2xPthe dead cells around the living cell find a living cell, become alive, and then that keeps happening

@km077 5 месяцев назад

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?

@jansustar4565 5 месяцев назад

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?

@satibel 5 месяцев назад

I expect that if the pattern is a correct multiple of the cell size it would tile correctly

@davbrdavbr 5 месяцев назад

This is a great idea for something to try. Maybe someday...

@jansustar4565 5 месяцев назад

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

@kokosensei5231 5 месяцев назад

Thank you for share!

@rogercruz1547 5 месяцев назад

what if you make the grid fit exactly? do all of them become stable and blue?

@amnesia7077 5 месяцев назад

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

@hidebehind3565 5 месяцев назад

I really liked this video :)

@d.lawrencemiller5755 5 месяцев назад

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.

@TuncanGaming 5 месяцев назад

cool! thanks for sharing. nice vid

@gijs5443 5 месяцев назад

To make a musical composition based on the 'dance' of the automaton was a really nice touch :)

@davbrdavbr 5 месяцев назад

Thanks! 🙂

@Rising_Pho3nix_23 5 месяцев назад

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

@programmingpillars6805 5 месяцев назад

explaination from another universe

@thildamoon 5 месяцев назад

Is it possible to fix the area at <a href="#" class="seekto" data-time="482">8:02</a> 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?

@aze4308 5 месяцев назад

incredible

@bloop_yipee 5 месяцев назад

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

@pkaser 2 месяца назад

I would love to see this run with random mutations or some simple algorithm to induce a subtle but expected change

@danieljohnson2393 5 месяцев назад

Great video! Inspired me to recreate it in Python!

@ralph3333 5 месяцев назад

The glider factory was always my favorite.

@williamdrum9899 3 месяца назад

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"

@Plazix999 4 месяца назад

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.

@CjqNslXUcM 4 месяца назад

great music

@Pockeywn 5 месяцев назад

i love the music

@davbrdavbr 5 месяцев назад

Thank you! Ending background music now available: soundcloud.com/david_broman/replicating-loops

@1Kapachow1 5 месяцев назад

Great content! Well done!!

@idontwantahandlethough 5 месяцев назад

@<a href="#" class="seekto" data-time="61">1:01</a> 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 😂

@davbrdavbr 5 месяцев назад

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!

@basilfeitknecht6430 5 месяцев назад

could i get the source code used by you in this video?

@GillAndBurtTheCop 5 месяцев назад

That smoke alarm beep in the music hurt my ears

@KennethTylerSon 3 месяца назад

You gotta upload that music, i love it

@davbrdavbr 3 месяца назад

Thanks! In the description there's a link to the ending song on SoundCloud.

@Halo56782 5 месяцев назад

The music is really good, is there a full list?

@davbrdavbr 5 месяцев назад

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.

@user-hi8jv6cw8n 5 месяцев назад

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!!

@davbrdavbr 5 месяцев назад

It is mine, glad you liked! I've gotten enough comments on it that I'll try to make it available.

@davbrdavbr 5 месяцев назад

Ending background music now available: soundcloud.com/david_broman/replicating-loops

@fomxgorl 4 месяца назад

what's the update order of the grid?

@NonTwinBrothers 5 месяцев назад

Dang, no mentions of Golly in the vid

@PolishRepublicYT 5 месяцев назад

can you make the backround ending music but on youtube pls

@josugambee3701 2 месяца назад

Is this music written for the video? It fits too well!

@davbrdavbr Месяц назад

Yes it is!

@GrimblyGoo 5 месяцев назад

Very cool

@CEOGities 5 месяцев назад

Did you make the background music? I love it!

@davbrdavbr 5 месяцев назад

I did, thank you! I just made it available here: soundcloud.com/david_broman/replicating-loops

@eminkilicaslan8945 5 месяцев назад

Only 60 comments, this video needs more attention.

@ExSpoonman 5 месяцев назад

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.

@JoseCarlos-dn6nx Год назад

nice

@sayyidassons9332 5 месяцев назад

this is good

@xuko6792 5 месяцев назад

On an unrelated note, can you provide links to background music used in the video, please?

@davbrdavbr 5 месяцев назад

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.

@davbrdavbr 5 месяцев назад

Ending background music now available: soundcloud.com/david_broman/replicating-loops

@FxTR22 4 месяца назад

<a href="#" class="seekto" data-time="530">8:50</a> 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?