How Amateurs Solved a Major Computer Science Puzzle
24:40 Share

Did you know there's a paleoanthropologist who hunts fossils in conflict zones? That's just one of the amazing stories we're sharing on Going Wild, the award-winning podcast produced by Nature on PBS, hosted by me, wildlife ecologist Dr. Rae Winn-Grant.

In the brand new season of Going Wild, we're highlighting some of the coolest champions of nature, like TikTok's black forager, Alexis Nicole Nelson, and Pulitzer Prize-winning science journalist, Ed Yong, to explore what led them to create change within themselves and the natural world. Get inspired. Follow Going Wild with Dr. Raewyn Grant on your favorite podcast app.

I love puzzles, at least certain kinds of puzzles. I do the New York Times Sunday Crosswords when I have time. I went from Sudoku to other logic puzzles from this cult favorite Japanese puzzle magazine called Nikoli.

My family gets in to jigsaw puzzles around the holidays each year. Now, I'm not a mathematician or a computer scientist, but I also appreciate the puzzle-like solving and structure of some mathematical proofs. And I suspect that the people who solve them might derive an even greater sense of satisfaction from doing it, especially the puzzles that take decades or even generations to figure out.

Welcome to the Quanta Podcast, where we explore the frontiers of fundamental science and math. I'm Samir Patel, editor-in-chief of Quanta Magazine. This week marks the first anniversary of the discovery of a solution to an unusual intellectual puzzle, one that our computer science staff writer, Ben Brubaker, wrote about right when it happened last year in a story called "With the Fifth Busy Beaver, Researchers Approach Computation's Limits."

Ben is with us today to dig into the elusive and strange Busy Beaver game and the unexpected source of the latest solution. Welcome back, Ben. Thanks. It's good to be back. This is one of my favorite topics to talk about. Let's start with what's the big idea? Where are we going with our conversation today? The Busy Beaver game is a mathematical puzzle about the strangest and most unpredictable things that simple computer programs can do.

And one thing I like about it is that it's attracted many people who are not professional researchers in math or computer science. They're just in it for the love of the game. And this big breakthrough a year ago that you mentioned came from a group of people working together online, open collaboration. Anybody could join. And this turned out to be a really fun human story as well as a story about some amazing mathematics and computer science. Are you a puzzle person?

I thought you'd never ask, Smear. Yes, I do love puzzles. I love crossword puzzles and lots of other word games. For a while, I was an obsessive player of a daily puzzle game called Redactyl, which is like Wordle, except instead of trying to guess a hidden word, you're trying to guess the subject of a hidden Wikipedia article. But I got a little too obsessive, so I had to stop.

Okay, before we get to this landmark puzzle solution that you reported on, I think we need to set up what the rules of this game are. Yep. So 1962 is when the Busy Beaver game was invented. It was invented by this mathematician, Tibor Rado, who has an amazing life that I'm not going to have time to get into here, but read the article. Yeah. So basically-

The goal is to find simple computer programs that run for like an unreasonably long amount of time, but not forever. They eventually stop running. And the programs that take this behavior to an extreme are called busy beavers. Rado called them that because of the reputation that beavers have for industriousness.

So why search for a computer program that runs for a long time? Yeah, this sounds kind of backwards. Normally, you want computer programs that run for a short time, that are fast. The reason these long-running computer programs are interesting is that that process of trying to find them forces you to grapple with one of the biggest questions in computer science, which is basically like, if I give you the code of some arbitrary computer program, can you tell whether it's going to run forever or stop running? Okay, we know...

There are lots of different computer languages, lots of ways to program a computer. I'm assuming that in order for this game to be relevant, we have to go to like a consistent sort of computing

environment. Yeah, exactly. And when people in this world talk about computer programs, they're not talking about ordinary programs that you're familiar with on your computer. They're talking about things called Turing machines, which are these theoretical mathematical models of computer programs. And these were invented 100 years ago. You could never actually build a Turing machine, but it in principle could do anything that any other computer program can do. And so you can use it to reason mathematically about computation.

