254
$\begingroup$

Of course, we've all heard the colloquialism "If a bunch of monkeys pound on a typewriter, eventually one of them will write Hamlet."

I have a (not very mathematically intelligent) friend who presented it as if it were a mathematical fact. Which got me thinking... Is this really true? Of course, I've learned that dealing with infinity can be tricky, but my intuition says that time is countably infinite while the number of works the monkeys could produce is uncountably infinite. Therefore, it isn't necessarily given that the monkeys would write Hamlet.

Could someone who's better at this kind of math than me tell me if this is correct? Or is there more to it than I'm thinking?

  • 4
    Here's an interesting Wikipedia link about "actual experiments." http://en.wikipedia.org/wiki/Infinite_monkey_theorem#Random_number_generation2011-01-12
  • 22
    Note that the set of finite-length strings of characters (i.e. "works") is *countably* infinite, not uncountable.2011-01-12
  • 3
    Related: http://math.stackexchange.com/questions/10658/monkeys-and-typewriters/2011-01-12
  • 4
    @Jason It will take less than infinite time and infinite monkeys, if you are willing to learn a new language.2011-01-12
  • 42
    Doesn't one monkey suffice?2011-01-12
  • 19
    http://dilbert.com/strips/comic/1989-05-15/2011-01-12
  • 4
    If this was posted at physics.stackexchange.com, there will probably be discussions on whether time can be infinite and the cardinality of the set of multiverses.2011-01-12
  • 0
    When calculating likelyhood.. don't forget that monkeys will be more likely hit a group of letters in the same area of the keyboard then to press one at a time..2011-01-12
  • 82
    “We’ve all heard that a million monkeys banging on a million typewriters will eventually reproduce the entire works of Shakespeare. Now, thanks to the Internet, we know this is not true.” (Robert Silensky)2011-01-12
  • 5
    Since monkeys doesn't have an infinite lifespan, infinite time won't do you much good. Try to get your hands on an infinite number of monkeys and an infinite number of typewriters instead.2011-01-12
  • 2
    After the monkey has finished writing Hamlet he will not take a break and say "Wow, I've written something great!" He will just keep on typing.2011-01-13
  • 0
    @Jason Given infinite monkeys and infinite time, you would have more pressing issues at hand! :)2011-01-13
  • 0
    @EdGuiness Thou shalt giveth it enough time and thou shalt see. We art working on it.2011-01-13
  • 0
    Footnote - it might be Robert Wilensky (not Silensky) according to this... http://seclists.org/politech/2000/Oct/172011-01-13
  • 2
    Most answers I read so far are assuming that a monkey would end his work when he reached the number of words (or characters) Hamlet has. But shouldn't we assume that monkeys are writing sometimes more and sometimes less words?2011-01-13
  • 0
    I do not think that the solution has been well defined. For instance, can Hamlet appear fully between strings of other text or would that not count? Are we assuming these monkeys are typing random patterns? There are so many variables that have not been constrained at all here...2011-01-13
  • 2
    Sounds like something that should have been in the Hitchhiker's Guide.2011-01-14
  • 4
    @muntoo EDIT: “Ford! There’s an infinite number of monkeys outside who want to talk to us about this script for Hamlet they’ve worked out” (chapter 9, H2G2 Bk1)2011-01-14
  • 1
    @Jason Serious question. I understand why numbers are countably infinte. But why are the works that will be produced uncountably so?2011-01-14
  • 0
    @abel: See Qiaochu's answer.2011-01-14
  • 10
    I closed this question as it's attracting a lot of "fun" answers which aren't helpful. I also marked it community wiki so these "fun" answers aren't reputation factories for stuff that really isn't about math.2011-01-15
  • 2
    Let's close it again. Too much trash accumulates here.2013-02-19
  • 2
    There's a very amusing short story about this by R A Lafferty, called ["Been a Long, Long Time](http://www.isfdb.org/cgi-bin/title.cgi?58333)". You might be able to find a copy -- it's been in a few anthologies.2011-01-12
  • 0
    @GWLlosa: ...and this one: http://dilbert.com/2013-12-12/2013-12-22
  • 2
    @Jason Everyone here needs to brush up on their logic. The statement begins "If a bunch of monkeys pound on a typewriter [forever]". Thus, it is vacuously true that given this, they will produce Hamlet. It is also vacuously true that given this, they will not produce Hamlet.2014-03-16
  • 0
    The answer is no because monkeys would press two buttons at the same time, not type completely random and would eventually become bored or hungry and thrash the place or attack each other. As empirical evidence has proven.2014-07-17
  • 0
    Indeed the probability that some string is not a substring of the first $n$ letters falls exponentially. So we'd get the substring very fast ;-)2015-01-15
  • 0
    I'm pretty sure said monkeys evolved or would evolve into humans who actually wrote "Hamlet". Q.E.D2015-04-27
  • 0
    How many monkeys are needed to validate result?2017-08-17

