[Laser] Firing squad synchronization problem

The video shows a theoretical problem in computer science and a solution for it. It is presented as a riddle, but note it's not easy to solve.
The shown solution is based on the first solution proposed for this problem. It requires ~3n steps, and 17 states.
See list of states and some additional information here: www.udiprod.co...

[@defaultusername9596]

“Yeah, we had some budget cuts this year, so we can’t go with the executioner robots.” “What are we using, then?” “The dancers.”

[@samuelding7854]

Hey, at least they’re programmable

[@koltrol4370]

I think it‘s the different way a round

[@Totally_Bonkers]

how are there TWO replies and 2k likes

[@ctdaniels7049]

The Clone Wars in a nutshell!

[@t-rex1019]

Roger Roger Now launching, Just Dance!

[@ya_boi_salami]

imagine being sentenced to death by a robot autocracy, and the last thing you see before you die is your executioners just grooving

[@thepiratepeter4630]

The war of the sorting robots

[@yonatanbeer3475]

"Sargent, give the order." "Yes sir." *Bonk* "What are they doing, Sargent" "Grooving, sir"

[@TheJamesM]

The goofiest dystopia.

[@godlikefish1193]

If it's execution by groovin robots I'd be more than willing to accept my fate

[@unexpected2475]

Instead of being blindfolded, you get a nice visual before you get fucking murdered.

[@seanproctor7830]

“Here’s a robot firing squad” is possibly the most ominous first line in any KZbin video

[@Natonada]

LMAO

[@MarieAmeliaFreyaAster]

Tom Scott

[@someguy70]

*proceeds to activate robot firing squad that is facing towards you*

[@Chineseisntalanguageapparently]

But very effective

[@EndEverEsports]

“vsauce, Michael here”

[@onebigchumptm4729]

I cannot stop laughing at the idea of someone who’s been sentenced to death by robot firing squad, screaming bloody murder while these robots just boogie down to upbeat royalty free music

[@ironmatic1]

well it's more or less an abstraction of the Colonel Bogey March, hardly royalty free style.

[@TegukiSix]

Huh, that's a neat solution. Mine was to use an iterator at the end of the line, but I'm not sure if that breaks the "finite poses" rule: - Build an arbitrary list of poses greater than the number of robots. - Robot 1 assumes the pose that says "I am number 1!" - Each idle robot looks to its right and assumes the pose one higher than that (unless right is also idle). - When you get to the end, you've counted all the robots! - The last robot (which sees a blank space next to it) begins ticking down through all the poses ("blank left & not idle = my pose - 1"). - Each other robot, when it sees a robot with the same pose on its left, ticks down one pose. - When the robots declare "We are number 1!" ("I am number 1 & left is number 1") they're ready to tick over into "Firin' ma lazor!".

[@bushbaby4421]

It specifically mentions a squad of any FINITE size, so I would argue your solution is more elegant and exactly where my head went with this one!

[@Poldovico]

​​​needs to work for ANY finite size of squad, but you have to define A finite amount of poses in your solution. If you can find a finite quantity that is greater than any other finite quantity, hit me up.

[@aa01blue38]

It does break the finite poses rule, as there must be one finite set of poses and rules that works for ALL finite squads, -- so no matter how many poses you have, there is a squad with more robots than you have poses.

[@ugielka]

@@aa01blue38yeah but i can also come up with one more pose than your biggest squad. even with countably infinite robots i could come up with countably infinite poses and one more

[@jackeea_]

everybody gangsta until the firing squad starts dancing

[@pvic6959]

imagine youre been sentenced to firing squad and you have to stand there watching for 30 min while they dance and figure out when to fire

[@forregom]

This is a pretty effective intimidation tactic

[@ClokworkGremlin]

It's like being executed by the Ginyu Force.

[@alansmithee419]

@@pvic6959 They do a full musical number about their lives as members of a firing squad, and your death comes on the last beat of the song.

[@traceyjacobsen8544]

I don't think anybody gangsta if your on the receiving end of the firing squad

[@shaunyap4090]

Imagine being on death row for committing several war crimes, and you're sentenced to death via firing squad. As an extra punishment, they have you executed via 128 robot soldiers that do this, and at 15 BPM

[@jebediahkerman8245]

Stop trying to escape! We have to reset the process every time you do that.

[@Yui714]

I would love this. thank you.

[@blarghinatelazer9394]

