I’ve wanted to start this discussion for several weeks, but wasn’t sure how to present Wagner’s argument. Fortunately Piotr has saved me the trouble with a post at UD.

Piotr February 24, 2015 at 1:35 pm
Gpuccio,

Do you mind if I begin with a simple illustrative example? Let’s consider all five-letter alphabetic strings (AAAAA, QWERT, HGROF, etc.). By convention, a string will be “functional” if it’s a meaningful English word (BREAD, WATER, GLASS, etc.). Functionality is therefore not a formal property of the string but something dictated by the environment. There are 26^5 = 11881376 (almost 12 million) possible five-letter strings. The number of five-letter words in English (excluding proper nouns and extremely rare, dialectal or archaic words) is about 6000, so the probability that any randomly generated string is functional is about 0.0005.

Any five-letter string S can produce 5×25 = 125 “mutants” differing from S by exactly one letter. If you represent the sequence space as a five-dimensional hypercube (26x26x26x26x26), a mutation can be defined as a translation along any of the five axes.

It would appear that the odds of finding a functional mutant for a given string should be about 125×0.0005 = 1/16 on the average. In fact, however, it depends where you start. If S is functional, the existence of at least one functional mutant is almost guaranteed (close to 90%). For most English words there are more than one functional mutants. For example, from SNARE wer get {SCARE, SHARE, SPARE, STARE, SNORE, SNAKE, SNARK…}. Though some functional sequences are isolated or form small clusters in the sequence space, most of them are members of one huge, quite densely interconnected network. You can get from one to another in just a few steps (often in more than one way), which is of course what Lewis Carroll’s “word ladder” puzzle is about:

FLOUR > FLOOR > FLOOD > BLOOD > BROOD > BROAD > BREAD

You can ponder the example for a moment; I’ll return to it later.

The Elephant in the Room

The whole thread is worth a look.

I might add that there is a rather crude GA at http://itatsi.com that does something not entirely unlike a word ladder.