infinite loop = I = infinity

Infinite-Monkey Theorem n.

"If you put an infinite number of monkeys at typewriters, eventually one will bash out the script for Hamlet." (One may also hypothesize a small number of monkeys and a very long period of time.) This theorem asserts nothing about the intelligence of the one random monkey that eventually comes up with the script (and note that the mob will also type out all the possible incorrect versions of Hamlet). It may be referred to semi-seriously when justifying a brute force method; the implication is that, with enough resources thrown at it, any technical challenge becomes a one-banana problem. This argument gets more respect since Linux justified the bazaar mode of development.

This theorem was first popularized by the astronomer Sir Arthur Eddington. It became part of the idiom of techies via the classic SF short story "Inflexible Logic" by Russell Maloney, and many younger hackers know it through a reference in Douglas Adams's "Hitchhiker's Guide to the Galaxy". On 1 April 2000 the usage acquired its own Internet standard, RFC2795 (Infinite Monkey Protocol Suite).

--The Jargon File version 4.3.1, ed. ESR, autonoded by rescdsk.

If you give an infinite number of monkeys typewriters, an infinite subset of them will figure out how to beat the monkeys around it to death with its typewriter. It is not known whether this would happen enough to thwart the goal of the complete works of Shakespeare. But keep in mind the other things that a subset of the infinite monkeys will do:

See also Jorge Luis Borges's short story The Library of Babel. It is about a library which not only comprises the entire Universe, but which also contains every possible book, including all the books of pure nonsense, etc.

Something that's been in my fortune list for a few years:

I'm not really this much of an OS bigot. This list was compiled based on of the common stereotypes. Yet I suspect that a lot of people are voting this up because they like having their prejudices reaffirmed.

Here is what - despite the writeups below - I consider the definitive article on the subject. I hope the original author, whom I haven't attempted to contact, doesn't object to this redistribution in a different medium.


From: dsfergem@fas.harvard.edu (David Fergemann)
Newsgroups: harvard.general
Subject: Re: Power Putty: Info Wanted
Date: Jan, 1996

jhliu@scunix4.harvard.edu (Jonathan Liu) wrote:

> Cindy Alvarez wrote:
> :       "If an infinite number of monkeys typed at an infinite number
> :       of computers for an infinite length of time, they'd produce
> :       a paper which would get a B+ at Harvard."  -me
>
> I'm looking for an infinite number of monkeys and an infinite number of
> computers to type a paper for me.  Anyone know where I can find one?
                                                                  ^^^^
One isn't going to do you any good.  The "infinite number" part was
important.  I've never believed the "infinite number of monkeys" idea
anyway.  If you said instead, "an infinite number of truly-random
character generators running on an infinite number of computers for an
infinite length of time," I'd believe it.
(Your typical pseudorandom function won't work; it repeats after a few
billion numbers or so).  The monkeys won't work for a number of reasons.

1) Monkeys will get bored, and won't type one character at a time.
Instead, you'll get stuff like:

X-IO432, .CXZX
 CZV ;ASskjzx c
[\W.,/KJ23\
X C. /ZX-=1
'C/XC0-WQ  \WE
?VC VB45A432we
?D;[2e   \[]c?x ;mpioqw\4352?GH';l[bvx-=trw123?!
';\]zx[  awre 3241;1-=sd?>Fg;lk230-=AS
';ZX C.,/WEQ[]
SDKLJ;FJ;KL32490CD,. AS/
"}aSDKLRE.'
;C KJQW
\rds;l'4iopczx/.,zx;"
|sfd]wA,CVZX[]XVC[PSO0-XCZ,.VSD09-=123\
SA
?:vzc;odssa\q  [\]vc,.mldf;':i690-hgfdc
\';asdl]aS
Z

(I typed that with my knuckles).

2) As you can see in the above example, knuckle-typing leads to serious
problems, including:
   a) high frequency of the semi-colon and other punctuation
   b) Rather than single capital letters followed by strings of lower case
letters, you wind up with strings of capital letters, due to the caps-lock
key.
   c) Extremely redundant.  In particular, notice the digraph frequencies