The fucking suspense that would create

[@The_Epicness9000]

Alright, let’s take out some math and see how long it would take. Seeing as the BPM is 15, one beat will take 4 seconds, so we will multiply the number of beats by 4 to get the time in seconds. We now check if 128 is a perfect power of 2. It is, being the 7th power of 2. We don’t need any double general rules. The first hand signal will take 3n/2 beats to propagate to the end and back to the middle. Our squad is 128 robots, so 3(128)/2 = 192 beats. Our squad is now split into subsquads of 64 robots. 3(64)/2 = 96 beats. 192 + 96 = 288 beats so far. Now we have subsquads of 32. But here’s where we employ a neat trick. Because our squad size has been divided by 2 each time, so has our number of steps to division. We can simply divide the previous number of steps by 2. 96 / 2 = 48 beats. We can verify this fact by also evaluating the old steps formula. 3(32)/2 = 48 = 96 / 2. 288 + 48 = 336 beats so far. Subsquads of 16. 48 / 2 = 24. 336 + 24 = 360 steps so far. Subsquads of 8. 24 / 2 = 12. 360 + 12 = 372 beats so far. Subsquads of 4. 12 / 2 = 6. 372 + 6 = 378 beats so far. Subsquads of 2. 6 / 2 = 3. 378 + 3 = 381 beats so far. Now we simply add 1, representing our final firing order, to get a grand total of 382 beats from start to firing. Now let’s evaluate the time in seconds. We simply multiply our number of beats by 4 to get 1528 seconds. Now how long is that in seconds _and_ minutes? One minute is 60 seconds, so we divide 1528 by 60, keeping the remainder as the number of seconds. We get our final answer of an insane *25 minutes 28 seconds.*

[@mrosskne]

and the first cycle is a sike

[@25usd94]

Its important to have all the robots fire at the same time so that any individual robot won't feel guilty from knowing they had pulled the killing shot.

[@iwomartofel1849]

Guitly, or perhaps satisfied

[@happmacdonald]

Nah they can't see past their neighbors nor remember the past, I think they're gonna sleep well tonight after their neighbor signals that it's nighttime. xD

[@kaidatong1704]

nooo u can’t just break the first law of robotics machine gun goes brrr

[@usernametaken017]

@@kaidatong1704 if nobody saw it its not a crime

[@nondescripthandle212]

@@happmacdonald that nighttime bit got mw

[@klobiforpresident2254]

We went from sorting robots to laser firing squads. Amazing. Is there a cut version of just the "dancing" robots out there? Did you hand-animate each squad or did you create a utility to do these in practice animations for you?

[@udiprod]

Thanks! It's procedural animation. Yes, a cut version is a nice idea, I'll consider doing that with a few more runs.

[@klobiforpresident2254]

Ah, thank you for the reply. I'll glad if you do release one eventually. I may or may not imagine a tool that can synchronise the firing squad(s) to any song given a BPM and be laughing much too hard at all the inappropriate results. Dang it, now I want to see "Robot execution synched to _I Will Survive_". I hope you enjoy the thought as much as I do.

[@HidekiShinichi]

​@@udiprod i need a version without a beats, just a nice continuus flow of dance and moves.

[@joshuapowers4623]

The weird thing about these types of videos is that visually you can see it work, follow it, and it appears simple. But there are likely pages of math computations that prove this out that never get shown. I'd never follow it, but I'd like to see the math behind it.

[@MadScientist267]

The weirder part is THIS is the more difficult to understand version 🤣

[@jjwkoester]

There’s a quote that says “if you can’t explain something simply, then you don’t understand it well enough”

[@Catman_CM]

​@@jjwkoesterI prefer phrasing that as "You have truly understood a complex concept when you can describe it in a simple manner." It feels more positive, in my opinion :)

[@ralexcraft990]

@@Catman_CMand in general fairness, more correct.

[@TheRestedOne]

My thoughts went to waveform interference; the robots act as a medium where you’d normally use water for a demonstration. Eventually the waves bounce enough times to synchronize a “destructive” wave, clearing the signal.

[@EarlHare]

"pause if you want to think about it" Meanwhile on the screen: "problem proposed in 1957, solution found in 1967" Think i'll pass.

[@extraintelligence]

Sometimes the solution to a problem is not solved with careful study and experimention, but with a singular flash of insight. For instance, Archimedes' "eurika" moment, or Newton an the apple.