And this goes back to computing pioneer Alan Turing who came up with this idea. So let's talk real quick about what a Turing machine is. So a Turing machine has three parts. The first part is a tape, like a one-dimensional strip. You can think about it like a film strip or something. It is divided into cells. Each cell can either have a one in it or a zero in it, and it's infinitely long. So that's the very first reason you cannot build a Turing machine.

The second component is what's called a head, and that is a thing that is able to read and write on these cells on a tape. And I like the way our great art department chose to illustrate this as like an eye of Sauron type of thing. It's pretty cool. So the head basically can look at the tape and it can see a zero or one and it can choose to change it or not change it. And then it can step along the tape or move the tape one square at a time to the left or the right.

And then the third component is like, how does it decide what to do with the tape? And that is a list of rules. It's like an instruction for what the Turing machine should be doing right now.

So, for example, rule A might say if the symbol that you're currently reading is a zero, then replace it with a one, move one step to the left, and when you get there look at rule B. But if you read a one, then do this other thing. So the head can either read a zero or a one, and that tells it what to write in the cell, which way to move on the tape, and which rule to follow next. And there's just one exception to this general rule structure, and that's when it gives the instruction to halt or end the program instead of going to another rule.

So this is a Turing machine. We go back to Rado. We want to write a program, meaning a series of rules for the Turing machine that will run as long as possible.

But still stop. Exactly. And so the first thing you want to do is choose a specific number of rules. For example, let's say two rules. And the rules have this very specific form. Write a zero or one, move one cell left or right, then go to another rule. And for two rules or any specific number of rules, there's just a finite number of machines. So they all fall into two buckets, some that run forever for whatever reason and some that make it to the rule that tells the program to stop.

So if you want to find the one that runs the longest and then definitely stops, first you have to separate the possible machines into these two buckets. But figuring out if a Turing machine actually stops, that's called the halting problem, and it's one of these core issues in computer science. Yeah, let's talk about the halting problem for a second. You can write a computer program that is designed to give you some answer and then stop. What are some of the things that can go wrong with a computer program that would prevent it from stopping?

You can write really easily a computer program that's not going to stop. For example, just print the number one and then add one to it and then print the next number and just keep looping and adding one to it. So that's not... And it just goes on. It just gets bigger and goes on forever. So right. Unless you like manually interrupt this thing, it's not going to stop.

But then there's all sorts of other kind of crazy things that a computer program might do where like there might be some condition there that's like if you ever get to this point, stop. But maybe it just never gets there because it's doing some crazy pattern of writing zeros and ones on a tape and it's bouncing around this list of instructions, but it just never gets to the case where it wants to stop. And it ends up looping, right? So it'll never reach the halt. Right, yeah. So you could have one that gets into like an infinite loop, but because the tape is infinite, it might never start doing exactly the same thing but still run forever. Okay.

So Rado defines this question, says, let's take a Turing machine so that everyone is using the same puzzle environment functionally. And let's determine what is the longest program that'll run and eventually stop for a given number of rules for the Turing machine. Yep. So we start with one rule. Yeah. What does one rule look like for a Turing machine? So when the game starts, every cell in the tape is set to zero.

And a Turing machine with one rule is really simple because it can say either, if you read zero, halt, or it can say, if you read zero, do something else, like maybe write another zero and move to the right. But it's just going to encounter another zero, and there's no other rule to look at. So unless it halts right away, it just has to keep on going forever and repeating the same thing.

So thinking about this for a minute, you can see that in the one rule case, the maximum number of steps that it can run for and be assured to stop is one step. Otherwise, it'll run forever. Right, okay. So in the language of Busy Beaver Hunters, the way to say this is BB of 1 equals 1. And the Busy Beaver game is about finding these Busy Beaver numbers, BB of 1, BB of 2, BB of 3, and so on, that represent the longest running time for a specific number of rules. And the more rules you add, the harder it gets.

Okay. So now we go to two rules. Two rules. How many different Turing machines have two rules? So that's a great question because one thing that's going to happen as you increase the number of rules is the number of possibilities is going to increase. And in this case with two rules, it's going to be like 6,000 Turing machines.

And that sounds pretty crazy. But for example, some of them might be like, oh, this one looks the same as this other one, except all the right and left are switched. So that difference shouldn't matter. Or some of them will say halt right away, but then they'll have different entries in all the other cells of this table. And we don't have to worry about those because they're all going to halt right away. So there's ways to kind of reduce this number when it went down. But we start with 6,000. Yes. Our puzzle game then is to determine which out of that 6,000 will run the longest and end. Yes. Okay. Okay.

