Monkey and a poet's work ?
in [General Programming]
|
From: Karthik Balaguru on 7 Mar 2010 13:39 On Mar 7, 11:02 pm, j...(a)toerring.de (Jens Thoms Toerring) wrote: > In comp.unix.programmer Karthik Balaguru <karthikbalagur...(a)gmail.com> wrote: > > > I came across the 'Infinite Monkey Theorem'. > >http://en.wikipedia.org/wiki/Infinite_monkey_theorem > > I wonder how can a monkey hitting keys at random on > > a typewriter keyboard for an infinite amount of time will > > almost surely type a given text, such as the complete > > works of William Shakespeare ? > > What could be not in an infinite set? You will have not > only the works of Shakespeare, but also all his works > with all kinds of typos, readers digest versions etc.;-) > Readers digest version too :-) :-) :-) Yeah, an infinite set can have all kind of works ! > > And why was monkey chosen to convey this theorem ? > > Because at the time someone came up with this idea there > weren't any keyboards that cats use for sleeping on. :-) :-) Maybe, cat might eat the mouse ;-) > That > later led to the theorem that given enough cats, keyboards > and time all possible Perl scripts will be created. > > > How far is this theorem true ? Has any monkey > > proved this now :-) ?? > > Well, instead of using a single monkey, giving it infinite > time, you can use a large number of monkeys for a shorter > time. :-) :-) > Now, since the works of Shakespeare actually have been > written (assming that Shakespeare was a kind of monkey and > you don't instsit on the typewriter part), the theorem thus > has been experimentally proven (as a possibly uninteded side > effect of the mice having earth produced for finding "the" > question). > > For another take on this have a look at the story "The Library > of Babel" by Jorge Luis Borges (who was, BTW, the model for > the blind librarian in Eco's "The Name of the Rose"). > :-) Karthik Balaguru
From: Ben Bacarisse on 7 Mar 2010 14:40 jt(a)toerring.de (Jens Thoms Toerring) writes: > In comp.unix.programmer Karthik Balaguru <karthikbalaguru79(a)gmail.com> wrote: >> I came across the 'Infinite Monkey Theorem'. >> http://en.wikipedia.org/wiki/Infinite_monkey_theorem > >> I wonder how can a monkey hitting keys at random on >> a typewriter keyboard for an infinite amount of time will >> almost surely type a given text, such as the complete >> works of William Shakespeare ? > > What could be not in an infinite set? You will have not > only the works of Shakespeare, but also all his works > with all kinds of typos, readers digest versions etc.;-) You probably should clarify this: "what could not be in an infinite set constructed like this?"[1]. The mere fact that the set is infinite is not enough to ensure that even one word of Shakespeare is almost surely present. [1] or "what could not be in such a set?". <snip> -- Ben.
From: Stefan Monnier on 7 Mar 2010 15:14 >> For another take on this have a look at the story "The Library >> of Babel" by Jorge Luis Borges (who was, BTW, the model for >> the blind librarian in Eco's "The Name of the Rose"). You might like the "Pierre Menard, Author of the Quixote" as well, for a different take on it. Stefan
From: Nick Keighley on 8 Mar 2010 04:56 On 7 Mar, 18:02, j...(a)toerring.de (Jens Thoms Toerring) wrote: > In comp.unix.programmer Karthik Balaguru <karthikbalagur...(a)gmail.com> wrote: > > I came across the 'Infinite Monkey Theorem'. > >http://en.wikipedia.org/wiki/Infinite_monkey_theorem > > I wonder how can a monkey hitting keys at random on > > a typewriter keyboard for an infinite amount of time will > > almost surely type a given text, such as the complete > > works of William Shakespeare ? > > What could be not in an infinite set? lots of things. An infinite set doesn't have to contain all values with equal probability. It is far from clear that pi expressed as a decimal fraction and then mapped to ascii in some reasonable manner / has/ to contain the complete works of shakespere. Nasty stuff infinity. <snip> > > How far is this theorem true ? Has any monkey > > proved this now :-) ?? > > Well, instead of using a single monkey, giving it infinite > time, you can use a large number of monkeys for a shorter > time. so if I used 10 monkeys how much time would I save? > Now, since the works of Shakespeare actually have been > written (assming that Shakespeare was a kind of monkey and > you don't instsit on the typewriter part), the theorem thus > has been experimentally proven (as a possibly uninteded side > effect of the mice having earth produced for finding "the" > question). shakespere didn't generate his plays by random means. > For another take on this have a look at the story "The Library > of Babel" by Jorge Luis Borges (who was, BTW, the model for > the blind librarian in Eco's "The Name of the Rose"). -- Nick Keighley "Anyone attempting to generate random numbers by deterministic means is, of course, living in a state of sin." -- John Von Neumann
From: Richard Heathfield on 8 Mar 2010 05:59
Jens Thoms Toerring wrote: > In comp.unix.programmer Karthik Balaguru <karthikbalaguru79(a)gmail.com> wrote: >> I came across the 'Infinite Monkey Theorem'. >> http://en.wikipedia.org/wiki/Infinite_monkey_theorem > >> I wonder how can a monkey hitting keys at random on >> a typewriter keyboard for an infinite amount of time will >> almost surely type a given text, such as the complete >> works of William Shakespeare ? > > What could be not in an infinite set? The infinite set of even integers contains only half the integers. None of the odd integers (of which there are infinitely many) is present in the set. The infinite set of prime integers contains almost none of the integers - just an infinite handful that share an odd characteristic. Most of the integers are absent from that infinite set. The infinite set of integer powers of two contains practically no integers at all - merely infinitely many. If the infinite set of integers were an infinitely large barrel, the infinite set of integer powers of two would be an infinitesimally small apple rolling around at the bottom. (Admittedly it would be an infinitely large infinitesimally small apple...) The set of things that could not be in a given infinite set is infinitely large. In fact, there are many such sets. Now, consider the set of *all* such sets... Er, actually no, let's not go there... > You will have not > only the works of Shakespeare, but also all his works > with all kinds of typos, readers digest versions etc.;-) That isn't certain by any means. See above. <snip> > Well, instead of using a single monkey, giving it infinite > time, you can use a large number of monkeys for a shorter > time. Now, since the works of Shakespeare actually have been > written (assming that Shakespeare was a kind of monkey and > you don't instsit on the typewriter part), the theorem thus > has been experimentally proven (as a possibly uninteded side > effect of the mice having earth produced for finding "the" > question). I think we can agree that the works of Shakespeare have actually been written. But you are assuming: (a) that Shakespeare wrote them, which is apparently a matter of some dispute; (b) that Shakespeare was a kind of monkey, which is very unlikely to be true. Both are primates, but then cars and bicycles are both vehicles; that doesn't mean a bike is a kind of car or vice versa. And in any case the theory is about duplicating the works of Shakespeare, not originating them. Let's try to quantify it a little, shall we? We start by defining our terms and our tools. We will begin with a simple monkey, eventually replacing him with a computer. Let's assume that we have *one* monkey, then, hitting *one* typewriter *once* per second, purely at random. The typewriter has *two* keys, 0 and 1. (When we install the MonkeyBrain XII later on, we can soup up the speed a bit.) Here is a Shakespeare sonnetette: 10010111. We want to know whether, if we'd installed our monkey attadawnatime, he would have a reasonable probability of having produced this sonnetette by now. Of course, we'd like to be more general than that. Attadawnatime, they say, was 14,000,000,000 years ago. That's about 441504000000000000 seconds, which we'll double (in case the scientists got it wrong, which is not exactly unheard of), giving us a million million million seconds to work with. Bags of time. Now, the first seven times our monkey hits the keys, he can't possibly produce the sonnetette. But the eighth time, he *may* have produced a sonnetette. That is, if the bit length of the target text T is L, then we have to produce at least L bits. The probability of the first L bits producing T is 1/(2^L). More specifically, for L=8 it's 1/256 = 0.00390625 = p (probability of matching L bits of data against all L bits of text, in a given position in the bitstream). Now if we produce *more* bits, it gets a bit(sigh) more interesting. Let's assume we produce 9 bits. We now have two stabs at the T cherry: a match of T against the first 8 bits of the 9, and a match against the last 8 bits of the 9. Any one match will do, so both matches have to fail for the monkey to fail. We calculate this failure probability F by raising (1-p) to the power of the number of match attempts: F = (1-p)^2 = 0.99609375^2 = 0.9922027587890625 More generally, if we produce B bits (where B>=L): F = (1 - (1/(2^L))^(B+1-L) and this will take us B/R seconds, where R is our bit production rate (bits per second). Clearly, the probability P of success is 1-F. At this point, we have a program spec. Inputs: L (the length of the test corpus, in bits) R (bit production rate) K (seconds sinceadawnatime - assume 10^18) Calculation: Attempts = ((R * K) + 1) - L SingleFailure = 1.0 - (1.0 / pow(2.0, L)) F = pow(SingleFailure, Attempts) P = 1.0 - F The implementation is left as an exercise for the terminally bored reader. -- Richard Heathfield <http://www.cpax.org.uk> Email: -http://www. +rjh@ "Usenet is a strange place" - dmr 29 July 1999 Sig line vacant - apply within |