[@kurumi394]

@@extraintelligence I think OC accepts he isn't Archimedes or Isaac Newton

[@extraintelligence]

@@kurumi394 not with that attitude.

[@Orlandofurioso95]

@@extraintelligence Not with that name, either

[@eilmiv]

Thanks for that comment! I felt extremely stupid thinking for many hours and being stuck with some sort of binary counting for a long time. Now I feel extremely proud to have found a solution at all. The solution I found in the end is pretty similar to the one presented in the video.

[@brady1407]

Prisoner: *Dances along to the beat* Warden: *Dances along to the beat* Shooters: *Dancing along to the beat* Prisoner: *Dances away slowly*

[@legendgames128]

I'd like, but I'm afraid that I might cause an unsigned integer overflow to 0. If there is no integer overflow though, I will like because I was wrong. (back when it was at 255 likes)

[@squidgelad1983]

@@legendgames128 Yes you're very clever, this is youtube.

[@memegumin]

@@squidgelad1983 but that was a joke, a programing joke

[@Epic_Droid]

@@legendgames128 Gosh dang it, take your like, you fellow programming punster of a mad lad.

[@theRPGmaster]

@@legendgames128 I assume 32-bit integers are used, not 8-bit, the real question is, what happens when we exceed 4.29 Billion likes

[@i_teleported_bread7404]

However, due to a design flaw, in the time the robots take to finish the sequence and set up for firing, the prisoner has already broken free from their restraints, disarmed the guards and escaped over the side of the wall.

[@i_teleported_bread7404]

@@Warze And that's why you don't drink while designing your robotic executioners.

[@52flyingbicycles]

You think you can escape them? They may be slow and limited to finite state machine commands, but they are immortal and relentless. Better to die by the merciful hand of a laser gun than huddling in a dark cave dreading your coming doom

[@stelcxantisto]

Rearrange them into a circle so that the left leg signal can never meet the right hand signal.

[@user6122]

@@stelcxantisto nah just make this the josephus problem and get it over with

[@SoupEarthOfficial]

Just get one robot

[@littlegamedude6351]

Football star: gets brutally injured. The cheerleaders; 7:20

[@edwardblair4096]

One thing to point out here is that since the state transitions of each robot only depend on their immediate neighbors, you don't have to have any knowledge of how big the pool of robots is. But if you added a little bit of memory, you could probably arainge it so that once the synchronization event takes place, every robot knows what their position in the line is, up to some limit.

[@MadScientist267]

The entire point of this is that no such construct is needed. That said it has "memory", as a whole unit.

[@GeekOfAllness]

I just wrote this out replying to a different comment, and it does work, and faster than the video's algorithm. You can just use a 128-bit number that guarantees it can store the number of computers in the system (64 bits is almost certainly sufficient and 16-32 bits is overkill in most real cases, but there aren't even 2^128 atoms in the observable universe, so it's guaranteed). Each robot has 128 "legs" with two states (representing a single 128-bit number), then the "hands" tell it whether the signal is coming, going or idle. So computer 1 gets the start signal, says "leaving", "1" to its neighbor. The neighbor sees "leaving", adds 1 to the count and propagates "leaving", "2" to the next neighbor. This proceeds to the last computer, which holds the final count of computers, "N". After the right-hand neighbor is set to "leaving", the current computer can return to idle or just sit in the current state. The final computer sees that it's final and switches to "returning", "N". The penultimate computer sees "returning" and also switches, but subtracts 1 from the current count to be "returning", "N-1". This repeats back to the beginning. The difference on the return trip is that after the state is "returning", each computer counts down by 1 every tick. So the "returning" signal will hit computer 2 when the count is "2", but every computer to its right will also have counted down to 2. As computer 1 sets its state to "returning", "1", computer 2 counts down once to "1" (along with all the other computers). Now, all the computers count down once to zero and fire. Alternately, they could all fire at 1, and computer 1 knows to fire next tick if the computer to its right says "returning", "2" this tick. For N=11, the video took 34 ticks, where mine will do it in 21 ticks (10 "leaving" ticks, then 11 "returning" ticks, since the last computer can transition from idle directly to "returning", "N" and skip the "leaving" tick). Even better is if whatever method you're using to synchronize ticks just counts all the computers each time and you can just store the total computers plus a given computer's place in line. Then *any* computer can originate the signal and start the count based on the farthest distance from it (a middle computer would start at N/2, for example). If one computer sends a signal after another already did, but before it knows about the signal, all computers seeing both signals can just use the lowest count.

