This one is gonna be bigger than any of the numbers we've done before. So it's bigger than Graham's Number, it's bigger than TREE(3), it's bigger than TREE(Graham's Number), it's bigger than g(TREE(3)), it's bigger than TREE(TREE(3)). It really is, the sort of daddy of big numbers. - (Brady: You say that all the time!)
- I know, but it just keeps getting bigger every time! I'm not sure we can really get much bigger than this, but we can talk about that later. This number is actually called Rayo's Number. It's normally written like this. You'll notice a googol lurking in there. Rayo's Number really first came about as a result of something called the Big Number Duel which was this, sort of, contest that took place at MIT in 2007. [audience cheering] So it started with this philosophy professor, a guy called AgustΓn Rayo, and another philosophy professor from Princeton, Adam Elga. And they decided to put on this event, this Big Number Duel, as part of this independent activity period. And the basic idea was really quite simple, who could think of the biggest finite number? So this event, it was absolutely packed out. You know, there were people trying to peer through the edge of the door and all sorts, absolutely packed out. There were some very basic rules. So, two men, one blackboard. As a sort of starting point. And the idea was that one of them would go up to the board, write down a number, [writing a number] and then the other one would have to come up and write a bigger number. You had to do something novel or different when you went up to the board, okay? You couldn't just add one to the previous number or add a zero to the end of it. You had to do something new and different and a little bit novel. And you couldn't use any ideas that had gone before either, so you had to really do something new. You can only write down finite numbers, so you can't be writing down infinite ordinals or anything like that. Just finite numbers were allowed. And the other rule that was important is you couldn't use any sort of semantic vocab. So what I mean by that is you couldn't say something like "the biggest number Rayo could ever write down, plus one." Okay? You couldn't do something like that because obviously, you know, you're gonna get caught into logical loops, it's gonna be a nightmare. It's considered ungentlemanly. Okay? So you couldn't do that. The room was packed and Rayo went first. Now what Rayo did was he wrote down a series of about 30 or 40 ones. So it seems like a large number. Obviously it was just the starting point, of course he knows you could write something bigger than that, but he realized his mistake very quickly. Elga came up to the board and just did this. [erasing part of the number] You can see what he's done there, he's turned this series of ones into 11!!!!!!!!!!! and so on. So 11 with loads of factorial signs which is clearly a way bigger number! Okay, just to get a flavour for how much bigger this number is: 11 factorial is like 11 x 10 x 9 x 8 and so on. It's about 39 million. Okay, we're going to do 11 factorial factorial. We're essentially doing 39 million factorial which is going to be a number like this. If we did another factorial, well, now we'd be talking about a number - so we did three factorials now - we now would be talking about number that we couldn't even write, you know, in this sort of- as 10 to some power in any kind of practical way on this piece of paper in the time we have available. It's just not doable. But here we've got tons of these factorials. So this is a really really big number. So Elga had upped the ante massively. So it satisfied all the rules, we're doing something different, so this was a good move. So it was Rayo's turn to return to the board. At this point he remembered something. He remembered the Busy Beavers and he wrote down Busy Beaver of a googol. (Brady: Has he added that to what - ?) So this was his next entry. This was his next entry. So the idea was that they were going to the board. Somebody would put one number, somebody then comes up with another number, somebody then comes up with another number, and you've gotta up the ante every time and significantly so. (Brady: But you don't have to have manipulated the number before?) No, you don't have to manipulate it. The idea is just to up the ante on every round. So he comes up with the Busy Beavers. So what are the Busy Beavers? You've actually done a Computerphile video about Busy Beaver numbers. And basically what the Busy Beavers tell you, they tell you something about the sort of... productivity of Turing machines with a certain number of states. So if I have the nth Busy Beaver number, this is telling me something about the productivity of Turing machines when they have n states. So we'll explain a little bit more about what that means in a sec. This would be the case of where you have a googol states. So I'm not a computer scientist, so I'm just gonna explain it with an analogy. So I want you to imagine that you're in a hotel. Okay? And this hotel has a floor in it and it's essentially an infinitely long floor. And we're gonna start off and all the lights are gonna be off on this floor. But we're gonna send a robot round, and this robot is programmed by a Turing machine. And the robot's gonna go round, and it's gonna switch lights on and off. That's essentially the idea. Now, there's two states for our robot. So state number one is, say, that he's in a scared state. So what happens if he's in a scared state? He goes into a room. If it's a dark room, if the light is off, he'll turn the light on and then he goes to the room on the left. If he's in the scared state and he goes into a room where the light is already on, he transfers to the normal state. - (Brady: No longer scared?)
- So he's no longer scared. So what happens when he's in a normal state? Okay, well again, if he's in a normal state and he finds himself in a dark room, okay? He will transfer to the scared state. And if he's in a normal state and he finds himself in a room with the lights on, he will turn the light off and move to the right.
- (Brady: Ah, to save power) Yeah, just, this is just how the program's working, okay? Now, if this is all we had, then this is gonna get caught in a loop. Okay? So what's important when we're playing the Busy Beaver game is that this process has to stop at some point, okay? So in principle, what we should do is we should add some more states to this and one of them involves stopping somehow. That doesn't guarantee that we'll actually stop, but we need to have a scenario where things stop. Well, the Busy Beaver numbers say is this, okay? Right, imagine this robot has n possible states. Then this number tells you "what's the maximum number of lights that are on when he stops?" assuming the process stops. (Brady: But the states could be many and varied, they could involve all sorts of...) Yeah, all sorts of things and you're just asking to have all these possible Turing machines with a given number of states. What's the maximum number of lights you could have left on at the end of that process? And those are the Busy Beaver numbers. So these numbers, they start off fairly gradual, but they get big really really quickly. And actually, BB(10^100) - so you've got a googol states here - is enormous! It's absolutely enormous. (Brady: So the googol there refers to things like - ) (scared, normal...umm)
-Yes - (energy-saving?)
- All these possible states the robot might find itself on, we're saying there's a googol different ones. (Brady: Happy, Sad. And each one has a different action associated with it.) - Yes, exactly. Depending on whether it finds itself in a light room or a dark room. These Busy Beaver numbers are enormous. The fact- they're not even computable in some sense. If you give me the number of states, there's no Turing machine that can spit back the Busy Beaver number associated with that. - It's not even computable. This is how big it is.
- (Brady: Is BB(10^100) bigger than TREE(10^100)?) - (hesitating) I think the answer's yes? I think the answer's yes. Ehm... Yes. (laughing) (Brady: (laughing) Maybe?) (laughing) Yes. (Brady: But it's that kind of ballpark, you know?) - Oh, yeah, yeah, certainly, certainly. These are monsters. Yeah, I think that's - I think the answer's yes.
- (Brady: Okay.) So how much bigger is this than what's gone before? Well, you certainly don't need a Turing machine with a googol states to calculate 11 factorial fa- you don't need anything like a googol states, okay? This is- you just don't need anything like that, so this, this number is way bigger than anything you find here. Then Elga comes back to the board and the game takes on a new phase, essentially. (Brady: And Elga can't just draw a line through these to make factorials because he's used that trick?) Yes, you've got to do something new. Okay? You've got to do something new and novel, okay. So what did he do next? Okay, so now they start thinking about super Turing machines. So the idea of a super Turing machine: it knows whether a Turing machine is gonna stop or not. So what do I mean by that? So you start off with all the lights off. It's got a halting oracle. It knows instantly if this process is gonna end with this machine. And that halting oracle turns this into a *super* Turing machine. It makes it much more powerful and much more productive. You can actually compute, using one of these super Turing machines, you *can* compute the Busy Beaver numbers. It's computable with one of these machines. Okay? So it's much more powerful. That means you can play the same kind of game again and you get these SUPER Busy Beaver numbers which are gonna be way bigger again. Okay? Cause you've now got a much more productive machine, so you're capable of generating much larger numbers, many many many more lights left on, okay? So then they kept playing this, so then he came up with a super duper Turing machine, okay? Which again- then it can spot whether the super Turing machine's gonna halt and generate even larger numbers. But we feel like we're getting away from the spirit now, a little bit 'cause we're doing kind of the same thing again, right? So that's not good. Rayo then came up with the winning answer. This new number was the smallest number... that was bigger... than this particular number. Let me describe this particular number. - (Brady: Sounds like you're being semantic!)
- We'll come back to that. Okay? You're right, (laughs) but we'll come back to that. Okay, so consider any finite number, that can be expressed, using: the language of first-order set theory with a googol symbols or less. So we're going to write something in this language of first-order set theory. We're only gonna use no more than a googol symbols. What's the largest number we can write that way? And then think of the one that's just bigger than that. That's Rayo's Number. So let me explain a few features to that. What's the language of first-order set theory, firstly? What does that mean? Well, this is just kind of the language of mathematics. So you have symbols, you have things like upside-down A means "for all." Okay, these are quantifiers. "There exists," which is a backward E. And the other things you can have, you can have parentheses, you can have dots, which usually mean "such that," you can have variables (x, y, z), you can have equal signs, you have these various ingredients that build up a language. And it's first-order, that means you can only make references to singular things, singular quantifiers, you can't talk about plurals. This is basically the language of set theory, the simplest language of set theory. And, if you want to write down, for example, express a small number in this language, it's not very efficient actually. So for example, if you wanted to write down 0; you would identify 0 with the empty set, the set that literally doesn't have anything in it, and you'd need roughly about 10 symbols to do that, so it's not very efficient for small numbers. Again, maybe going up to about 30, 40 symbols to write down 1 and so on. Okay? So it's not very efficient for the small numbers, but for the big numbers it gets very efficient. You can start writing down functions and then you can build the numbers up that way. So it's immediately clear that you're gonna get something that's way bigger than TREE(3), for example. So one thing I could do is I could define the TREE function using these symbols, a modest number of symbols, okay? And then I could then build TREE(3) quite easily. I don't need anything *like* a googol symbols to do that. Right? And Rayo's saying you can use a googol symbols, get a number that, you know, gets you all the way up to a googol symbols. So you can do TREE of TREE of itself a googol times, you could, you could get something bigger than that anyway, it's clearly not the biggest, that's just an example of something that you could do. But, clearly you can get things that are a lot - really really really big, way bigger than TREEs. So you asked about "doesn't it sound a little bit semantic?" Clearly did, right? The way I expressed it. That's because I didn't express it in the way that Rayo expressed it. It's just the easiest way to think of it, Rayo was able to express this in pure mathematical language. Okay? Now, he used what's called the language of second-order logic, that does allow you to refer to plurals and things like that, but it had no semantics in it. The way he did it, it's quite a dry and mathematical statement, but he was able to say what I said without the semantics. And that was Rayo's Number. And it won, and Elga couldn't beat it. And it's up for debate whether anybody's ever since beaten it. There are some numbers that people have suggested beat it. It's not clear whether they're consistent, it's not clear whether they satisfy the rule of doing anything, you know, you need to do something new and novel and different.
- (Brady: Because obviously you could just increase the number he puts in there.) Yeah, of course you could, but that's breaking the rules, right? That's not allowed. The last thing I gotta say about this is that- so when I do these, ehm... These numbers, these big numbers, right? One of the things we often do is we tend to sort of throw physics at it and try to think of something weird that's gone on with it and... blatant plug, as you know, I'm writing a book about this (laughing), Brady! And normally, the number wins, right? Normally, the number beats the physics in some respect. And I'm gonna do it this time again with Rayo's Number, which is of course the biggest of them all, but I think we need to change. Let's, let the physics win this time. Let's see if we can write down Rayo's Number, you know, well, the number just shy of it, using our first-order set theory. Okay? We're going to use our googol symbols. How long would that take? So we're gonna write down as symbol as fast as we can. What's the fastest we can write down a single symbol? 'Bout a Planck time. If you try to go any faster than that, you're gonna destroy the fabric of space-time. It's gonna be - we really don't know what happens at timescales shorter than that. Space-time's just gonna go all quantum, we have no idea what's going on. (Brady: So your hand's moving so fast on the brown paper that you're writing one symbol per Planck time?) Yeah, if I did it any faster than that, I'd break space-time. Okay? As we understand it. Okay, so it's definitely the fastest I can go. So one Planck time is about 10^(-44) seconds. So if I want to write down all googol symbols, to get this number that's just shy of Rayo, (Brady: You don't know what the symbols are. They'll be some...mystery.)
- Nah, I don't know. Yeah, nah. There's something. There's a way to do it. Let's assume we know what it is, okay? We're not gonna waste time trying to work it out, we know it. It's just there. It's been given to us in some divine way. How long is it gonna take us to write down all googol symbols? Well, we're gonna take 10^56 seconds. Now, how long is that? Well, that's about 10^48, 10^49 years. Have we got enough time to write that down? Well, that kind of depends on the on the nature of dark energy, actually at the moment. What's happening with dark energy, you know, the moment the universe is having this accelerated expansion and what happens next - sort of will tell us whether we've got time to write down this number. If dark energy goes away, there's a possibility the universe could crunch and we'll never get to these times. There's a possibility the dark energy could get even more accelerated, with acceleration speeding up, and this would be quite exotic, but then the universe would rip apart before we got to this number. But neither of these possibilities I think is the most likely, I think the most likely is that dark energy is constant and we're gonna just sort of...the universe is gonna die a slow and relatively painless death. So in 10^48, 10^49 years, at that point, what will happen then is we will find ourselves in the era of Black Hole Dominance. So what that is, that's the time when basically all the matter of the universe, has either just disappeared to sort of unimaginably far distances or it's collapsed inside supermassive black holes. So the universe is being patrolled by supermassive black holes that are swallowing everything and they dominate. So we're still writing down our symbols, we write down the last symbol, we'll either be doing it in, sort of, empty space where nobody is anywhere near us, for unimaginably large distances or we'll be doing it inside a supermassive black hole. But we can write it down! [Outro]
"you've actually done a computerphile video about busy beaver numbers" ...... Brady knows he doesn't actually have much to do with computerphile anymore
This was a cool video, but I don't think Rayo's number is really that interesting, considering it's uncomputable. We have no way of estimating how big it is in terms of computable functions, which is really the only way to get your head around it. Loader's number is more interesting because it's the largest number anyone has defined in 512 characters or less in C, and theoretically any computer could (eventually) calculate it. It dwarfs other large computable numbers like TREE(1010100)
Those tools that were introduced as a matter of fact, the 1st order set theory, 2nd order logic, are way, way over my capacity for comprehension. I went to wikipedia for more info, that did not help at all. My B.Sc. with minor in math got me through most of the Numberphile videos but I've hit a wall here.
Loved the video and the illustrations, Brady!