So I think with two and 6,000, they came up with the answer relatively quickly. Yeah. So this is also not so hard because for two, a long time turns out to be six steps. That's the maximum number of steps. So BB2 equals six. Okay. What about BB3?

BB-2 is something that took like maybe a few hours, a few days. I don't know. BB-3 was a PhD thesis by this guy, Shen Lin, who was Rado's PhD student. So, you know, that's already like a lot harder. It turns out the answer is 21. So that took a couple of years to figure out. How many machines are there with three rules? There are like a couple of million machines in that case. A couple million machines. Okay. So that took a few years and a PhD thesis. What about BB-4?

So BB-4 is this one guy chipping away at it for a long time. There are billions of Turing machines. And the other thing is when you add more rules, it's not only are there more Turing machines, but the things that they do can get more complicated and harder to understand. And so it takes him like 10 years. Eventually, he figures out that BB-4 is 107. So anything that runs longer than 107 steps with four rules, that's going to run forever. Who was it who did this work? His name was Alan Brady, and he was a computer scientist.

Right. So the puzzle that your story was about was BB-5. That's right. So let's lay the groundwork for BB-5. How many five-rule Turing machines are there? There are about 17 trillion five-rule Turing machines. It's an extremely large number. Okay. 17 trillion five-rule Turing machines. We need to find the longest one that will stop. Yes. So strategically, how does one go about trying to figure out what...

that answer is. The first thing is you cannot possibly ever evaluate 17 trillion of anything in a human lifespan. So you need to find this automated way of winnowing that number down. And then you want to write a computer program that identifies as many of the machines that halt as possible. And then you can focus on the ones that run for a really long time and try to figure out if they will actually run forever. And you want to do that by looking for patterns.

So for example, one type of pattern might be just a loop like, ah, this Turing machine got back into exactly the same configuration that it was in before. And since there's no randomness, there's no chance, like no free will, it'll just keep doing the same thing forever. But then there's other more subtle ways that things can run forever. And those might also have signatures. So you're going to look for some kind of patterns. And this program is going to say, either I found that pattern, so therefore I know this is going to run forever. Or it's going to say, I don't know, not my problem. Some other program has to figure this out by looking for some other pattern.

So we have a few people who are working on this, and I'm assuming reduce that number from 17 trillion to something a little more manageable. Yeah, yeah. The people who are working on this early kind of had these programs that did everything in one program. So they started out and they were trimming the number of possibilities. And meanwhile, they were saying, all right, this one halted, so I'm going to ignore it. And this one, I discovered that it entered an infinite loop, so I'm going to ignore it. But they weren't really doing this in a super systematic way.

way. Mostly at this point, it was just people who maybe they were computer scientists professionally, but again, they were just doing this on their spare time. And it was in particular in 1989 that there was the first really big breakthrough, which was these guys, Heinrich Marxson and Jürgen Buntrock, they were living in Berlin, and they'd kind of done some busy beaver hunting a few years earlier, and they had not really gone very far.

And then Markson got a new computer at his job, and he was like, well, let me just test out my old program and see if this new computer that's faster, I can run it for longer and see what happens. He runs it over the weekend. He comes back, and it has found a Turing machine that runs for a little bit over 47 million steps, and then it stops. So at this point, we knew that BB5, this number, is at least 47 million. But he didn't have a comprehensive proof that everything else ran longer. In fact, there was no real way to know. It might have been much, much, much longer.

I'm assuming that by this point, a lot of the five rule machines have been ruled out. And maybe there's just a few left, right? Yeah. So, but because everybody was sort of running their own programs to find these Turing machines, there wasn't like a systematic database of these ones are solved and these ones aren't solved. This is just computer scientists and interested people working.

doing it for fun. Yeah, they're just doing it for fun. So about 10 years later, this guy, Georgiev Georgiev, who is a Bulgarian computer scientist, he has a PhD, but he's like working as a systems administrator for the telecom company at the time. So he has this job that he finds very boring. So he's looking for something interesting to do. He stumbles across this busy beaver thing and he just throws himself into it. He's just doing nothing for like a couple of years, nothing other than this. And he writes his own program, which