[@Poldovico]

​@@GeekOfAllnessyou're using memory to run in linear time, whereas the memory-less version runs in log time. Not so strange.

[@mayday8413]

Since they have no memory all they know is that since they’re not a general yet the group must be bigger

[@EnUsUserScreenname]

This video felt like some kind of AI is trying to trick me into progamming a dissident-killing subroutine for it.

[@WillToWinvlog]

Lol

[@shadowling77777]

Lmfao

[@senorpepper3405]

no bueño

[@skunkfac3]

Skynet: "Dammit, they're onto us!"

[@undefined6947]

As a musician I very much appreciate that you synced the music, it annoys me to no end when stuff like this is put to random music that doesn't sync and it takes work to sync something like this so well, I owe my life to you.

[@frocco7125]

I agree.

[@emil.pettersson05]

The only problem is that the robots dance in 3/4 and the music is in 4/4.

[@undefined6947]

@@emil.pettersson05 that's called an ostinato, looks like it's intentional here, so no problem :)

[@user6122]

@@emil.pettersson05 anything can be a waltz if you try hard enough

[@scottilewis3753]

How do you want to pay?

[@ColCoal]

Engineers: “Just make them all shoot once a signal is given, these constraints do nothing but hamper their functions.” Mathematicians be like:

[@jebediahkerman8245]

Yeah if the whole process is started off by hitting the first robot why not just hit all of them at the same time 😂

[@samfriend3675]

Actually this is a real engineering problem. Its from computer science, and the practical considerations are (Surprisingly enough) in computers. When computers are involved, each machine can be far enough away that only adjacent machines on the network can talk, and synchronisation of certain tasks can be important. This is the engineering side of it. It's a bit like the two generals problem - its seems silly to talk about, and like its just a problem for the sake of logic and maths, but its something that actually needs to be considered when dealing with computer networks.

[@KavsLockedOut]

@@samfriend3675 what situation would result in only adjacent clients be able to talk in a network?

[@arielsproul8811]

@@KavsLockedOut daisy chain a bunch of computers together, have first one connected to the server and then have them try play epic dubstep hardest beat drop (not clickbait) (almost died) (shot my neighbors cat with a sawed off) (working 2021) (working free robux) (no survey) (no virus) simultaneously if you mess up it's just going to sound like a loud cacophonous mess rather than a loud mess

[@samfriend3675]

@@KavsLockedOutLong distances in areas with lots of interference could do that easily. Networks of low power devices (not full computers) that can't afford to be constantly transmitting - to name two situations. A slightly different situation is in digital logic circuits - a circuit built on the transistor level. Memory requires a fair number of transistors to make work, but logic states are much easier. Connecting everything to everything may not work just based on space - transistor circuits can be absurdly small.

[@Quincunx_5]

I am so incredibly grateful that you finished off the video by just giving an opportunity to watch the robots do their thing a few times. Cool stuff!

[@FurryNonsense]

I love how more rules kept being added so that when he was wrong, he wasn't wrong

[@godlyvex5543]

those were all part of the solution

[@carykh]

the more green-lit generals i see, the more nervous i get.

[@ultrio325]

Probably because you are the prisoner from abusive AI usage (AI torture for music generation)

[@mayabartolabac]

POV: You get killed by the robot firing squad after committing genocide on 2 music AIs

[@keithplayzstuff2424]

TIL cary watches udiprod

[@urble]

The living legend himself

[@Chumpatrol1]

I keep seeing you in every comment section lol

[@Moley1Moleo]

I've been sentenced to death but robocop over here can't stop doing fortnight dances to taunt me.

[@DepletedLithium]

Brilliant!

[@Terraqueo22]

Until he finishes dancing

[@ITSMRFOXY]

Ironically, Robocop is now in fortnite

[@cye2310]

​@@ITSMRFOXYIt's fortnight, Fortnite is the kids version

[@丫o]

*Props to the cameraman for standing there and being shot with lasers so many times just to get us this awesome video!*

[@cobalius]

Imagine being in death row and the executioner starts arkwardly dancing while everyone is super serious. I would die laughing sooner than he would have shot me down lol

[@Nauctshea]