14 Answers 14

0

Consider the following premise:

There are a (countably, obviously) infinite number of monkeys, each with a typewriter, and each equipped to type for an infinite amount of time.

Given this premise, assume the following:

The first monkey types “$kpkpkp...$”, repeating this sequence infinitely.

The second monkey types “$kkpkkp...$”, repeating this sequence infinitely.

The third monkey types “$kkkpkkkp...$”, repeating this sequence infinitely.

...

The $n^{th}$ monkey types “$kk...kpkkk...p...$”, repeating a sequence of $n$ $k$’s and then a $p$ ad infinitum.

Now, it’s true that I have dictated what each monkey will type, but even so, ask yourself the following:

1.) Is this an infinite number of monkeys typing for an infinite amount of time?

2.) However unlikely this particular scenario may seem, is it a $POSSIBLE$ outcome of the given premise?

3.) Is each monkey’s “manuscript” unique?

4.) Will any of these monkeys ever type $Hamlet$? Or $Speed$ $2$? Or even an existing English word? (If so, which monkey will be the one, since we already know what each will put forth?)

The answers are quite obviously “yes” to the first three questions, and “no” to the last.

Again, although I’ve dictated a very specific prescription that this set of monkeys must stick to, this is still a counterexample (this is not a question of probability!). That is, nothing guarantees that this scenario won’t happen.

Hence, the reproduction of $Hamlet$ is not guaranteed.

313