at the end, proves that everything runs forever or halts before a certain amount of time, except for 43 machines out of the 17 trillion initially started. So by the early 2000s, we've got 40-odd machines that people need to prove either end or don't end. Yeah.

I'm assuming that with the advent of the internet and various chat boards, there's just a few more interested, smart, perhaps slightly obsessive people find the busy beaver game. So yeah, Georgiev and Markson and all these other people are kind of on these mailing lists and things with each other as a loose network of people. But there isn't really a systematic effort for a long time. So the story really picks up in 2022 when this French grad student, Tristan Sterrin,

discovers a Busy Beaver game, he decides he wants to do something like crowdsourced, distributed, like well-commented, centralized system for trying to solve this. He wants to bring some order to this chaos so that people can actually collaborate on the solution. Yeah. So he basically decides to break this up into parts. First part is winnow down the list and identify all the ones that halt up to 47 million steps.

And then every separate part is like, look for ones that loop infinitely. Look for ones that have this other signature of running forever. So this breaking the program into parts allows people to work on different parts independently and have some overall structure for tackling this. And he starts a Discord server. It's like an online chat board. And a bunch of people just start to trickle in by word of mouth. So this group grows slowly over time. And they're all working on different aspects of this problem.

So I'm assuming that over the course of a year or two, they start to eliminate some of the 43 leftover programs. Yep. How far do they get?

Within like a year or so, they've really got it down to like just a handful. They've proved that those really long ones do in fact run forever. Right. So they've proved it with computer programs that find this. And there's still the issue of maybe there are bugs in the computer programs. People are doing their own things. So how certain can you be in those proofs? But they have at least some idea for like almost all of them. And they're really just a couple of monsters left by this time in 2023. What do you mean by monsters?

These are Turing machines that you look at their behavior and you're just like, holy God, what is this? How am I even going to make sense of this?

So I'll tell you one example. This is called Skelet Number One. That name comes from Georgiev. His online username was Skelet. So they named these like 43 machines after him. And Skelet is skeleton in Bulgarian? Skelet is skeleton in Bulgarian. Got it. It's because he was very thin. That's what he told me. Okay. So Skelet Number One is a turret machine that kind of does some relatively orderly thing for a while. And you're like, oh, I think I know how this behaves. And then it kind of explodes into chaotic behavior. And then it goes back to some orderly thing and then explodes into chaotic behavior. And so...

It keeps defying your intuition. And it turns out they're able to prove that it does this alternation between order and chaos for at least a trillion trillion steps, maybe more like a trillion trillion trillion trillion steps. And then after all that, it settles into an infinite loop. And that infinite loop is eight billion steps long, which is also kind of weird. An eight billion step infinite loop. Yes. Okay. And this is from a simple Turing machine. Yes.

tape with cells on it, ones and zeros, five rules. Five rules. You can write it on an index card. That's amazing. But they do eventually find that it falls into this loop, right? What happens next?

At this point, they've found proofs for all these machines. So the next question becomes, do you have ironclad proof that these machines run forever? And at this point, some of the people working on this project start using this special programming language called COQ. That's C-O-Q. And this is a programming language for guaranteeing the validity of mathematical proofs.

And so they start translating these proofs into this language Coke. And then in 2024, in April, this new person pops into the server. Username is MXDYS. Nobody knows what that means, who it is. Just an anonymous person who's just like, hey, I'm interested in doing this Coke proof and here's what I've done. And like within a couple of weeks, just finishes this up. Mystery user lurker pops into the Discord out of nowhere. Right.

And basically finishes it. Yeah, collecting some coke proofs that other people have done and formalizing some methods and streamlining and coming up with some new methods. But it's basically just one computer program. It's like, run this program and it will mathematically prove that all of these machines run forever, starting from first principles.

So this new user proved that that 47 million odd, what's the actual number? 47,176,870. This person proved that that one that had been discovered earlier with the machine that was left running for the weekend is the actual solution to BB-5. That is right. That is the fifth busy beaver. Two questions come off of this for me. One is...