(count the number of times you see "zx", "jk", "23" and "kl".  Notice also
how frequently a line begins with ' " ? or / due to their proximity to the
return key.)
   d) A typical paper includes only one carriage return per paragraph.  It
looks like I'm averaging about one per 15 letters in the above.

3) Various other problems:
   a) Monkeys don't know how to adjust fonts and margins to make the paper
fit into the right number of pages.
   b) Monkeys might have a tendency to throw feces at the computer.
   c) The sun is scheduled to burn out within a few billion years, which
will put an end to the monkey typists.
   d) Your paper is probably due before then anyway.

--
Dave Fergemann
   

"Ford!" he said, "there's an infinite number of monkeys outside who want to talk to us about this script for Hamlet they've worked out."
Douglas Adams, The Hitchhiker's Guide to the Galaxy (1979).

This quote is perhaps the most famous reference to the Infinite Monkeys Theorem. This theorem states that if you put an infinite number of monkeys behind typewriters, eventually one will write the script for Hamlet. Alternatively a finite number of monkeys with infinite time will also accomplish this. The implication is that a problem or task of any complexity can be solved using brute force trial-and-error, even without intrinsic knowledge of a system, nor the intelligence to adapt to a situation.

The infinite monkeys theorem applies to (generally large) systems where the dataset is either sampled entirely in a systematic manner, or completely at random.

An example of sampling the entire dataset is finding a computer password or cryptographic key by brute force; one would simply try all possible character combinations (e.g.: aaaa,aaab, aaac...) until the proper solution is found. This would take a very long time, especially if there is no additional information about the length of the password, or the characters that are allowed. Nevertheless, this technique can be quite effective for smaller datasets. For instance, if the Coca Cola company wants to introduce a new beverage, they may survey people about a few of the properties of the drink, such as color, flavor, and carbonation. If each property has two options, they could do a market survey on the entire dataset, and serve the survey group a total of 8 drinks:

  1. Lemon / Yellow / Carbonated
  2. Lemon / Yellow / Non-Carbonated
  3. Lemon / Red / Carbonated
  4. Lemon / Red / Non-Carbonated
  5. Raspberry / Yellow / Carbonated
  6. Raspberry / Yellow / Non-Carbonated
  7. Raspberry / Red / Carbonated
  8. Raspberry / Red / Non-Carbonated

Using common sense, a researcher would only consider yellow lemon or red raspberry drinks, but the general idea is clear. For larger numbers of combinations in the dataset, this method becomes impractical very quickly. If we want to survey another property, the number of drinks doubles (24 = 16). If there are three choices for each category, the number of possibilities increases to 33=27.

An example of random sampling of a large dataset is (to a certain degree) evolution. The combination of different genetic material, and mutations allow for a seemingly infinite number of genotypes, each of which are more or less adjusted to a dynamic environment (not taking into account the factors that make up natural selection). Another example in this category is the mathematics of irrational numbers such as e, and pi. It is often assumed that pi is a normal number, i.e. any arbitrary, finite string of digits is represented somewhere in the digits of pi. The string of digits could be your phone number, social security number, or even Hamlet in ASCII values. However, there is no formal proof of this yet.

One final example in the time domain is the prophecies of Nostradamus. Given a final number of arbitrary, vague prophecies, and an infinite amount of time, each and every prophecy will prove to be true.

The history of the infinite monkeys theorem is not entirely known. Most certainly, Douglas Adams is not the source of the theorem, as it was reported much earlier than that. It may be as old as the typewriter itself. Or perhaps one of the infinite monkeys scribbled it into the soil with a stick a few thousand years ago. However, the first historical notion of the infinite monkeys theorem is in French, by Emile Borel1 (1913):

