Root Causes 453: It Turns Out Monkeys Couldn't Type Shakespeare After All

Episode Transcript

Lightly edited for flow and brevity.

• 

  Tim Callan

  Alright, so this is a fun one. You spotted an article in something called New Scientist, which is not a journal I'm familiar with. This was written by James Woodford, October 31, 2024. So Halloween day. Here's the headline, Chimpanzees Will Never Randomly Type the Complete Works of Shakespeare. So, in case anybody doesn't know this idea, what are they referencing here, Jason?

• 

  Jason Soroko

  Tim, I don't know if it's an old person thing. It's been around forever, but, the old infinite monkey theorem, which definitely not an official thing, but basically, if you had an infinite number of primates or some entity, and you put them in front of a typewriter, how quaint. That's what ages this theorem. You put them in front of a typewriter, infinite number of typewriters, they would, given enough time, type out the entire works of Shakespeare.

• 

  Tim Callan

  Here's the subhead. The infinite monkey theorem states that illiterate primates could write great literature with enough time, but the amount of time needed is much longer than the lifespan of the universe. So basically, I think what someone did is they figured out how many keys were on a keyboard in an old fashioned typewriter - because it's going to be a little different on your computer - and then they came up with some kind of rate at which the monkeys would type. I don't know, a key per second, or whatever you come up with, and then they calculated the total number of combinations that it would require of those to get the complete works of Shakespeare and not surprisingly, it's a stratospherically large number. Like if you want to say, I don't know how many keys are on the keyboard, but if you count the shift, if you want to say you've got a total of 80 possible things you might type, then what you got to do is it's 80 to the first, 80 to the second, 80 to the third, 80 to the fourth, etc., and you count up the number of characters, including spaces in Shakespeare, and it's an awful lot. That's a big, big number. I'm not at all surprised that a monkey couldn't do that within the lifespan of the universe. But I imagine that's what was done. Is that your impression of what went on here?

• 

  Jason Soroko

  I think what some people have done is say, look, we have to put some bounding boxes around this and show just how hard this would be. I think the original theorem was really to try to help people to think about the size of infinity. You and I talk about prime numbers, large numbers in this podcast, and when you get into large enough numbers, you get into large enough anything, the human brain does a really bad job at scaling to make understandings at that size of things. What these scientists have done is actually start to put some bounding boxes around this to actually say, well, what actually is the chance of this? It turns out it's brutally brutal.

• 

  Tim Callan

  It's just a fun exercise. But yes, I'm sure that number is just enormous.

• 

  Jason Soroko

  Tim, maybe we should talk to Dr. Dustin Moody about the difficulty of putting a large number of monkeys in front of typewriters. If you think about like even just the current population of chimpanzees, apparently, there's about 200,000 in the world, and if you gave them a lifespan of one googol years, that's one followed by 100 zeros.

• 

  Tim Callan

  Which is much longer than the expected lifespan of the universe by any current theory.

• 

  Jason Soroko

  Then you're assuming that you're typing one key every second for every second of the day, etc, etc. Apparently, the number that they came out with was the chance that in the entire time that one of those chimpanzees would exist, there'd only be a 5% chance that they even come up with one simple word like banana in the lifespan of one chimpanzee. Therefore, you talk about the entire works of Shakespeare, that's an awful lot of words. And so if you then extrapolate that to alright, how many chimpanzees do you have? How many typewriters do you have? How many words are you actually going to bang out that actually turn into English words, it turns out the universe will have turned into the next universe. Like it just simply won't exist.

• 

  Tim Callan

  Now there are some factors working in favor of the chimpanzees that I'm sure these people thought about, because presumably these are smart people, which is, for instance, you can tell the works of Shakespeare in any order as long as you type. So it's not just one combination. You don't have to start with the first play and end with the Tempest. You can do it in any order you want. So it gives you more outs, if you will.

  If you go back to the original, there weren't any stage directions, and it's very traditional to put stage directions in, the most famous one being exit pursued by bear. But you don't need those. You could have them or have some and not others. That also gives you more outs. If you got something that was the complete works of Shakespeare, but one of the stage directions was apocryphal, or let's say misspelled, I could contend that you still met the qualification so that would open the door up to a lot more outs than you think you have. You have many more than one outs. Nonetheless, even accounting for all of that, you still have an absurdly difficult problem that has been made easier by such a tiny fraction that you can't even notice it.

• 

  Jason Soroko

  Going right off of what you just said, one of the quotes that is, I think it's been on TV recently, and I'll re-paraphrase it here, which is, even if you took a shorter book, let's say Curious George, which apparently is around about 1800 words, if you do the arithmetic, even getting that work, even getting those 1800 words before the end of the universe would, there'd be pretty much zero chance of it. So there you go.

