Watching an evolving text is sure hypnotic, but it also brings thoughts about the whole thing, evolution, programming, evolutionary algorithm, even God and religion. Let's think it through together.
So here is a run of a script I wrote for a test. Nothing special, it is just a kind of functional test for a library I am writing as a pet project. So how how about this video?
The first thing comes into my mind is the chance. So what is the chance of this thing, how random is the evolution, how likely or unlikely this whole paragraph comes out? Well, it is easy to answer, probability theory to the rescue!
The paragraph is 339 bytes long, that is 2712 bits. How many combinations are there in 2712 bits? Well, it is exactly 2^2712, that is
24737069014555859845395986704420368397658086633909521850064520013137\ 38505839815425754377722629610936704856351016492278841610858135471701\ 59800883397297807762608866284516899215245650157426338163043578742880\ 65348299327693009612846441050315820268534834566935920792626650677563\ 30938349921340514694266320593457550203601187244551007934323757937899\ 97058204523335837961688400144804933425013795327763813284185302219163\ 87981979506679352406793107901134917967085652531285509164461347047753\ 91802743679643536796400839221376144329712830249543115355542347093043\ 48028744559810168726862135785158835763964262599313747301938280122431\ 34460913690094311025695634009765493129192024740986806802515137264509\ 67051904562796161086614186174390704166953090842560106291242115958382\ 54214353696157066501565418589320316697771176183174893318691922483609\ 6
Yes, that's a number and that's actually a very big number. Let's say we try brute force, we create all the possible combinations to find this paragraph and let's say we can process 1000 combinations every seconds. There are 60 seconds in a minute, 60 minutes in an hour, 24 hours in a day and 365 days in a year. Let's say we calculate in million years as we often do when talking about evolution. Then we need this many millions of years to try all the possible combinations:
78440731273959474395598638712647033224435840417013958174988965034048\ 02466513874384051172382767665324406571381965031325601252086933890479\ 44574084846834753179251859096007417602884481726998789202954016815324\ 24366753322212739766763194603994863865217004588203706217106325081060\ 72229673773910815240570524459213439255457848948982140836896746378424\ 56425052395154229964765347998493573772874794925684339434884900492021\ 43524795493021792258983726221254813442052424312802857573761247614643\ 32200480972994472337648526196651903633031552034319873654053612040345\ 89132244291635491904052941987439230606177900175398742078698250007709\ 74317965785433507818669564972620158324429302197446749120101272401413\ 21194522332560125211232198675769609864767538186707592247723604637184\ 6212060405935142853109277837810856385645350134187878
Wow, that is still very big, mindbogglingly big. Let's say we can evaluate 1,000,000 combinations a second and we calculate in billions of years:
(2^(339*8))/(1000000*60*60*24*365*1000000000) 78440731273959474395598638712647033224435840417013958174988965034048\ 02466513874384051172382767665324406571381965031325601252086933890479\ 44574084846834753179251859096007417602884481726998789202954016815324\ 24366753322212739766763194603994863865217004588203706217106325081060\ 72229673773910815240570524459213439255457848948982140836896746378424\ 56425052395154229964765347998493573772874794925684339434884900492021\ 43524795493021792258983726221254813442052424312802857573761247614643\ 32200480972994472337648526196651903633031552034319873654053612040345\ 89132244291635491904052941987439230606177900175398742078698250007709\ 74317965785433507818669564972620158324429302197446749120101272401413\ 21194522332560125211232198675769609864767538186707592247723604637184\ 6212060405935142853109277837810856385645350134
So we can conclude, that many-many-many-many-many lifetime of the universe would not be enough to find this paragraph by brute force, by generating all the possible combinations hoping hat by pure chance we find the one combination of bits that we are looking for. And we did it in like 2 minutes?! That's remarkable, right?
'member how many times religious people say there is no way evolution works because there is just too many combinations, there is too little chance for them. Now you can send them here, show them these numbers. I hope I did not miscalculate them for they are truly unbelievable. I even put there some extra parenthesis so nobody thinks I am cheating.
So how come the program finished in under two minutes? How come it found the paragraph so fast? How can evolution triumph over probability?
The answer is very simple. The fitness function doesn't just say if the bit combination is what we wanted or not the one we are seeking, but also says which of the combinations is the better. The fitness function gives the possibility to gradually find the solution, to go step by step. This is way-way-way-way better than brute force.
And that's it, that's the answer for our question. The evolutionary process is gradual, it is going step by step. People say it is random and sure, random mutations are an important part of the whole process, but to say "evolution is random" is a criminal oversimplification here. You can't say "it's random", because then you miss the point by a lot. Look at the numbers, you miss the point by that much!
But then here is the next thing that pops into our mind...
So if it is gradual, then we could go step by step, bit by bit. We could simply set a lot of bits to 0, then go from the first to the next, set them to 1 and ask the fitness function "is this better, is this better?"... and of course if it is better we can leave them set to 1 if it is not, we leave the bit 0.
If we did this we can finish in 2712 steps. We don't need evolution here, we just do a slightly better search method. Playing twenty questions game with the fitness function, but of course instead of 20 questions we would need 2712 questions. Aaaand we would have finished in 3 seconds.
That's it, that's why I said in my previous post that this kind of evolving strings are not really evolution. Well, it is evolution, because the program does that, but the solution can be found without evolution even faster. So this program you see is simulating evolution, yes, but it is not really an achievement, what it does could be done without evolution even faster.
I use these string comparison evolution scripts as a benchmarks, to see that there is no software error, to see how efficient the code is. Finding one single solution that we know in advance is practically the definition of the word "test"... right?
Oh, yes, true, but then...
What would be a real evolution? Can we come up with a task the script has to do that needs real evolution, that can't be done by going twenty questions? Moreover can we come up with a class of problems that need evolution and not just a smart search? What would be a definition of such a class, can we formulate a check that decides if a problem has no bit by bit search solution but have a chance to be solved by evolution? Well, probably not, this last one sounds like computability theory, but there might be some subset of problems we can handle, right?