If you haven't heard of Monkeys Typing Shakespeare: Infinity Theory, here is a brief overview.
The theory is that if you had an infinite number of monkeys typing at random (as monkeys would) on an infinite number of typewriters for an infinite number of years, it is probable that one would eventually type out the entire works of Shakespeare.
A good explination of this theory is here. After reading that, you will see that it would take a monkey years and years to type out a sonet. But, with an infinite number of monkeys, it should only take a few years.
Now, what does this have to do with Perl? Well, during my morning cup of coffee, I decided I wanted to be a monkey (since I don't own one), and made a quick hack which mimics a monkey typing randomly on a 27 key keyboard, 26 letters, and a space bar (I added 5 spaces, since the space bar is large, and helps speed things up).
I have it pointing to a log file, so I can later parse what was typed. If you too become a monkey, remember that this is a slow process, and an infinite number of us is the only thing that could raise the probability. After running this for a while, I see the monkey mainly gets small words correct. If you have changes for this (like adding in the use of the Ispell module, or anything to quicken it or make it more 'life-like' (remember, this was a quick hack to amuse myself), let me know!
#!/usr/bin/perl -w
use strict;
no strict 'subs';
# 27 letters and a space bar (5 spaces since the space bar is large :)
+.
my @keys = (A..Z, ' ', ' ', ' ', ' ', ' ');
# Open log to print good words
open(FH, ">>monkey.log") or die "No monkey ($!)";
select(FH); $|++;
# Start a block
{
my $str;
# Building a 572 char string, could be longer.
for (1..572) {
$str .= $keys[rand(@keys)];
}
my @words = split(" ",$str);
for (@words) {
# Not too many 15+ char words, so skip em
next if /\w{15,}/;
my @spell = `echo $_ | ispell -a -S`;
if (grep /^\*/, @spell) {
# Good monkey!
print $_ . " " unless !/[IA]/;
next;
}
}
# Keep redoing this block
redo;
}
See also: RFC2795, Infinite Monkey Protocol Suite
Cheers,
KM |
RE: Be a monkey!
by turnstep (Parson) on Aug 30, 2000 at 21:46 UTC
|
> After reading that, you will see that it would take a monkey
> years and years to type out a sonet. But, with an infinite number of monkeys,
> it should only take a few years.
Actually, an infinite number of monkeys will produce
the works of Shakespeare only as long as it takes to type
it. More like a few days, assuming a fairly regular
typing rate. :)
One other point, ispell might not have a lot of
Shakespeare's words. Perhaps a program to create a list
of only those words from a Shakespeare play? :)
Better yet, how about having it try to create a
perl script and periodically eval'ing the result?
*grin* "It's not obfuscated, it's written by my
monkey!"
| [reply] |
|
|
Better yet, how about having it try to create a perl script and periodically
eval'ing the result? *grin* "It's not obfuscated, it's written by my
monkey!
They actually use a technique a bit similar to the
monkeys system to breed programs.
It's called genetic programming.
It can be used to breed program that are good at a certain
task. Say for instance sorting a file or solving some
math problem, or writing shakespeare :)
Applied to perl it would go something like this:
You have a population of 1000 individuals.
Each individual is a program of say 100 lines of perl code. These lines are chosen randomly at the begin.
Each population goes through a number of generations.
During each generation the fitness of each individual
(perl program) is tested.
It is tested by running the program and evaluating how
well it perform the target task. In the case of sorting
it is tested of the file was sorted correctly and how
fast the program sorted. Or how well it writes literature
in case of the Shakespeare problem.
The 500 best programs are allowed to mate and produce
two childern. For this a pair of programs is chosen at
random. A random line number is chosen. Say n.
Child 1 is created out of the first n lines of parent 1
and the remaining 100-n lines of parent 2. Child two is
made out of the first n lines of parent 2 and the remaining
100-n lines of parent 1. Sometimes a line of code
is also mutated, (changed a bit), this introduces more
diversity.
Now all the parents die. What remains is a population
of 1000 childern, a new generation. Which are hopefully
better addapted to solving the given problem.
The process is repeated.
With each generation the individuals will become better
and better (on average) at solving the given problem.
It works much like evolution works,
survival of the fittest, with a bit of mutation.
The only thing you have to do solve a problem is
specifiy is a function that defines how good a program
is at solving the given
problem.
Which is easy in most cases, though in case of
the Shakespeare problem finding
such a function is probably more difficult, cause
how do you define good literature :)
Have Fun
GalaxyNG
| [reply] |
|
|
More like a few days, assuming a fairly regular typing rate. :)
You should take a look at all the mathematical theories on this. The question is when would one monkey type it, not the collection of monkeys. Another fun read on this (which does give a number of monkeys if you wanted a 50% chance of them typing it within 24 hours) is here (not for mathaphobics!). If it could be done in a few days, I say we start cloning some simians!
One other point, ispell might not have a lot of Shakespeare's words. Perhaps a program to create a list of only those words from a Shakespeare play? :)
Yes, I thought of that. There must be a dictionary around which he used. But, lines like 'To be or not to be' could be from ispell. I simply wonder how much computing time would be needed for one of the monkeys to type any cohesive sentence :)
create a perl script and periodically eval'ing the result?
I simply use grep on my log file.
Cheers,
KM
| [reply] |
|
|
"The theory is that if you had an infinite number of monkeys typing at random"
See, there is an infinite number of monkeys, and he is right, in that it would only take as long as it takes a monkey to type enough characters to be shakespere.
However, on another subject, can the shakespeare be in the middle of gibberish. Or does the monkey have to stop typing eventually? or can it be:
fjkjdfjdsk
<the entire hamlet script>
fjkjdsljdsk
(of course that question would only matter if there were a finite number of monkeys>
However, back to my question as to when do the monkeys STOP typing?
Does each monkey just keep going?
| [reply] |
|
|
|
|
|
|
> > create a perl script and periodically eval'ing the result?
> I simply use grep on my log file.
I meant how long for a monkey script to create a
valid perl file...
| [reply] |
|
|
|
|
|
|
|
|
| [reply] |
|
|
| [reply] |
RE: Be a monkey!
by jlistf (Monk) on Aug 30, 2000 at 21:34 UTC
|
If you have changes for this (like adding in the use of the Ispell module, or anything to quicken it or make it more 'life-like' (remember, this was a quick hack to amuse myself), let me know!
as one of those unfortunate to be working on windows i started wondering... what happens if the monkey is working with microsoft word? it has some built-in spell checking (changing teh to the for instance). i wonder how much this would help/hurt.
jeff
| [reply] |
|
|
| [reply] |
|
|
I think PETA should be informed anyway. Microsoft's strategy of hiring a nearly infinite amount of monkeys, supplying them with keyboards and bananas and waiting until they come up with a complete operating system is atrocious and should be stopped immediately.
| [reply] |
RE: Be a monkey!
by lindex (Friar) on Aug 30, 2000 at 22:35 UTC
|
Ok I havent slept in a lil over 20 hours so this could be completly wacked out code
but here it is :)
#!/usr/bin/perl
use strict;
no strict qw(refs);
use Fcntl qw(:flock);
use Lingua::Ispell qw( spellcheck );
die "$0: <logfile>\n" unless(@ARGV==1);
open(LOG,">>$ARGV[0]") || die "$!: $ARGV[0]";
flock(LOG,LOCK_EX) || die "Can not get lock on: $ARGV[0]";
my(@keys) = ('a'..'z',' ',' ',' ',' ',' ');
my($word,$chr,$count);
while($chr=$keys[rand @keys]) {
if ($chr eq ' ' || length(($word)? $word : 1) ==15) {
print $word,"\n" if((spellcheck($word))->{'type'} eq 'ok');
$word = "";
}
$word .= $chr if($chr ne ' ');
}
close(LOG);
exit();
lindex
/****************************/
jason@gost.net, wh@ckz.org
http://jason.gost.net
/*****************************/
| [reply]
[d/l]
[select] |
RE (tilly) 1: Be a monkey!
by tilly (Archbishop) on Aug 30, 2000 at 23:05 UTC
|
Actually with an infinite number of monkeys it should take
only as long as it takes one monkey to type that volume of
gibberish. That is because in that timeframe, out of all
of the monkeys, an infinite number will have accidentally
come out with the perfect Shakespeare.
Of course figuring out which monkey(s) did it may take a while. :-)
EDIT
An incidental note. An infinite number of chessplayers
playing each other at once are rather less likely to come
up with the perfect chess game than an infinite number
of monkeys trying to play chess. Why? Because humans
will attempt to apply their theories and consistently
make certain types of mistakes.
So you see, a little knowledge is a dangerous thing. :-) | [reply] |
|
|
| [reply] |
|
|
We may need a mathematician or perhaps a physicist to
devise a proper module for this purpose. The Infinite
Monkey Protocol Suite obviously considers the use of
subatomic monkeys and monkeys in multiple universes,
hence the need for the I-TAG encoding needed to enumerate
them all.
This problem seems to closely resemble the programming
necessary for quantum computers. Obviously if you need
as many qubits (quantum bits) as there are letters in the
longest document you seek to reproduce, you are in trouble
since science has yet to produce more than a handful of
qubits.
But if you had the use of the 5 qubit computer IBM built
last month, which is basically using five atom-sized
monkeys in multiple universes, you could work on the problem
five bits at a time (should be just enough to pick a character
from the set of capital alphabet letters, the space key,
and a few diacritical marks).
In the
words of the inventor of this quantum computer, words
which little does he realize will soon be immortalized (!)
through Perl and our application of the Infinite Monkey
Protocol Suite,
`A quantum computer could eventually be used for practical
purposes such as database searches -- for example searching the
Web could be sped up a great deal -- but probably not for more
mundane tasks such as word processing,'' said Isaac Chuang, the
IBM researcher who led the team of scientists from IBM, Stanford
University and the University of Calgary.
This open source effort could possibly be funded by a modest
tax of 1/1000 of a penny per monkey provided, including
all universes traversed by the protocol of course.
| [reply] |
|
|
(Two
other papers that might be of interest are "The Mathematics of Monkeys and
Shakespeare" and "More Monkey Business".)
Note that the argument against evolution presented
in this last document is wrong. The chance that a work
shakespeare is generated randomly is indeed almost zero.
However it is rather easy to evolve a work of shakespeare,
provided there is a way to select the works that look more
like shakespear from works that look less then shakespeare.
Have Fun
| [reply] |
|
|
|
|
|
|
RE: Be a monkey!
by eclecticIO (Beadle) on Aug 31, 2000 at 19:41 UTC
|
I wonder if anyone would be interested in writing a perl script that could be distributed
with a screen saver. Or maybe the script could run as a daemon that watches for the screen
saver. As long as it finds the screen saver process it can do it's thing in the background
and then send (via e-mail, http, etc.) the results to a person or group of people willing
to donate cpu time to puting it all together looking for Shakespearian works,functional perl
scripts, etc. All of this a la SETI@home.
I may look into it, but given my present skills it may be faster to round up the
actual monkeys. :)
eclecticIO
"Given the pace of technology, I propose we leave math to the machines and go play outside."
Calvin - Homicidal Psycho Jungle Cat | [reply] |
|
|
| [reply] |
|
|
| [reply] |
(jeffa) Re: Be a monkey!
by jeffa (Bishop) on May 10, 2003 at 16:10 UTC
|
| [reply] |
|
|
| [reply] |
|
|