... Concevons qu'on ait dressé un million de singes à frapper au hasard sur les touches d'une machine à écrire et que, sous la surveillance de contremaîtres illettrés, ces singes dactylographes travaillent avec ardeur dix heures par jour avec un million de machines à écrire de types variés. Les contremaîtres illettrés rassembleraient les feuilles noircies et les relieraient en volumes. Et au bout d'un an, ces volumes se trouveraient renfermer la copie exacte des livres de toute nature et de toutes langues conservés dans les plus riches bibliothèques du monde. Telle est la probabilité pour qu'il se produise pendant un instant très court, dans un espace de quelque étendue, un écart notable de ce que la mécanique statistique considère comme la phénomène le plus probable...
Let's consider that we trained one million monkeys to randomly strike the keys of a typewriter, and that under surveillance of illiterate foremen the monkey typists ardently work for ten hours per day on one million typewriters. The illiterate foremen would collect the blackened sheets and compile them into volumes. And after one year, those volumes would contain the exact copy of books on any subject, in any language, in the largest libraries around the world. This is the probability that occurs during one very short moment, at some place, a remarkable event that statistical mechanics considers to be the event with the highest probability

The first mention of the infinite monkeys theorem in English is attributed to Sir Arthur Eddington2 (1929):

...If I let my fingers wander idly over the keys of a typewriter it might happen that my screed made an intelligible sentence. If an army of monkeys were strumming on typewriters they might write all the books in the British Museum. The chance of their doing so is decidedly more favourable than the chance of the molecules returning to one half of the vessel.

There are numerous other mentions of the infinite monkeys theorem; too many to sum up. Although one of them I found particularly interesting: L. H. C. Tippett was a statistician who was the first to produce a large table with random numbers for statistical purposes (in fact, the table consisted of 41 600) numbers. On one occasion, Tippet was introduced by Edward Condon, the director of the Bureau of Standards. Condon illustrated the idea that random events by chance may lead to a meaningful sequence, such as the possibility that a monkey may write a Shakespeare play. Referring to the book of random numbers, he then remarks that in fact Tippett had written a book that could have been produced by a monkey.

Another interesting writing on the infinite monkeys theorem is by the poet Lucio3, regarding an address at the British Association for the Advancement of Science (a.k.a. the British Ass.). The second two stanzas are:

Give me half a dozen monkeys
Set them to the lettered keys
And instruct these simian flunkies
Just to hit them as they please
Lo! The anthropoid plebians
Toiling at their careless plan
Would in course of countless aeons
Duplicate the lore of man

Thank you, thank you, men of science
Thank you, thank you British Ass!
I for long have placed reliance
On the tidbits that you pass
And this season's nicest chunk is
Just to sit and think of those
Six imperishable monkeys
Typing in eternal rows

And since we're on the topic of poetry, allow me to close by quoting a Dilbert comic strip4, where Dilbert writes a poem and presents it to Dogbert.

DOGBERT: I once read that given infinite time, a thousand monkeys with typewriters would eventually write the complete works of Shakespeare.
DILBERT: But what about my poem?
DOGBERT: Three monkeys, ten minutes.

Factual Sources:

1: Émile Borel, ``Mécanique Statistique et Irréversibilité,'' J. Phys. 5e série, vol. 3, 1913, pp.189-196.

2: A. S. Eddington, The Nature of the Physical World: The Gifford Lectures, 1927. New York: Macmillan, 1929, page 72.

3: Warren Weaver, Lady Luck, Anchor Books, Garden City, NY, 1963, 239-240

4: Scott Adams, Dilbert comic strip, 15 May 1989.

http://www.research.att.com/~reeds/monkeys.html (many more examples of the infinite monkeys theorem)

William S. Peters, Counting for Something - Statistical Principles and Personalities, Springer Verlag, 1986

Someone raised a question about the monkeys and copyrighted works. Allow me respond to that briefly. If an infinite number of monkeys create an infinite amount of work, and some of that work just happens to be an MP3 of Metallica's latest hit, the work is free from American copyright restictions. This falls under one of the four main "limitations" of copyright:

Idea
Ideas expreesed by creative works are not themselves protected. Copyright covers the work, the expression of ideas, but not the ideas themselves. That is what patents are for.

Facts
Plain facts, like, say, a phone book, are not protected. However, cataloguing or organizing facts in a certain way can sometimes result in the database or collection of facts being copyrighted.