• 

  Tim Callan

  So that says it all. That says it all. Now this is fun and interesting. And why are we discussing this on a cryptography podcast, Jason?

• 

  Jason Soroko

  I think that it comes down to this. There's a lot of talk these days about the NIST rounds, post-quantum cryptography, all of us still to this day - -

• 

  Tim Callan

  And just attacks against RSA.

• 

  Jason Soroko

  That’s what I was just gonna say. Attacks against RSA. Understanding why elliptic curve cryptography is hard. I think, and that's beautiful. Any of these things that are difficult and hard make for the basis of cryptography. And so when you're trying to think about something that is as large as the problems posed by something even as simple as the chimpanzee theorem, Even computers that we perceive as being very, very fast as compared to our human brains, they're still not even fast enough to solve some of these truly large, large space problems which are posed by things like lattice mathematics, post-quantum algorithms. I think that this coming up in the news, this chimpanzee theorem, I think it was just a nice reminder about just how darn difficult it is to think about large spaces.

• 

  Tim Callan

  I think for your average person who isn't thinking about it in these terms, the numbers can be deceptive. And I remember you and I talking years ago on this podcast about the problem that a bunch of CAs faced, where they had one bit too few of entropy in their serial number.

  And you made the argument, which was correct, which is to say, look, this might not seem like much. Might say, ah, you went from 40 bits to 39 bits, what's the big deal? And the big deal is half your key space. And so, add one more character to Shakespeare, and if we say there's, again, 80 things you might be able to type on a traditional typewriter, add one more character in the end, and you just increased the total number of things you might need by 80. And so every time you do that, you increase it again, which is why the Curious George thing gets so crazy, so fast, and just the power of exponential expansion. I think for your average person who's not thinking about, I think for us intuitively, living our normal lives in the real world, there's a strong tendency not to really give credit kind of emotionally and off hand to the power of exponential expansion and how really crazy it is.

• 

  Jason Soroko

  Let me draw an analogy that came from our podcast, and I find it fascinating. I can do this pretty quickly. Most of us who walk around, Tim, are exactly as you said. We have to admit that we do not have an intuitive understanding of these large numbers and large spaces. However, if you think about a person who does have to work in that realm on a daily basis, let's talk about a guy like Bas Westerbaan, who was on not that long ago. If you notice when he talked about key lengths, when he talked about the problems associated with large key lengths and signatures on our podcast, if you listen to his patter, his talking just out loud, out of his mouth, some of the words he was using was to remind himself of the size of the space of key lengths. He was actually doing that, if you listen to how he was speaking. Even a person who lives thinking about large number spaces is constantly having to remind themselves of one large space versus another large space. That even came out in his vocabulary, Tim. That's how hard this is.

• 

  Tim Callan

  That's another thing where numbers, once numbers hit a certain size, they kind of all seem the same to us. Our intuitive minds are walking around in the physical world minds, and you hear people say things all the time. They'll say, you say, what's the chance of this happening? And they'll go, oh God, one in a million. I mean, like, it's probably 99% likely. And you're like, okay, well, you just said one in hundred and one in a million. They're completely different things. Which one is it? This kind of thing goes on all the time in people's minds, where 99% likelihood of success and one in a million chance of failure kind of get lumped together in the same bucket, and they're not remotely the same bucket. That's what's hard for all of us to really get these numbers and understand them correctly, kind of at an intuitive and emotional level.

• 

  Jason Soroko

  A million, a billion, a trillion. We're not talking apples and apples. Like that is the truth and some of these large spaces we're talking about, in the realm of cryptography, go even well beyond those large numbers. It just makes it even more difficult to think through.

• 

  Tim Callan

  Then it also doesn't help that, when we're doing things just with powers, two to the 32nd versus two to the 33rd and you go, 32, 33 what's the difference. The difference, of course, is twice as much. That sort of thing doesn't help either.

• 

  Jason Soroko

  In fact, even on that like, why is that the case? There's a reason for it. The beauty of exponential numbers and exponents themselves is that it's a way to very, very quickly annotate onto a page these number spaces. The problem is that they're not human intuitive, because the fact that our brains tend to think that things that are very close to each other are very similar, but the whole nature of exponents is that they are not. Anyway. It's interesting. And Tim, this story came up, and I just had to share it.

• 

  Tim Callan

  We had to share it. We need to do a fun one. We're so heavy about stuff, once in a while we need to do a fun one. I'm glad we did a fun one.