I found online the claim (which we may as well accept for this purpose) that there are $32241$ words in Hamlet. Figuring $5$ characters and one space per word, this is $193446$ characters. If the character set is $60$ including capitals and punctuation, a random string of $193446$ characters has a chance of $1$ in $60^{193446}$ (roughly $1$ in $10^{344000}$) of being Hamlet. While very small, this is greater than zero. So if you try enough times, and infinity times is certainly enough, you will probably produce Hamlet. But don't hold your breath. It doesn't even take an infinite number of monkeys or an infinite number of tries. Only a product of $10^{344001}$ makes it very likely. True, this is a very large number, but most numbers are larger.

  • 52
    In fact one monkey alone would write Hamlet an infinite number of times given unlimited time.2011-01-12
  • 7
    @Sean: not original with me. I saw it in Martin Gardner's column many years ago.2011-01-12
  • 82
    But what is even more alarming, is that the same monkeys - and probably (in the mathematical sense of the word) within the same time limit mentioned above by Ross Millikan - will write Hamlet with every possible typo imaginable.2011-01-12
  • 28
    @Fredrik Meyer: ...and there was I thinking the decline of English was down to textspeak and all forms of youthful disregard for conventions; when actually the inaccurate spelling movement is being led by a band of thespian-tendencied research monkeys.2011-01-12
  • 3
    all non-infinite numbers are small2011-01-12
  • 0
    "this is a very large number, but most numbers are larger" Is there any practical number larger than this? Number of atoms in the universe perhaps?2011-01-12
  • 2
    @Louis Rhys: It is thought that the number of particles in the universe is less than $10^{100}$.2011-01-12
  • 133
    "but most numbers are larger". Not really. There's this infinite set of negative numbers to contend with. :)2011-01-12
  • 0
    So no practical/meaningful number is larger than that?2011-01-12
  • 6
    @Louis Rhys: Graham's number is a famous example of a meaningful large number. It's an upper bound to an open problem in Ramsey theory.2011-01-12
  • 0
    @Ross Millikan: "this is a very large number, but most numbers are larger" -> why would I accept this statement insted of "most numbers are smaller"?2011-01-12
  • 8
    @darocig: It depends upon what set you are working in. For $\mathbb{N}$ there are only finitely many smaller, and infinitely many larger. For $\mathbb{R}$, however,...2011-01-12
  • 5
    @Haacked When imaginary numbers were explained to me I was told that the _idea_ of an imaginary number is a lot like a negative number; they don't _really_ exist but to solve a problem. You can't have negative apples.2011-01-12
  • 0
    Hmm.. I suck at math but what I think you did here is to determine the chance for a monkey that writes "a random string of 193446". The question does not specify that. Isn't the problem domain infinite?2011-01-12
  • 1
    @Cristian: this is the chance that a monkey writes a given string of 193446 characters, assuming all strings are equally likely. The problem domain is not infinite as there are only 60^193446 strings of that length.2011-01-12
  • 7
    There has already been consideration of some ability to manage the monkeys: you need the [Infinite Monkey Protocol Suite--RFC2795](http://www.ietf.org/rfc/rfc2795.txt).2011-01-12
  • 3
    I hate to have to be the one to say this, but infinity is not a list of all numbers one could dream up. There is an equally likely chance that an infinite number of monkeys on typewriters will produce all the works of the universe with the exception of any Shakespeare what so ever, just as there is they may produce a limitless supply of nonsense. Infinity is not a list of numbers, for example, infinity may hold multiple infinities.2011-01-12
  • 2
    @user4014 - I suppose that's a good point. I'm reminded of this dilbert comic: http://dilbert.com/strips/comic/2001-10-25/2011-01-13
  • 0
    You guys have blown this WAY out of proportion. If you don't include whitespace, the numbers are much smaller. Number of characters: 194311 Number of non-whitespace characters: 135036 Number of unique characters: 64 Number of unique non-whitespace characters: 51 Number of permutations: 4.33e350960 Number of permutations ignoring whitespace: 2.79e2305832011-01-13
  • 0
    @David I got some of those for my birthday!2011-01-14
  • 4
    @Incognito That's not correct. If you have an infinite sequence of random characters, the probability of it not containing the works of Shakespeare is 0 (or said differently, as the size of the stream of characters grows toward positive infinity, it approaches 0). Unless you are arguing that monkeys are not perfectly random and thus might fall into some sort of repeating pattern.2014-03-12
  • 0
    Apparently there are 175090 characters in Hamlet (if you use the version here: http://shakespeare.mit.edu/hamlet/full.html) - so it is slightly more likely ;)2015-02-08
  • 0
    I think that semantically, the word "most" only applies to finite quantities and therefore doesn't make sense in the context of infinite numbers.2015-05-02
  • 0
    @jeremyradcliff: there are various ways "most" can be applied to infinite sets. If the naturals are divided into a finite set and an infinite set, "most" or "almost all" numbers are in the infinite set. You need some concept of measure to do so. Similarly, most reals are irrational.2015-05-02
  • 0
    @J.G: No, I am not a moderator.2016-02-04
121

Some references (I am mildly surprised that no one has done this yet). This is called the infinite monkey theorem in the literature. It follows from the second Borel-Cantelli lemma and is related to Kolmogorov's zero-one law, which is the result that provides the intuition behind general statements like this. (The zero-one law tells you that the probability of getting Hamlet is either zero or one, but doesn't tell you which. This is usually the hard part of applying the zero-one law.) Since others have addressed the practical side, I am telling you what the mathematical idealization looks like.

my intuition says that time is countably infinite while the number of works the monkeys could produce is uncountably infinite.

This is a good idea! Unfortunately, the number of finite strings from a finite alphabet is countable. This is a good exercise and worth working out yourself.

Edit: also, regarding some ideas which have come up in the discussions on other answers, Jorge Luis Borges' short story The Library of Babel is an interesting read.

  • 21
    @Jason: of course, the theorem isn't really about monkeys. It's about a particular model of monkeys. (Mathematics cannot prove anything about the world: it can only prove things about models of the world.) One can argue, as so many are doing in this thread, for or against this model, but when people quote this result I am assuming that they are referring to the model.2011-01-13
  • 0
    @Qiaochu - I noticed that. It doesn't make the idea of an "infinite monkey theory" any less amusing though. ;-)2011-01-13
  • 3
    As Borges said, Infinites and Mirrors are evil.2011-01-14
  • 2
    @Trufa "¿De qué otra forma se puede amenazar que no sea de muerte? Lo interesante, lo original, sería que alguien lo amenace a uno con la inmortalidad."2011-02-03
  • 1
    @Trufa: I don't understand. I gave that link in the second sentence.2011-02-03
  • 0
    @Qiaochu I'm sorry! deleted my comment. I was looking for the wrong description! My bad, agan, sorry! :(2011-02-03
  • 8
    I imagine the reason is no, and for relatively simple reasons. Monkeys won't see the use of typing. After at most a few keypresses they'll either get bored or destroy the typewriter in a fit. I doubt an infinite number of monkeys could even put together a full page full of nonsense but reasonable-length words with punctuation. You could ask the same question about spiders. Put an infinite number of spiders on typewriters and they won't produce Hamlet either, mostly because most spiders lack the strength to type.2011-12-02
  • 0
    This answer is garbage. The zero-one law is not needed to show that the probability of (one or more) monkeys typing Hamlet eventually is 1. In fact neither Borel-Cantelli nor 0-1 are needed unless we want to know the probability of Hamlet appering infinitely many times. Simply showing that it will appear once is a straightforward application of naive probability theory (find the probability that it will never appear). Even if you were mathematically correct, you haven't *explained* anything about the 'mathematical idealization'. All you have done is provide *names* (and links to Wikipedia).2013-08-01
  • 1
    Russell Maloney's short story "Inflexible Logic" concerns a slightly eccentric bachelor gentleman who borrows six chimps from the zoo and sets them to work at typewriters.2015-03-12
  • 1
    @RyanBudney Certainly possible, consider that we were once monkeys of kind or another. We "monkeys" didn't even need a infinite amount of time to write hamlet! So it seems very likely that modern day monkeys could do the same. (I assume you accept evolution and the colloquial use of "monkey")2015-04-27
  • 1
    @Zach466920: there's no reason to expect monkeys trapped in a room with typewriters would evolve towards something that would use typewriters for their original purpose. Presumably they would find better things to do with them in the short term.2015-04-27
104

[Note that in my answer I am actually assuming that there are only a finite number of monkeys. I don't see what is gained by having both the number of monkeys and the time frame be infinite: mathematically speaking $\aleph_0 \times \aleph_0 = \aleph_0$, and it is somewhat confusing to contemplate infinitely many monkeys typing simultaneously: too much is happening at once. In fact, there might as well be only one monkey, or at any rate only one typewriter.]

Let me take the unusual (for me) step of considering the practical aspects of this question as well.

As Ross Millikan has explained, there is a simple mathematical model of monkey keyboard pounding under which it is easy to see that the claim is true: the probability that at least one of the monkeys will type out Hamlet approaches $1$ as the time $n$ approaches infinity.

However there is an assumption here: namely, that the pounding on the typewriter is random or sufficiently close to random. One way to formalize this is to say that after typing any $n$ characters, the probability of hitting any given key as the $n+1$st character is at least $P$, where $P$ is positive and independent of $n$.

The problem is that for actual typewriter banging, this is a very unlikely assumption. The issue is similar here to what happens if you ask someone to produce a random sequence of digits, say from $0$ to $9$, or even a random sequence of $H$'s and $T$'s (for "heads" and "tails"). Just closing your eyes and banging away will produce something very far from being random.

If the question is meant to apply to actual monkeys with their nonrandom motor behavior, then it is something else entirely. I would be tempted to say that the probability of producing Hamlet does not approach $1$ as time approaches infinity, but I'm not sure off the top of my head how to justify this.

  • 35
    Pete: I think this might be my favorite answer to any question ever. I know you meant it seriously, and it is certainly a well thought answer, but I find some of the phrases hilarious. Only a mathematician could write the phrase "there is a simple mathematical model of monkey keyboard pounding".2011-01-12
  • 15
    Dear Pete, The paper [Power laws for monkeys typing randomly: the case of unequal probabilities](http://math.stanford.edu/~conrad/papers/powerlaw.pdf) has some relevance to the issue considered in your answer, I think. Regards,2011-01-12
  • 2
    @Sean: yes, I was serious, and yes, I had an unusual amount of fun writing it. I'm glad you enjoyed it.2011-01-12
  • 4
    This reminds me of a Dilbert strip: http://clipmarks.com/clipmark/4905F106-063A-401C-8631-392E2E49652A/2011-01-12
  • 37
    I believe there was an actual experiment done with monkeys in a room with typewriters to see what exactly they would produce. If I recall correctly the monkeys destroyed the typewriters, science.2011-01-12
  • 7
    @Jacob Schlather. Not only did they destroy them, they treat them like toilets, too.2011-01-12
  • 0
    @Jacob, Atømix: I guess in a model that incorporates this, the probability does not go to 1 as the time goes to infinity, then :-)2011-01-13
  • 2
    @Jacob Schlather I recall reading that the monkeys had an almost exclusive preference for the letters 's' and 'l', though the choice of letter varied by monkey.2011-01-13
  • 1
    Even if the pounding of keys by monkeys is not entirely random, as long as every sequence of characters has probability > 0 of happening, then yes we can say the probability here is 1 of the monkey typing out hamlet. I also think we need to define "slamming the keyboard" more precisely for this question to be answerable. For example, a normal human slamming the keyboard would never produce the same character 3 times in a row. But this may not be true for monkeys. In conclusion, if the slamming is define in such a way that each sequence of keys is possible, no matter how small the2011-01-15
  • 0
    probability, then clearly the probability of the monkey typing hamlet is 1. Otherwise it is 0. Note that we are dealing here with an infinite amount of time and therefore as long as the probability of something happening is >0, it has probability 1 of happening over an infinite amount of time.2011-01-15
68

If you have an infinite number of monkeys, then an infinite subset of them will just sit and type out Hamlet, letter-for-letter, straight away. So after a few hours you will have an infinite number of copies of Hamlet.

If you have a finite number of monkeys then you may have to wait. But given in infinite amount of time (and immortal monkeys, etc.), you'll get your Hamlet. Eventually.

  • 11
    So infinite monkeys, no problem; finite monkeys, request infinite improbability drive for Christmas present. This poses the question, how do you count your monkeys?2011-01-12
  • 1
    I wonder whether they will be charged for copyright infringement in that case...2011-01-12
  • 40
    Fortunately, Hamlet is out of copyright. But they'll also write copies of everything that is in copyright, plus hexadecimal representations of binary files for every copyrighted movie, TV show, recording, etc., so they're still in big trouble.2011-01-12
  • 35
    The problem is distinguishing the correct copies of Hamlet from the infinite number of copies with significant typographic errors --- for example, the one in which Hamlet and Ophillia create a time machine and run off together to America.2011-01-12
  • 3
    @Orbling With an infinite improbability drive you get whales, not monkeys :D2011-01-14
  • 2
    @Orbling @belisarius “Ford! There’s an infinite number of monkeys outside who want to talk to us about this script for Hamlet they’ve worked out” - Arthur Dent (chapter 9, H2G2 Bk1)2011-01-14
  • 2
    @belisarius: Flying whales at that, well falling whales. Not sure whales have the same knack for prose.2011-01-14
  • 2
    @muntoo: Classic. Those books are so very quotable.2011-01-14
  • 3
    @Orbling And the quotes are _mostly harmless_2011-01-14
  • 3
    And if they are typing in a language, say C++, they might create a superbot.2013-10-28
  • 1
    In other words, all that matters is that the number of monkey-hours is infinite.2016-06-18
23

You don’t even need an infinite number of monkeys! For any $\epsilon > 0$ and $k \geq l(\text{Hamlet})$, there is some number $N$ such that $N$ monkeys at typewriters, each typing for $k$ keystrokes, will produce a copy of Hamlet with probability greater than $1-\epsilon$. (This holds under some quite weak conditions on our model of monkey typing.)

This is an example of the general “soft analysis to hard analysis” principle, championed by Terry Tao among others: most any proof in analysis may be transformed into a proof of a quantitative statement such as the one above.

This can be made precise in some generality using various rather beautiful proof-theoretic methods, such as variants of Gödel’s Dialectica translation; lovely results along these lines have been obtained by e.g. Avigad, Gerhardy and Towsner. In this particular case, the bounds we get will of course depend on the model of monkey typing used.

For instance, if we assume that the keystrokes are independently uniformly distributed, if our Hamlet-recognition criterion is case-, punctuation- and whitespace-insensitive, then for the case $k = l(\text{Hamlet})$,

$$N = \left\lceil \frac{\log \epsilon}{\log \left(1 - \frac{1}{26^{l(\text{Hamlet})}}\right)}\right\rceil$$

will work. (The proof is an exercise for the reader.)

Project Gutenberg’s copy of Hamlet (first folio) weighs in at 117,496 alphanumeric characters. So if we want to produce Hamlet (first folio) with probability 1/2, in the minimal number of keystrokes, then by some quick slapdash estimating (rounding up a little to be on the safe side), something like $10^{170,000}$ monkeys should certainly suffice!

I guess empirical testing is out — ethical controls are so tricky. Anyone want to run some simulations?

  • 2
    Oops — I see now that my answer overlaps somewhat with Ross Millikan’s excellent one above. However, there is a fair amount that is different, so I will leave this nonetheless…2011-01-13
16

It would probably be faster to apply selective pressure to breed intelligent, literary monkeys. Our common ancestor with chimps lived only 4 million years ago, and by design I'm sure we could make something similar happen faster starting with chimps, bonobos, or whatever.

We could probably get orcas and other whales up to speed very quickly, too!

  • 8
    What is the probability that I now read the word bonobo for the SECOND time today after a lifetime of never having heard it - ahh the internets...2011-01-12
  • 3
    Even if you do that, why would they produce an exact copy of Shakespeare? I mean almost surely their history will be different than ours.2011-01-13
  • 4
    @timur True; you would have to reproduce the exact conditions that lead to Hamlet it produce the same exact text at the same exact time. Or, as Carl Sagan put it, "If you want to make an apple pie from scratch, you must first create the universe."2011-01-13
  • 0
    No, just pay them minimum wage to write it out. Before they become smarter than us and destroy the Statue of Liberty!2011-01-14
  • 2
    Apparently Hollywood is already halfway there, judging by their product.2011-01-14
9

For some reason I want to attribute this reasoning to Douglas Hofstadter, though I couldn't tell you which of his books it's from. Here goes:

If you could get sufficient randomness from an infinite number of monkeys (this is trivial if you assume that by mere chance, a infinite subset will fit the bill – or you could follow Arjang's approach and aggregate across monkeys for more entropy, which has the benefit of getting results much faster), you already have every variation of every story ever told. You'll even have every story that ever could be told. Just get an infinite number of monkeys (or a slightly smaller number of computers) and opening a publishing business. Make a million bucks and retire.

But this rings false, especially since modern computing power (relative to the difficulty of the task) is practically infinite, putting the practice of this philosophy within reach. Just imagine trying it yourself. It's not the monkeys or the computers or the printers doing all of the work. Suddenly, you are wading through millions of pages of gibberish text looking for the book that will make you rich. Good luck. (It is the fact that the filtering process is much slower than the production process that makes me say that computer power is practically infinite.)

It's not the characters on the page that make Hamlet. Hamlet is a synthesis of information, a composition that can only be guided by intelligence. In a sea of random characters, the sequence that maps isomorphically to Hamlet is just more noise.

This may sound like a qualified "yes" in response to the question, but in reality it is an empathic "no." It is not the act of producing the character sequence of Hamlet in a random string that writes Hamlet – it is the act of finding Hamlet in a random string that writes Hamlet. The distinction may sound subtle, but the two tasks are profoundly different.

  • 5
    *"modern computing power […] is practically infinite"* — I think you misunderstand what "infinite" means. "A very large number" is not "practically infinite". In fact, the world's total computing power isn't even, "relative to the difficulty of the task", close to 10^344000, which is roughly how big you need things to be for Hamlet to be produced. It's a minuscule insignificant fraction of that, which means that we have no chance of generating Hamlet today by an actual uniform random process. Yes, if it *were* generated, we'd have trouble finding it, but that's a far out concern.2011-01-13
  • 2
    @ShreevatsaR *A very large number" is not "practically infinite".* I think the stress should be the word "practical" rather than "infinite." If the value could be either its current value or infinity without changing the bottleneck task (qualitatively or quantitatively), how is that anything other than practically infinite? It would be been better if I'd clarified that point more explicitly and earlier in the paragraph, though.2011-01-13
  • 0
    @ShreevatsaR *Yes, if it were generated, we'd have trouble finding it, but that's a far out concern.* On second thought, though, I think this is where our opinions diverge. In my opinion, this is a more fundamental point than physical limitations, or even the theoretical implication of infinity. You could say I played a sly trick in redefining "generating Hamlet," but I was really trying to make a point about the nature of information. To sum it up differently, I would say, "The question is irrelevant, because data is not information without context." Or, in Hofstadter's words, "Mu."2011-01-13
  • 0
    As far as I can see, the question is not about whether we can sift through the generated text to find intelligent text ("opening a publishing business. Make a million bucks…"), but whether a *specific* long text (Hamlet) may be generated by a random process at all. (That is, it's not the question here, though it may have been Hofstadter's, knowing his concerns.) So that part is simply irrelevant. And if you're looking for Hamlet specifically (letter-for-letter), it's a rather simple task that can be done with almost the same amount of resources as stepping through the generated text.2011-01-15
  • 0
    @ShreevatsaR: Given the context, you could fairly say that I answered "the wrong question." I would even agree.2011-01-17
8

Let me be the one who says NO. It is a bit hard to handle an infinite number of monkeys (because you will need an infinite number of bananas to feed them), but if you agree to have a finite number of monkeys and infinite time, I would guess that considering the time it should take for this to happen, it is likely that the universe would die before it actually does.

To quote a chat of one of my friends with my first year "intro to CS" professor:

professor: "So there is no chance that a fair coin would fall with the head side up 50 times in a row."

my friend: "No!, there is such a chance it's just very small...."

professor: "Well yes, its like the chance for all the nitrogen molecules in the air to gather around your head and have you die from lack of oxygen."

  • 11
    Ultrafinitism takes out all the fun from mathematics. Especially from the parts dealing with infinite processes.2011-01-12
  • 15
    From a [ultra]finitistic perspective, I don't think you can say "NO"; you can only say that the question is meaningless as there's no such thing as infinite time or infinite monkeys.2011-01-12
  • 2
    And there would need to be an infinite amount of space to contain the monkeys... not to mention infinite typewriters... better ramp up typewriter production in China.2011-01-12
  • 1
    @ShreevatsaR Talk about practical thinking.2011-01-14
  • 0
    Also, I doubt the monkeys will specifically twist their hands for each letter. The QWERTY keyboard was designed to make it slower/harder to type, after all, so I doubt the mindless monkeys will go to all that trouble to contort their 'inferior' hands.2011-11-21
  • 0
    +1 for professor's quote, great metaphor for visualizing how unlikely such a small probability truly is.2017-05-10
  • 1
    But this quote from the professor is **very wrong**. The chance of 50 heads, $1/2^{50} \approx 10^{-15}$, one in a quadrillion, is indeed low: There are roughly one quadrillion hairs on people's heads on Earth, so it's the chance of winning a lottery where you have to pick the right strand of hair on the right person's head. But the chance of dying from lack of oxygen is **far, far lower.** If the chance of randomly not having any oxygen for 5 minutes were as big as $1/10^{15}$, then someone would die from "random lack of oxygen" every year.2018-03-04
  • 1
    Let's do a rough calculation. To die from random absence of oxygen, say you need around 5 minutes of no oxygen. During these 300 seconds, you might take 200 panicked breaths, each around 0.5 liters, so we are talking roughly 100 liters, or 130 grams, of air being oxygen-free. This is roughly 5 moles of gas, and each gas molecule has about a 4/5 chance of being something other than oxygen, so the chance of 5 moles $(30\times 10^{23} molecules)$ being oxygen-free is around $(4/5)^{30\times 10^{23}}=10^{-3\times 10^{23}}$. That's about $3 \times 10^{23}$ zeros after the decimal point!2018-03-04
  • 1
    The probability of flipping 50 consecutive heads, $1/2^{50}$, has just 15 zeros after the decimal point. Describing this number by falsely saying it is as small as a number with $3\times 10^{23}$ zeros after the decimal point is, to put it politely, an inaccurate comparison. The chance of dying from a random lack of oxygen is approximately the same as the chance of flipping $10^{24}$ consecutive heads. Not $50$ consecutive heads. Not even close.2018-03-04
4

The answer is yes, With infinite time and all of the infinite monkeys will produce hamlet and every other works infinitely many times.

After the first keystroke of the infinitely many monkeys, there will be infinitely many hamlets if you just grabbed the first letter from each one of them.

Also at the first keystroke, infinitely of monkeys would have types the first letter of the entire hamlet already, this shows that if you have infinite number of monkeys you only each one of them to type just as many letters as the number of letters in hamlet to have already infinitely many copies of hamlet, so there is no need for infinite time to have one of them produced hamlet, infinitely many of the monkeys would produce infinitely many hamlets in finite amount of time as long as the finite amount of time is equal or greater than the time to type a single copy of hamlet. (this was already mentioned in Bennett McElwee's answer)

If you rephrase the question to : Would an infinite random sequence of letters in 2 dimensions contain at least one hamlet in every and each one of it's columns/rows? then the answer is yes, but there would be infinite number of hamlets contained in each row/column, As an infinite random sequence will contain all it's possible finite sub sequences, infinitely many times. ( Reference needed ).

  • 0
    I suspect this is incorrect.. Consider a random sequence using only 1's and 2's. No reason why it contains all possible numbers especially 123 inside it.2011-01-12
  • 0
    @picakhu : edited, of course a sequence of 1's and 2's wont have a 3 in it! :) added the finite subsequence into edit2011-01-12
  • 0
    I think this is still incorrect.. Assume that a 11 is banned. so we can have a random sequence like 121222212221222122222222212121212221212 which has no sub-sequence 11 in it.2011-01-12
  • 0
    @picakhu : Why random sequence of 1's and 2's is not allowed to have 11? of course if a subsequence is always take out from the sequence then it will not occur.2011-01-12
  • 0
    any random sequence of digits not containing 0 can be encoded into 1's and 2's without having a 11 inside. for example consider the encoding where the number of 2's consecutively indicate the number being encoded. For example, 1234 may be encoded as 2122122212222 If we have a random sequence(containing 1-9), then the same sequence using the code is also random.(note we could also code for a sequence (0-9) in similar methods with a little modification). This perfectly random sequence has no 11 inside it.2011-01-12
  • 2
    @picakhu I could then just as easily say that the sequence 212 contains the sub-sequence 11 and the sequence 2122 does not contain the sub-sequence 22. If the interpretations are isomorphic, you are free to choose either one. That said, monkeys are unlikely to produce output that can be universally interpreted in more than one meaningful, non-trivial way. I.e., interpreting 'aa' as 'b' is meaningless in the general case, and the choice of computer character encoding (ASCII vs. UTF-8, say) is trivial. My point, I guess, is that random letter generators won't perform high-level encoding.2011-01-12
4

Monkeys don't produce a proper random distribution on keystrokes. Not even a Markov-chain of keystrokes.

Given infinite time (and an undying support of monkeys) or just infinite monkeys, they will produce infinite text. But that does not need to imply that Hamlet will be part of this infinite long text.


[edit]

There is empirical evidence from such an experiment, reported by the BBC.

The actual text produced is obviously not that random at all.

(@Henry: Thx for these links.)

[/edit]

  • 0
    Did you mean "perhaps" instead of "eventually"?2011-01-16
  • 0
    daah... yeah, of course. silly me. – The german word "eventuell" means "possibly" in english. It's one of those strange words... The inventor of the english language must have written some bugs in one of the first english dictionaries, which is now hardwired in the standard library.2011-01-27
  • 1
    *Monkeys don't produce a proper random distribution on keystrokes. Not even a Markov-chain of keystrokes.* How do you know?2011-11-11
  • 0
    Just look at the monkey, dude! Not better than a baby on the piano, nearly repeating the same wham from before. (Assumed that it's not Markov's child playing.)2011-11-12
  • 0
    This is what I call a zero-content comment. (But please learn how to use the @ thing, that is, if you want to actually reach the person.)2011-11-12
  • 3
    @Didier: There is empirical evidence from an experiment [reported by the BBC](http://news.bbc.co.uk/1/hi/3013959.stm) and I suspect that the [actual text produced](http://www.vivaria.net/experiments/notes/publication/NOTES_EN.pdf) would fail most test of randomness.2011-11-14
  • 0
    @Didier: Thx for the @ thing, I didn't know.2011-12-02
  • 0
    @Henry: Nice! I've known about such an experiment for a long time, but didn't think that it was published in the news. Thx for the reference!2011-12-02
  • 0
    The correlation between math and empirical data is at best coincidental.2011-12-02
  • 0
    @Asaf-Karagila: Yes, indeed. We need some pure mathematical definition of a monkey to argue about, so that we do not enter the category of empirical data. Something that doesn't depend on actual physical monkeys but relate to them. (Probably sth. like banana-brackets from category theory, which relate to bananas only in syntax.) But even using temporal logic, we can't exclude the possibility that the desired event won't happen in finite time.2011-12-09
  • 1
    Look at the photos in the second half of the book. The monkeys are not actually typing at all. They are just standing on some keys and the keys are then auto-repeating 10 times/sec or whatever. That is why you get pages of nothing but s. So I reject this empirical evidence. It shows monkeys standing - or resting their hands on the keys - not monkeys typing :)2012-09-26
  • 0
    @Henry What I like most about the BBC piece is the quote on the right column, saying "The work was interesting but had little scientific value, except to show that the "infinite monkey" theory is flawed" by some "Dr" who happens to be "Paignton Zoo scientific officer". "the "infinite monkey" theory is flawed"? Sure, dude, sure...2016-09-11
4

NOTE: By probability, I mean the chance of it happening per iteration, and starting with a new page each time.

Let's take a step back, shall we? (Not too many, because there's a cliff behind you.) Let's think of what the probability is of producing the following randomly:

A

Assuming there are only 26 characters (A-Z, uppercase), the probability would be $\frac{1}{26}$.

What about this:

AA

It'd be $(\frac{1}{26})^2$. This:

AAA

It'd be $(\frac{1}{26})^3$. And this:

XKCD

It'd be $(\frac{0}{26})^4$. [Just kidding, it's: $(\frac{1}{26})^4$].

So, for every character we add to the quote, it will be: $(1/26)^c)$, where $c$ represents the number of characters.