Executioner: "If you can figure out how to make this robot firing squad fire simultaneously using only body language from neighbors, we'll commute your sentence." Prisoner: "Logic problem? Ugh, just kill me." *robots dance* Prisoner: "Ohhhh, that's ho- *LASERED*

[@rootabeta9015]

Imagine being sentenced to death by firing squad during the robot uprising, and your last sight is a bunch of robots dancing to coordinate your demise

[@MorningDusk7734]

The best part of this is that there's actually a practical application for simultaneous mechanisms. As long as their clocks are synchronized, pinging the nearest two devices with your state and updating accordingly should allow for simultaneous firing of whatever thing needs to be simultaneous. And if you put it in a machine, the order could carry across the line and back nearly simultaneously!

[@Sylfa]

Mmmm, except you fail at the synchronized clocks. Alternatively, you already had a method to synchronize all devices.

[@officersoulknight6321]

"there's actually a practical application for simultaneous mechanisms" "whatever thing needs to be simultaneous" Sorry bud but you're not making the greatest point. This argument does prove however that this could happen in real life, so it is a step toward making this useful.

[@Henfredemars]

This is fragile because it supposes that all of your machines are reliable.

[@loganduncan1259]

Almost as though almost every analogue mechanical device is consistently simultaneous, and this is a superflulous example. You've really not said anything here that isn't already implied, and frankly I've lost some faith in the intelligence of humanity.

[@DrakeOola]

@@loganduncan1259 This is an example of swarm behavior, try again.

[@50shadesofmycow]

This is probably the most random video I've ever watched and I loved every second of it.

[@roblxplyr2017]

no clue what i just watched but i can tell whoever came up with it is a genius

[@bustahwoalf2858]

I like that the leg signal is basically the countdown. In the time it takes for it to move from the first to the last robot, all the other signals would have been set to fire

[@DJChiefX197]

Not quite. If a robot becomes a double-general while queuing the leg signal, the leg signal is delayed by one beat.

[@ryannorthup3148]

@@DJChiefX197 The point still stands, since the final robot only fires when that final leg signal reaches the end of the line.

[@ValeBridges]

@@ryannorthup3148 heh, the point still _stands_

[@ryannorthup3148]

​@@ValeBridges heh

[@thetiredladdy]

@@ryannorthup3148 Puns!

[@TheRabbitPoet]

"Many years later, as he faced the firing squad, Colonel Aureliano Buendía was to remember that distant afternoon when his father bonked a robot on the head" -one hundred years of solitude

[@Elizhium]

as a programmer the only issue I see is giving them a beat that is perfectly synchronous so we can do this fast

[@Elizhium]

​@TailExchange can you trust that clock tough? are you sure your thread is not pushed to the back and almost forgotten about when the others are having fun. or when you're communicating with other systems and somehow their message takes a freaking long time to arrive... I'm not stressed working with multi-threaded web services, what are you talking about :p

[@spiralhalo]

I want to see a simulation where each robots propagate their signal at very slightly different rate and see how bad the desync is gonna be..

[@martysh1226]

@@Elizhium maybe set a time when the beat should start and have a hardcoded beat?

[@ivarangquist9184]

If you had a server, you wouldn’t need the dancing.

[@wojtek4p4]

If every robot can measure time and can perform actions instantly, it should be pretty easy - every robot performs action exactly on beat, to act as a basic synchronous clock. Before starting the execution dance, they sync their clocks. The leftmost robot sends out a sync signal with no information. It gets passed like the "hand up" signal in the video, bounces back and comes back to the leftmost robot. Every robot automatically syncs their clock to the robot left of them. Only after leftmost robot receives the returned sync signal, the main execution dance begins.

[@DeltaSix_YT]

This will probably get recommended again over 6 years. See ya there.

[@SomeoneYouDontKnowOfficial]

Middle of an odd squad general is an absolute chad. Coolest robot in the squad by far

[@alansmithee419]

Now we just need twenty people to learn the choreography for this and do it as a stage performance.

[@hueyiroquois3839]

The audience might not like the plot twist at the end.

[@PokeShadow77]

@@hueyiroquois3839 Dead men tell no tales

[@SniperOnSunday]

@@hueyiroquois3839 What are they gonna do about it?

[@aiosquadron]

@@hueyiroquois3839 Maybe, but they won't live to tell the tale. (Hides mousin negate behind back)

[@MadScientist267]

...why... 🤦‍♂️

[@zlodevil426]