Independent Creation
If an exact duplicate of a work is created independently and with no knowledge of the original, it is not a copyright infringement. Providing you can prove it.

Fair Use
The one most well known. The Fair Use doctrine says that creative works can sometimes be used, in whole or in part, in specific circumstances, without violating copyright. Fair use is constantly being redefined.

As you can see, the third limitation is what makes this okay. Additionally, if the monkeys are in a nation that does not have an agreement with America, where Metallica received its copyright, then this statuatory analysis is not even required.

The biggest problem you'd have with this project is keeping your monkeys fed.

We can safely ignore the efficiency of an actual monkey versus a computer simulation of one, as this is simply a constant factor (The ratio of energy used between computer monkeys and real monkeys is not affected by the number of monkeys).

What we need to worry about are these three facts:
  • It takes energy1 to perform computation (The monkeys have to press keys)
  • The energy supply is limited (There is only so much mass to destroy in the solar system)
  • Each extra bit we're going to monkey doubles the work load. (Even if we copy our old results, and put a 1 on the end of one, and a 0 on the end of the other, the energy needed to copy them doubles each time. And so does the energy spent looking at the results to see if we've got anything useful)

What this means for us, is that given all the available energy in the solar system, there is a limit to the length of string we can monkey. And it turns out it's quite short. Somewhere around 192 bits, in fact2. There are many ways to represent english text as a binary number. The naïve way is to simply map the 26 possible characters to a sequence of bits. This takes 5-6 bits per character. Better ways include using a huffman tree of the character distributions in english, using a huffman tree for each preceding character, etc. etc. It is an open (and possibly as hard as the infinite monkeys problem) question whether there is a lower bound for this number.3

Giving the benefit of the doubt, we'll assume it takes only 1 bit to represent a character. So (assuming you are generating english more intelligently than picking characters at random, which would give you about 40 characters) you're getting something in the region of 192 characters. There aren't a lot of things that fit in 192 characters:

Alas, poor Yorick! I knew him, Horatio:
a fellow of infinite jest, of most excellent fancy: he hath borne me on his back a thousand times; and now, how abhorred in my imagination it is! my gorge rims at it. Here hung those lips that I have

You'd better hope that one of these things is an incredibly consise guide to building a computer (in the words of Bruce Schneier) from something other than matter and occupy[ing] something other than space.


1 - technically, we're talking about entropy - the amount of energy left that can be leveraged to do something useful. But entropy is also an information theory term, and using entropy to mean both in the same node is just confusing.
2 - APPLIED CRYPTOGRAPHY, 2nd edition (John Wiley & Sons, 1996) goes into more detail on the subject. It suggests that you could get all the way to 219 bits by building a dyson sphere around a supernova. (222 if you could find a way to catch all the neutrinos)
3 - These don't give us work for free, though. While they give english-like text a shorter representation, they make representations of non-english text much longer.
The Infinite Monkey from a Duration of the Universe Perspective (as well as a recent experiment)

Yes, We’ve all heard it and we’ll all hear it again. You know the story- get some monkeys together and give them all some typewriters or some computers and they’ll eventually type out every masterpiece man has ever written (and then some!). Of course, infinite time is given and some people insist upon an infinite amount of monkeys too. It is a nice idea but in reality, this is impossible and I am going to run off a list of the real reasons why this would never happen…

Many attribute the source of the Monkey Myth to Arthur Eddington. He claimed that six monkeys on six typewriters, set to type for the duration of time would eventually produce all the books in the British Museum. It has been stated in many different ways, all with the same intention- Proving that what seems impossible is possible; however, what is Impossible is such for a reason- Because it is.