Basically, it would be a probability of $(\frac{1}{26*2+12})^c$ since the characters used could be: A-Z, a-z, .!?,;: "'/() Of course, there could be more characters, but that's just an example. :)

  • 3
    Could I please have the ability to downvote myself? 10 months and 6 days later, I find out that I am an idiot.2011-11-21
  • 2
    You can delete the answer, right?2012-02-27
  • 1
    Don't be so hard on yourself! Maybe this is proof that given a finite amount of time, a human with a keyboard will type... ________ ???2012-02-28
  • 0
    Upvote from me. This is a genius answer, you proved the opposite, muntoo. (kidding, no offense :)2012-06-06
3

Here's a rather interesting article discussing the probability of a monkey producing Shakespeare's works and uses a random letter generator to demonstrate some results.

3

If there truly was an infinite amount of time and monkey, yes, it could happen. However, we know that time and monkeys are both limited. Let's say that the universe will be gone when there are no more neutrons. According to this article, that will be about 10^40 years. There are approximately 4*10^78 atoms. And let's just say that an atom monkey can type at 10^15 keys per second. Let's also assume that there are 40 keys on a typewritter (26 A-Z, numbers, period, comma, semicolon, and space). That'll give the following:

There will be 4e78*365*24*3600*1e15 key strokes per atom, giving a total of 1.26e101. There would then be 5.05e177 key strokes. 40^108=1.0531e+173. That means that there would be segments of around 108 characters of Hamlet around, but certainly not the whole work.

  • 3
    +1 The answer is **no** because the question is impossible. Given that the mass and age of the universe are both finite, it is impossible to have an infinite number of monkeys typing for an infinite amount of time.2011-01-12
  • 10
    @Qwerky: I think you are interpreting the question too literally. That is one interpretation, but there are other interpretations less tied to physical reality.2011-01-12