Amateurs Just Solved a 30-Year-Old Math Problem

I have a question for you what's the longest time a computer program can run before it stops a year a decade a century a millennia or even the age of universe if you don't know the answer you're not alone this question has baffled and mesmerized mathematicians for over 60 years why it has surprising connections to some of Math's oldest and most famous unsolved problems it offers a window into where the fundamental logic of math starts to crumble and could even reveal the edge of what's humanly knowable and just last year after 30 years of no progress a major breakthrough was made but what makes this discovery truly remarkable isn't just the result It's the weird way that it happened it wasn't solved the way most maths problems are solved by a team of Highly skilled researchers at a university it was solved by an unlikely group of math enthusiasts mostly without formal academic education who all met online through a website announcing something called The Busy Beaver challenge by the end of this video you'll know exactly what that means as well as the surprising story behind this breakthrough and exactly what it was they discovered it all started with one mathematician and a game he invented when most people were asking what problems can a computer solve a mathematician named tbbor R asked what problems can't a computer solve how far could an algorithm a stepbystep Mindless set of instructions really get us were all problems computable or was some too complicated for a computer to handle what are the limits of computation at the time the idea of what a computer could solve was well understood thanks to Alan churing he thought up these simple theoretical devices called churing machines that capture exactly what it means to compute something churing theorized that these simple kind of computers could perform any possible computation they're the blueprint upon which all our modern digital computers are based even the computer you're watching this video on radiar did end up finding a problem that a computer can't solve and to understand it we need to know how cheering machines work a cheering machine is made up of an infinitely long tape divided up into cells a symbol like a zero or a one is in each cell a head reads the symbol and depending on what it is can erase it write a new symbol move to the left or move to the right every touring machine has a unique set of rules which tells it what to do for example rule one might say if you read a zero write a one in the current cell move one cell to the right and go to rule two there's also a Special Rule which tells the machine when to stop running a cheering machine can have any fixed number of rules some have three rules some have 10 rules some have 100 rules usually the more rules a cheering machine has the more complicated computations it can do if you want to know more about how cheering machines work I've made a whole video about them which I've Linked In the description but here's the important bit you need to know starting from rule one a churing machine will either eventually halt or it will run forever so cheering machines come in two types halting and non-h halting Ros sorted cheering machines into groups according to how many rules they have he grouped all the one rule machines together all the two three rule machines together and so on in each group some machines will Meander along forever some will halt pretty quickly and some will take much longer to Halt one will be the last to halt this was the machine R was interested in the longest running of all the halting machines Rao named them busy beavers because of how they forage along the tape the number of steps The Busy Beaver takes before halting is called its Busy Beaver number or BBN for short for example for a one rule touring machine if you want to make sure it holds you can really only have the rule that no matter what it reads it holds so the Busy Beaver Number of a one rule touring machine is just one as it only takes one step before halting getting BB2 is a bit more complicated as there are 6,561 two rule machines but it's been shown that busy beaver number two runs for six steps before it holds now here's the cool part R found that finding Busy Beavers and their Busy Beaver numbers is uncomputable there's no General algorithm or formula a computer can perform to find them the only way to