Can we have 10 hours of these robots please

[@walksanator]

Yes just a stream where after firing it adds another robot

[@eclipse_darkpaw]

@@walksanator 10/10 would watch

[@yonatanbeer3475]

Please

[@leondost3575]

follow up problem: "at 2 beats per second, what number of robots would take (closest to) 10 hours to fire?"

[@redyau_]

@@walksanator Oh that's a nice programming challange

[@mrmimeisfunny]

8:05 Imagine this is the last thing you see before you die.

[@pvic6959]

id die amused and that wouldnt be terrible lol

[@FlashDrive356]

They be groovin'

[@shoam2103]

I'd be pretty amused

[@tykjpelk]

Imagine a future where they need 20 coordinated robots to kill you.

[@erinboyle2889]

sometimes I come back to this video just to watch from 8:05 onwards

[@druid_zephyrus]

n=17 is my favorite. The pirouettes and the high notes make me giggle. Maths is beautiful AND deadly. I love it.

[@danielyuan9862]

I thought about splitting the problem along the middle of the line, but I didn't think about sending a signal that is 3 times slower than another. Beautiful solution!

[@PRIMEVAL543]

Meanwhile in terminator 5: „Mom? Why are the robots dancing?“ „Oh no, we are dead in 20 seconds! Give me one last hug“ „I love you mom“ „I love you son“ .... One eternity later Piu piu piu

[@AssistantCoreAQI]

A Group Of Rebels Moves The Robots From The Beginning To The End Cyclically, Resulting In Them Being Completely Relocated.

[@PRIMEVAL543]

@@AssistantCoreAQI „Error, arm signal from right == True and left leg stretched == True not found! Nuclear self destruct in 3, 2, 1“

[@sinom_00]

Ive seen this algorithm before with just colored cells, but its so much easier to visualize with the robots.

[@247flashgames]

Wow, this is a really clever solution, and the procedural animations are impressive! Thank you!

[@explorer47422]

The last bit with the music just had me smiling crazily and don't know why, it bought a lot of happiness

[@rre9121]

This is one of those lesson introductions one of my old professors would use right before launching into the history of statistical mechanics and how simple models can show phase changes in materials.

[@XCSme]

Why the leg has three stages: the hand signal must travel three times faster than the leg signal because it has to travel three halves while the leg signal only one so that they meet in the middle.

[@sebasfavaron]

Thank you!

[@TG-to5nf]

good comment.

[@HypnosisBear]

That's genius!! Thanks for explaining it to my stupid mind! Now I can truly appreciate the solution!

[@DrakeOola]

And multiple leg signals to handle even or odd amount of squad members since with an odd amount you will have a single person in the middle but with an event amount there will be 2 middle men

[@BlackM3sh]

Thought this was going to be an impossible problem, but it wasn't. Very neat!

[@Marcox385]

Two uploads in a century? God has blessed us

[@TheGreatDanish]

I like how this video presents this as a logic or math puzzle but doesn't ever give us the whole picture we need to solve it until *we're already* at the solution.

[@steamyninja8881]

8:00 POV: You’re about to be executed, but are confused af, especially when they don’t even fire

[@finnaginfrost6297]

For some reason this is the funniest thing I've seen this week.

[@ivarangquist9184]

Wow, this is probably the most clever logic puzzle I’ve ever seen.

[@SorryBones]

The mathematical precision of them trying to decide when to kill you is so detached it’s scary. But also I want to dance

[@_ramar]

hello merge sort type solution, very cool to see you here!

[@derfastimmerzustimmer8635]

A classic divide and conquer approach. I love the solution, it's beautiful.

[@niemandwirklich]

Such a fascinating problem and solution!

[@isaach.1135]

All the while, whatever was in the path of 100 robots decided to take a nap and then just leave

[@rodrigoappendino]

It looks like those Wolfram cellular automata, but with finite set of cells in the horizontal axis and with more than 2 states.

[@charlz-darvin]

It means that this is just 1D automata.

[@rodrigoappendino]

@@charlz-darvin Yes, like all wolfram's automata

[@rodrigoappendino]

@Michael Darrow I know. But Wolfram studied the 2 states 1 dimensional and infinite cells cellular automata. The video shows us a 1 dimensional, finite cells and more than 2 states.

[@hamburgerbroz6439]

mathematicians are the type of guys to go "heres a simple problem" and then add 20 more rules once you get it right