Firstly, for the sake of this we must make a basic assumption: that reality as we know it will hold for an infinite period of time. (i.e. – the monkey population will never be infinite, a monkey will never be able to type an infinite amount of letters/words per second etc.) These are all distinct components of the world as we perceive it. If you want to debate these statements, try Philosophy.

  • The time span it would take a monkey to type any work is much greater than the duration of the universe. The Universe may never reach a definite end; it may extend onwards forever; however, there is one aspect of physics that scientists are (fairly) certain of. Protons will decay in about 10 to the 25th power years (10^25). There won’t be an monkeys or typewriters if there aren’t any protons to make up the objects. Proton Decay will only be a problem if these monkeys can somehow survive without light. All the stars in the universe will burn out long before they ever get to the stage of proton decay. The Stars will be dead by the time the universe reaches the age of 10^15. (Also known to many as the 15th cosmological decade). This is only a problem if these monkeys can survive the red giant phase of our sun in about five billion years. There are a lot of obstacles between the monkeys and their literary accomplishment; however the remaining 4.5-5 billion years of life on Earth should surely be plenty of time for something of worth to arise…?

    The probability of six monkeys producing a single work within any period of meaningful time is zero. Calculations have shown that it would take six monkeys approximately 500,000 cosmological decades (10^ 500,000) years to produce a single workThose are pretty long odds.

  • Another wrench (maybe a Monkey Wrench) in the cogs of this argument is the fact that Monkeys are not mindless. Monkeys respond to stimuli and can formulate, at the very least, basic ideas. This means that a group of monkeys would never be able to truly achieve a random distribution of letters. When a monkey strikes the keyboard there is not necessarily a 1/26 chance that the monkey will hit that letter.

    The University of Plymouth in England in the Spring of 2003 conducted an experiment on six monkeys where the monkeys were given a computer with which they could mindlessly type; however the results were not mindless- nor anywhere near random. The monkeys demonstrated a fondness for the letter S (which filled most of the pages) and a tendency towards pushing J, A, L, and M towards the end of the four week experiment. This is not a random distribution of letters by any means, nor is it anywhere near close. This experiment proves that a monkey is too intelligent a subject for the infinite time typing. The monkeys noted that when they pushed a key, something happened on the computer screen.

    Time and Intelligence stand as major obstacles to the monkey idea. It is just as likely that you would be able to walk through a wall (a near infinite number of Particles undergoing Quantum Tunneling at the same instant) than a group of monkeys composing a single work of literature.

  • There are other logical impossibilities with this:
    • We would need an infinite amount of paper
    • an infinite amount of ink (and at these prices!)
    • An Infinite amount of typewriter parts (or an adequate supply of nev-R-break typewriters).
    • An infinite amount of either monkeys or time.
    • And even if we did have all these supplies would probably form a ball of mass so great that it would probably degenerate into a black hole and eventually end up crushing all of the monkeys, typewriters and office supplies into an infinitely small and ironic point.


Sources
http://education.jlab.org/qa/radelement_03.html
General Wesc who also mentioned the Black Hole Point before me; therefore, the credit belongs to him…
http://www.arn.org/docs2/news/monkeysandtypewriters051103.htm
http://www.cnn.com/TECH/9701/15/end.universe/
For more on the duration of the universe I recommend “The Five Ages of The Universe” by Fred Adams
More on Quantum Tunneling can be seen in “The Elegant Universe” by Brian Greene

It has been written, in various forms, that a monkey sitting at a typewriter tapping at random will, if given enough time, produce any piece of writing ever produced, Shakespeare’s Sonnet 18, for instance1. This supposition has been used in the past to demonstrate the difference between the concepts of “infinite” and merely “mind-bogglingly massive”. Here, I will attempt to calculate the probability of this happening.

First, we need the number of keys on a standard typewriter keyboard. Easy enough – discounting special keys such as shift and backspace, there are approximately 50 keys. There’s also no need to make things overly difficult – we are talking about a monkey, after all – so we’ll discount capitalisation, italics for stage directions and such.

Then we need the exact length of Sonnet 18. A quick meander around the Internet tells me it is 115 words long, including 619 characters. Surely not too daunting a task for a determined primate? And because we’ve promised him a banana when he’s done, he’s very determined indeed.

So, onto the calculations. If the monkey were only given one shot at this, one shot at glory, he would have to get the first character right on the first strike, the second character right on the second strike, and so on. Given 50 keys on a typewriter keyboard, the probability of getting each character right is simply (1/50). Given 619 characters in Sonnet 18, the probability of getting each one exactly right in the correct sequence is (1/50)619. This comes to 2,1755412185774780362325532940389 x 10-1052, a truly miniscule number.