find a busy beaver is to manually examine each machine one by one and see how long they run he'd found what he was looking for R turned his search for Busy Beavers into a game to play you have to do two things discard all the non-h halting machines and search the remaining machines for the one that runs the longest little did he know that this game would have roots in some of Math's biggest open problems and turn into a decades long hunt that would haunt generations of mathematicians but what did busy beavers have to do with these famous problems to understand let's take a look at one of them the goldback conjecture says that every even integer greater than two is the sum of two primes for example four 2 and 2 a prime 28 is the sum of 17 and 11 both primes do this for any even number and it'll work this seemingly simple conjecture has defied proof for almost 300 years yet so far we know that it's true for all even numbers up to 4 * 10 to the power of 18 but checking individual cases isn't good enough for mathematicians they need hard logical proof that it's true for all even integers this is where a busy beaver might come in handy suppose you wrote a computer program that checks every even integer starting from four one by one and halts only if it finds a number that cannot be written as the sum of two primes such a program has been shown to be computable by a cheering machine with 27 rules but here's the cool part if we knew the value of bb27 we could solve the goldback conjecture if our program does halt then it must halt in bb27 steps or less if halts within this number the program has found an even integer that can't be written as the sum of two primes this would prove goldbach's conjecture wrong but if the machine continues running past bb27 steps then we' know it will never Hal as all the halting machines halt before bb27 steps goldbach's conjecture would be proven true so the solution to the goldback conjecture can be reduced to finding the 27 rule busy beaver there are other similar cheering machines for other unsolved problems in math like the remon hypothesis in fact any mathematical statement that can be written in a computer language can be proven in this way it's amazing to think that doing something in a finite number of steps can tell us something about an infinite amount of numbers so what are we waiting for why don't we figure out bb27 and then solve the goldb back conjecture and all other unsolved problems in math for that matter we've seen the one and two rule Busy Beavers but the three rule well there are over 5 million three-r touring machines and over 7 billion four rule machines remember that the only way to find a busy beaver is by examining each machine individually it's like finding a needle in a giant digital haast stack where the Hy Stacks increase more than exponentially in size as the number of rules gets bigger but surely we could make our lives Easier by getting rid of all the non-h halting machines and then just looking through what's left the non-h halting machines are definitely not the Busy Beaver as by definition The Busy Beaver halts but churing has a nasty surprise for us he proved that there is no reliable repeatable way to tell if a cheering machine will ever halt if a machine has run for 100 years it may halt in 100 years in one day and there's no way that we can tell except to just wait and find out this result is called the halting problem and I've made a video All About It which I've Linked In the description it's actually a really cool results even if it is a pain so it turns out that both steps of R's game are extremely difficult one because of the halting problem and two because there are so many machines to search through but have we at least found the third busy bether before we get into it there's a great article on Quantum magazine by Ben Baka that details the story of The Busy Beaver progression really well I got a lot of the information for this next part of the video from there so I definitely recommend checking it out if you want to learn more okay here we go in the mid1 1960s a persistent mathr student at Oregon State University whose mascot is coincidentally Benny the Beaver gave it a go his name was Alan Brady and he realized that he could sort through all 5 million of the three state cheering machines if he ignored large chunks of them such as those that halted

immediately he also recognized that many non-h halting machines were easy to spot because they began looping performing the same instructions over and over Brady coded up this technique of discarding the obvious non- Busy Beavers into a computer program but the average computer at the time couldn't handle that kind of heavy computation Brady had to drive 90 miles to a town called Beaverton I'm not joking to access a state-of-the-art computer at the oragon Regional primate Center but oh no he was too late Rao and his grad student Shen Lyn had beaten him to the punch they' found the third Busy Beaver it halted in 21 steps but Brady didn't lose hope he immediately moved on to finding the fourth Busy Beaver but there was a problem fourr touring machines can do much more complicated computations than three real ones this means it was much harder to spot the non-h halting machines because many of them don't get stuck in infinite Loops which Brady's program was good at recognizing but nevertheless 2 years later he'd found a four RU cheering machine that halted in7 steps it would take him several more years of painstaking work to prove that this machine was indeed the fourth Busy Beaver which brings us to April 2024 The Busy Beaver Challenge and a Aver group of math enthusiasts despite there being nearly 17 trillion 5-year-old touring machines they managed to do what no one else could they found the fifth Busy Beaver and bb5 okay we actually need to jump back for a sec around 20 years after Brady found the fourth Busy Beaver the University of Dortmund held a competition to find the fifth Busy Beaver over 100 contenders showed up but by the end of the competition no one had conclusively found bb5 however one contestant had found a machine that halted in 100,000 steps the contest was reported in Scientific American which popularized the game to a new generation of mathematicians and this number soon blew up to over 2 million steps pushing the potential bb5 up even higher but everybody was shocked when grad students haa markson and Jurgen bunu discovered a five-state machine that halted in 47 million 176,177 a grad student named Tristan staron tried out Brady's original method with a Twist like Brady Starin wrote a code that weeded out machines that obviously weren't the fifth Busy Beaver he collected all the remaining machines and dumped them into a database for examination by December 20121 the database was complete and held over 88 million machines 88 million possible Busy Beavers if he could show that each of these machines either halted before 47 m million steps or never halted then he would know that this 47 million step machine really was busy beaver number five but how was he going to sift through this mountain of 88 million machines Starin knew he needed help so he founded the Busy Beaver challenge an online community anyone could join around 20 people from all around the world started working on the problem and most of them didn't have any formal mathematical training they just did math as a hobby or for fun together they began chipping away at the 88 million machines keeping the others updated on their progress through Discord but there was a big problem some machines were nearly impossible to classify one in particular developed an especially scary reputation they called it skellet number one what was tricky about it was that it would sometimes act completely predictable and sometimes completely wild there was really no telling what it would do next but after months of bashing their heads against a wall two contributors finally managed to crack it sha Lecky and Pavel copits showed that skelet number one did finally settle into an infinitely repeating Loop but after more than a trillion steps at long last they'd managed to classify it as a non-h halting machine and remove it from the list of potential Busy Beavers but there was a doubt growing in everyone's mind could they trust the co code they wrote even if they did find