[@cowcrusader]

Imagine being sentenced to death and you see a firing squad dancing to happy music before they all shoot.

[@personman4011]

It's amazing to see how people can find ways to emulate things like memory and recursion in such simple and restricted systems like this.

[@nowhed]

Wow blue moon today, udiprod uploads

[@Huntracony]

It's always a great day!

[@bajooder5518]

4:56 when you find the nerf dart that you lost in 2010

[@Riolande]

Why did you private this video? I watched it halfway before going to sleep and waking up to see you had made this video private.

[@G.Aaron.Fisher]

Thanks for posting. This is just about the proudest I've ever been of solving a logic puzzle. The crazy thing is that as complicated as the solution is, most of it is actually forced by the constraints of the puzzle. There are a few different ways of dealing with parity issues. But most parts of the solution are provably required.

[@them4309]

I like how the music and the dancing is all cute to watch, but what they're actually doing is getting ready to kill you, since your point of view is that of the condemned. XD

[@protondium_8927]

The new rhythm heaven game looks amazing!

[@EthanTheGamer77]

the visual cues seem a bit complicated I'm not gonna get better then a OK

[@Xzanah]

Lmao "this is a robot firing squad" being the first thing, sounds like Mark Zuckerberg and his buddies dislike my being alive.

[@maccrew612]

Good KZbin algorithm! A video I would have never found but needed.

[@somedude8380]

imagine being executed and the firing squad does a little jiggle before killing you

[@lgrantcdg]

This excellent! Very well presented, and it brought back happy memories of reading Edsger Dijkstra's paper, "Self-Stabilizing Systems In Spite of Distributed Control", back in the day. Thank you.

[@thejbo777]

Woah, more than one video posted in a year? THIS IS AMAZING!!!

[@colevilleproductions]

6:40 when the laser sound effect said "ch" i felt that

[@highoncatnip_]

pw ch zzt

[@jonathanpallotto8227]

This is a perfect example of a more advanced Turing machine. Great video

[@TheSpookiestSkeleton]

This has to be the most upbeat tune I've heard while being executed by firing squad

[@PiercingSight]

Before the moment to pause and think about it, you probably should have explained that a robot could give two signals simultaneously, and explained that a signal could take more than one beat. Also, how many signals are allowed? If the number of signals is as arbitrary as the number of robots (can change with the number of robots), then the solution is easy. (Though the wording seems to imply that the number of states needs to be the same between all robot numbers?) The robots only need to know the signal of the robot to their right. It will be a countdown starting with a signal representing the number of robots. When a robot sees a numbered signal next to it, on the next step, it gives the signal of n-1. This repeats until the signal of countdown has propagated to all robots and they all fire.

[@Tumbolisu]

There is no limitation on signals, as "signals" are just our human way of thinking about this. The problem description only mentions a finite number of states and a finite number of transitions, which has nothing to do with signals. Every combination of a hand signal, foot signal, including direction, is a completeley seperate state with accordingly completely seperate transitions. It is easy to describe them all by thinking of them as individual "signals". This is why a large portion of the video is about handling odd numbers of robots, as it is not obvous how these signals are combined in such edge cases. Of course the number of states and transitions should not be dependant on the number of robots, since you can not pre-program that behaviour. If you programmed it for 1000 robots, but then had to do it with 1001 robots, you would need to reprogram all robots to allow for the extra states and transitions.

[@samuelfaille-denis8098]

here's the problem to your method, what specifically is "n"? the problem assume that number isn't known

[@ivarangquist9184]

Before I watch the solution: My idea is to start with two chain reactions moving with different speeds to the right. One that moves right every beat and another one that moves forward every third beat by cycling through three different states. The faster one bounces when it hits the right end of the line, which means the “waves” will meet each other exactly in the middle. When the waves hit each other, they should release four waves, two to the right and two to the left with similar speeds as in the beginning. This will essentially divide the line into two equal parts in which the process will be repeated, diving the line into smaller and smaller similar pieces. We want the robots to fire when the line can’t be divided any further. The robots notices this when two fast waves collide right next to slower beams, which indicates that the beams collided right after they got released. This is by no means a complete solution, but I don’t think the details matter that much.

[@banknote501]

That's essentially the solution in the video. Count the number of states that the robots use. Now try to do it in as few states as possible and in the shortest time possible. A friend of mine solved that as a PHD thesis. Unfortunately a second researcher was faster in publishing his solution. 6 states is current minimum, 5 states are not proven to be possible or impossible yet.