Clearly, our monkey isn’t likely to manage this feat on the first go. To calculate the probability of anything else, we’re going to have to figure out exactly how many chances he’s likely to have. Typing continuously, he has a chance to start the winning sequence every time he strikes a key.

First, how fast does this monkey type? Let us assume that this monkey, while not particularly accurate, can type at a speed rivalling the fastest human – this is, to date, Barbara Blackburn, who can maintain 150 words per minute for nearly an hour. As this measurement assumes a word to be five letters and a space, this is 900 characters per minute, 15 characters per second which corresponds to a period of 0,06 (recurring) seconds per character, which for the sake of my sanity I’m going to round down to 0,06 seconds per character.

So every 0,06 seconds our primate friend is striking a key, and that key may or may not start the correct sequence. Now, how many keystrokes is he likely to get in? Given his remarkable longevity (members of Atelis longlifidae are prodigiously long-lived), we will give him, literally, until the end of the world to get it done.

There are many theories regarding how long we have to wait until the Earth meets its maker, ranging from about five years (the Incas believed that 2012, by our measurement, was a good time to start panicking) to approximately 5 billion years (when the Sun is estimated to become a Red Giant, boiling off the oceans and expelling the ol’ blue-and-green into the void). I’m an optimist, so five billion years seems a good place to start.

Five billion years is 1 826 250 000 000 days, which is 43 830 000 000 000 hours, or 157 788 000 000 000 000 seconds. This is time enough for 2 366 820 000 000 000 000 of our monkey’s keystrokes. Because it’s not good enough to merely begin the winning sequence – he also has to have time to finish it – we’ll subtract the number of keystrokes that will take, from the total, leaving us with 2 366 819 999 999 999 381 chances to initiate the sequence of characters that will leave us Sonnet 18.

So, given 2 366 819 999 999 999 381 chances to get it right, our monkey has a probability of 2 366 819 999 999 999 381 x 2,1755412185774780362325532940389 x 10-1052 or 5,1491144669535452190559174879383 x 10-1034 of getting it right before the world ends.

Still no cigar, and not even close. So obviously our monkey needs some help. For this, we have the patented Monkey Cloner 6000™, the latest in primate replication technology. It’s very easy to use – we just have to set the dial for how many monkeys we want, and it does the rest. So how many monkeys do we want?

To be certain of having this task done in time, we need to make the probability of it equal to 1. 5,1491144669535452190559174879383 x 10-1034 goes into 1 (1,9420815101662448575607332403532 x 101033) times, so in fact that is how many monkeys we’re going to need if we were going to get this done.

Of course, 1,9420815101662448575607332403532 x 101033 monkeys are going to take up a lot of room. And a lot of bananas. Assuming one banana each (no favouritism, here) it’s about 2,4276018877078060719509165504415 x 101029 metric tonnes of bananas, or 1,5462432405782204279942143633382 x 101022 times more than is produced on Earth every year (about 15,7 million tonnes). Then again, we have until the end of the world to produce this many bananas, meaning that we only have to up banana production by less than 3,0924864811564408559884287266764 x 101012 tonnes of bananas per year and sustain that for 5 billion tears to produce enough.

Hence, I believe we can put the issue to rest. Never again can a reasonable person argue that Shakespeare was in fact a monkey, due to the sheer improbability of Sonnet 18, not to mention the lack of 17th-Century typewriters. Nor, indeed, could they argue that Shakespeare was in truth 1,9420815101662448575607332403532 x 101033 monkeys, as although he (they) may have produced Sonnet 18 given enough time, the world banana economy would simply not have sustained him (them).


1In the first draft of this w/u, I used the complete text of Hamlet, but the numbers involved produced errors on scientific calculators, Microsoft Calculator and Google Calculator alike. I am not above admitting defeat, especially to numbers like (1/50)167173.

Log in or register to write something here or to contact authors.