Is there some intrinsic value to knowing the solution to this relatively esoteric and weird puzzle outside of the wonder at how quickly it scales from 107 to 47 million? You could safely say that there is not going to be a practical application of computer science where you're like, thank God I know that the fifth busy beaver number is 47,176,870.

But there is like an intellectual application to the Busy Beaver game, isn't there? Right. In some sense, as these Busy Beaver numbers get larger, you can relate them to these unsolved problems in mathematics. And then you can use them as a way to categorize the difficulty of these unsolved problems in a way of saying, like, this problem is as hard as finding this Busy Beaver number. And this other problem is as hard as finding this other Busy Beaver number.

So the natural question is, now that we have a solution to Busy Beaver 5, what's the deal with Busy Beaver 6?

It gets worse. I can imagine it gets worse. How much worse, I guess, is the question? So Busy Beaver 6 is hard for basically two reasons. One is that the people working on this already know of Turing machines that run for just like an insane number of steps. Much larger than the number of atoms in the universe is kind of a lazy comparison, but like just so much larger that that's almost meaningless. And they obviously don't know that from running them for every step, but just indirectly proving this.

And then they stop. But there are many other machines that might run for even longer and stop. So it's at least a just mind-bogglingly more atoms in the universe kind of number. That's right. Okay. Then the second problem is that there is a particular Turing machine that they have discovered. They've called it the antihydra.

And the question of whether or not it halts is equivalent to a math problem that is really similar to this longstanding open problem called the Collatz conjecture. So if you could solve this problem that's almost the same thing as a Collatz conjecture, then you would determine whether this machine halts and vice versa. People have been trying to solve the Collatz conjecture for a really long time. If you can't do that, then you also probably can't solve the halting problem for this machine, and therefore you can't determine BB6. That's amazing. I just love that it's called the antihydra. Yeah, it's a great name. Okay. Okay.

So we have Busy Beaver 5, and we have an amazing story on the site that you wrote a year ago explaining this entire saga with wonderful detail, so everyone should check it out. I'm sure if there's any advances on Busy Beaver 6, you will write about them. I would love to write about them. And I would be excited to read about them. So thank you for joining us today, Ben. Thanks for having me. Ben, we like to end each episode with a recommendation, so what's exciting your imagination this week?

I already managed to sneak one puzzle recommendation into the main podcast. I'm going to give you another puzzle recommendation. This is a computer game. It is called Baba is You. And you control this little pixelated sheep. You're walking around an environment. You're trying to kind of solve puzzles and make your way to a flag.

The gimmick is that the rules of the game are like objects in this world that you can manipulate. So you could change those rules and maybe make it so instead of touching the flag to win, I have to touch the wall to win or something. A computer puzzle game in which you can alter the rules as you go along. That's right. Sounds great. I'm going to check it out.

Also on Quanta this week, you can read about a special kind of tetrahedron that always flips to the same face, and you can see it in action. And you can also check out a story about a new theory having to do with how AIs do creative things, or at least things that weren't in their original training data.

We're going to leave you today with the music of someone who goes by Lucy Moonlight. Now, Lucy is a friend of one of the contributors to the Busy Beaver Challenge who goes by the username Rachelin and is working on Busy Beaver 6. Rachelin sonified some of the data from touring machines and Lucy then used that to compose this piece, which is called Cities Coming Down. It's all in retro, true approach, it's all easy.

The Quanta Podcast is a podcast from Quanta Magazine, an editorially independent publication supported by the Simons Foundation. I'm Quanta's Editor-in-Chief, Samir Patel.

Funding decisions by the Simons Foundation have no influence on the selection of topics, guests, or other editorial decisions in this podcast or in Quanta Magazine. The Quanta Podcast is produced in partnership with PRX Productions. The production team is Ali Budner, Deborah J. Balthazar, Genevieve Sponsler, and Tommy Bazarian. The executive producer of PRX Productions is Jocelyn Gonzalez.

From Quanta Magazine, Simon France and myself provide editorial guidance with support from Matt Karlstrom, Samuel Velasco, Simone Barr, and Michael Kenyongolo. Our theme music is from APM Music. If you have any questions or comments for us, please email us at quanta at simonsfoundation.org. Thanks for listening. From PR.