## Wednesday, August 26, 2009

### On Oracles and Weasels

It's once again about Richard Dawkins's weasel algorithm. In his book The Blind Watchmaker, Dawkins gives the following description.
Dawkins describes his algorithm in the following way:

It again begins by choosing a random sequence of 28 letters, just as before:

WDLTMNLT DTJBKWIRZREZLMQCO P

It now 'breeds from' this random phrase. It duplicates it repeatedly, but with a certain chance of random error - 'mutation' - in the copying. The computer examines the mutant nonsense phrases, the 'progeny' of the original phrase, and chooses the one which, however slightly, most resembles the target phrase, METHINKS IT IS LIKE A WEASEL. [...] the procedure is repeated.

In my previous posts, I explained how this can be transformed into a program:

1. chose random string
2. copy string n times with mutation. NOTE: at this step you don't know which letters are correct in place, so no letter is safe from being mutated!
3. chose best fitting string. NOTE: best fitting seems to be generally understood to be the string with the most correct letters, the fitting is expressed by a number between 0 and 28
4. Stop, if the number of correct letters is 28, otherwise
5. goto 2
Some people (including W. Dembski, I think) are baffled by step 3: seemingly, the program has to know the best string and can extract information about it. Therefore, I restate this algorithm slightly:

1. chose random string
2. copy string n times with mutation.
3. ask oracle which string it likes best
4. Stop, if the number of correct letters is 28, otherwise
5. goto 2

Evaluating a fitness function for an algorithm is like questioning an oracle. Even Robert Marks's and Richard Dembski's web site says so - though they don't think it through.

So, how does the oracle work in Dawkins's case? You present it with a list of strings and it just tells you which string is best ("The computer examines the mutant nonsense phrases, the 'progeny' of the original phrase, and chooses the one which, however slightly, most resembles the target phrase, METHINKS IT IS LIKE A WEASEL."). You don't have to know how the oracle deems one string better than the other: it could be that it prefers the string with the most letters correctly in place, or the one which shares the longest substring with its (hidden) target, or perhaps it looks how many letters are right from the begin of the phrase, preferring METHINKS IT IS FROGLIKE XXX to BETHINKS IT IS LIKE A WEASEL, or preferring correct vowels to correct consonants, it could be a combination of these on Fridays, and Saturdays something else....

Could Dembski's algorithm with such an oracle? No. Here is a his algorithm:
1. chose random string
2. ask oracle which letters are in place
3. if all letters are in place: STOP Otherwise:
4. mutate letters which are not in place
5. goto 1

What Dembski exploits is the knowledge about the inner processes of the oracle: but knowing how it works allows for a deterministic approach - the Hangman game - which terminates in a few steps...