bb5 any small error in the code of the program would make their result worthless they needed to prove that their code was free of errors but how can you prove that thousands of lines of code have no errors this is where a new and unlikely player joined in with a secret weapon a proof Checker proof Checkers are programs that don't run if they come across a logical error so mistakes are virtually impossible possible a good proof Checker program could confirm Beyond a doubt that the team's proof was free of faulty logic an ambitious University Dropout and self-taught programmer May stepped in May translated skelet number one's proof into a proof checking language called verifying thei and crit's result that skellet number One never halts little by little the mountain began to dwindle with proofs of non- busy beaver trickling in from other participants but many proofs still hadn't been translated into cook to make sure they were legit and error free then on May 10th 2024 a mysterious participant named MX dys made an announcement the coke proof of bb5 is finished they compiled the group's work into a single 40,000 line Coke proof it was the final step in the Busy Beaver 5 Mission an unlikely team of individuals from all over the world who had come together over their love of math had finally proven that this 47 million step cheering machine was the fifth Busy Beaver it was a momentous feat but sadly not everyone got to celebrate Alan Brady the finder of the fourth Busy Beaver died just a few weeks before the proof was finished he was 90 years old though he didn't live to see this Milestone his legacy will always be intertwined with the story of The Busy Beaver so what's next for the busy Beav Saga some of the team are already busy hunting for this sixth Busy Beaver but it isn't looking good they've shown that bb6 is at least 10 to the power of 10 steps we wouldn't even be able to run a machine for this long before the predicted heat death of the universe so it's quite possible that bb5 is the last Busy Beaver Number we'll ever know but some of the Busy Beaver challenge team have moved on from Busy Beavers May has become obsessed with the European International rail network and is aspiring to be a train driver will Humanity ever find bb6 there are nearly 60 quadrillion 6 rule touring machines with numbers this big the odds are stacked against us but if there's one thing this story has shown it's that when people want to get to the bottom of something they'll find a way no matter how impossible it may seem the drive to understand solve and explore the unknown is what makes us human it makes me wonder what made us like this where did this insatiable curiosity come from what were the moments in our Evolution that made us the smartest species on Earth the answer to these questions are actually fascinating and my friends over at real science have made an entire series that explores these questions plus many more like the origins of language and the breakthroughs that made us uniquely human it's called becoming human and I highly recommend it it's one of my favorite things on nebula right now a platform that's quickly becoming the go-to space for the best educational content on the internet now nebula is built and run by creators with the mission to be the best place for us to make work that we couldn't make anywhere else I've always wanted to take my videos to the next level and nebula is enabling that for our entire list of creators better stories better production value taking creators to the next level is what nebula is all about and there are countless examples of what we're capable of and it's only getting better as time goes on it's completely adree and most creators post their YouTube videos there a week early to check out becoming human as well as hundreds of other topnotch thoughtful videos completely ad free sign up with my link to get 40% off that's just $3 a month or $36 for the entire year seriously for the price of a latte you're getting access to some of the most interesting and creative content out there go to nebula. com or click the link in the description you'll be supporting this channel as well as the entire educational Community thanks and I'll see you next time bye