[@debblez]

Sure bud

[@naturally_rob]

"We have some constraints that make this simple task difficult" Typically those constraints are emotions.

[@o_sch]

0:00 "Heres a robot firing squad" in a happy and upbeat tone

[@johnvriezen4696]

I have a copy of the 'Computation' book by Minsky-- college text book. This problem is basically the only thing I specifically remember from the book and it has always intrigued me. When I saw the video title I knew immediately what the topic was about. I'm still, to this day, curious what the 2n-2 step solution is. The book claims the soldiers in that solution have 1000's of states, but the link in the description says "Optimal solution: The fastest solution to this problem uses 2n-2 steps. There’s a proof this is the best possible time. It uses also only 6 states. It is not known whether this is optimal or not."

[@SirPlotsalot]

This is the most American sounding problem ever

[@jackbauer322]

firing squad exists and existed all over the world ...

[@antoniomaglione4101]

Would be nice to see the truth tables, or the Karnaugh maps, how you build and solve the logic process. Thank you for this. I once used a Johnson counter (one for each robot) and a logic array to build it.

[@mayanightstar]

uncanny how cheerful the video is for being about a firing squad

[@MillMoxx]

Its like a terrifying robot timer. You know its getting closer to shooting you, but you never know exactly when it will

[@SCRedstone]

everyone gangsta till the robots start doing their funny dance

[@albertlau867]

mathematician: now do it in 2-D rectangle, or generalize to n-D hypercuboid.

[@mymoomin0952]

I know this is a joke but the problem was actually solved for squares, rectangles and cubes in 1974 bc mathematicians are just Like That

[@Tumbolisu]

2D: Assuming each robot can see the 8 neighbours around it, and that the lower left robot is the one that gets activated at the start, do the following: The robots on the lower row of the rectangle perform the hand and foot signals as shown in the video, up until they all turn into generals. The robots in the row above will notice that all robots below them have turned into generals. At this point, they will simply perform the exact same dance going vertically. Eventually ALL robots will become generals and they shoot. It should be easy to see how this can be generalized to any number of dimensions.

[@yellowjackets8011]

Imagine being executed and this Music starts playing

[@mr.calamity8886]

Honestly the idea that the robots won't fire their weapons until every single one of them has been promoted to general is hilarious to me.

[@Jeff-ku9bq]

I could watch these full runs for hours. It's hypnotizing.

[@Day13May]

It's odd I came across this when I did, I had just come up with a similar solution for syncing groups of objects via signal transferring when I was programming, although my solution was a bit more crude than this. Great stuff!

[@MadScientist267]

Damn. More crude than this? What they use? Smoke signals? 🤣

[@May825]

The dancing at the end was so cute lol

[@adjoint_functor]

POV: You're in battle, rising against your robot overlords, climactically facing a large firing squad, and in your anticipation, they start dancing

[@RaExpIn]

Everytime the robots shoot I'm hearing a friendly voice saying: "Now you are dead."

[@dtkedtyjrtyj]

I didn't even attempt to solve it, but my first instinct was "set up some sort of wave that constructively interferes at the end". I was missing the two other critical insights: send two waves at different speeds and make them collide. Also, I want to see a 200 robot execution.

[@BlueMelon555]

What would happen if we initially hit two robots on the head who are following these rules?

[@nigeljames6017]

The interesting thing here is, unless I’m mistaken, this task was solved by humans. I’d love to know how many iterations it would take for an average computer to solve the problem starting with no prompting except for the arm, leg and body movements. In other words by A.I.. I would have guessed it would have taken many hundreds of thousands of iterations before even the simplest problem would be solved. What do other people think ? I’ve seen other channels where problem solving is taken on by computers, and sometimes the results are quite amazing, but most take hours.

[@dred_dreamr]

The enemy squad when they catch me reloading:

[@soup5344]

I keep forgetting about this video and then it pops up again in my recommended a random day

[@WillToWinvlog]

Welcome back Udiprod, I just watched the first half and I'm considering solving it on my channel.

[@iavv334]

This is also a decent example of how a resonance chamber works if you think of each limb position as a harmonic series

[@Awesomekraken677]

Imagine being on the receiving end of this, just watching the robots do a dance number and knowing once all the robots finish you’re dead