A Fool's Hope

I love the FIFA World Cup, it's the one global sporting event I'm guaranteed to be excited about regardless of who is playing. Coming from a nation that admittedly is not a football powerhouse, most times I don't have to watch knowing the inevitability of watching my nation drop out - because we're not even there to begin with!

But this time, like last time, we are there. And that changes things as a spectator. While I would love Australia to win and hope they do, realistically I'm expecting them to exit. Because ultimately while teams in our position occasionally make fairy-tale runs, we're there to make up the numbers. I don't say that cynically, plenty of nations are there that won't win. But even to get that far (remember this is the finals, it takes years of hard work to qualify) is a fantastic achievement and something to be proud of our team for doing.

For years Australia was a big fish in a small pond, dominating a region of Island nations where the closest thing to a challenge was taking on the rugby nation of New Zealand. Getting to the 2006 World Cup at the expense of Uruguay and moving into Asia were huge for our development as a football nation. That we qualified for the finals and were among the first nations to do so (Japan and Netherlands qualified that same day) should be enough.

Nonetheless I'm still disappointed when we lose. The match against Germany was pathetic, they are a better team and traditional world cup powerhouse, but still it was painful to watch. Perhaps we as Australians aren't used to being a small nation in any sport, we're either world contenders or we just don't care. Football is something the whole world cares about and we aren't on top!

The atrocious time zones make watching games tough. I pushed sleep last night to catch the Socceroos draw with Ghana, wrapped in a blanket and staring intently at the television. It was a game we (as in Australia, collectively, expressing themselves through a sporting team) needed to win and we couldn't do it. But thanks to Serbia shocking Germany, qualifying is still a real possibility however improbable. If we can beat Serbia, we stand a chance of qualifying regardless of the outcome in the game between Germany and Ghana.


It's not guaranteed that if we win we qualify. We have to win convincingly, how convincingly depends on the outcome for the other game. If we lose or draw, we're out so those results aren't to be considered. So take the three outcomes.

1. Germany win - If I were a betting man this is the outcome I would bet on. If Germany beat Ghana, the margin in that game and our game matters. Ghana are currently +1 in their goal difference while we are -4. We have to get a higher goal difference or equal to where we score a greater number of goals. So if Germany win 1-0, we'd have to win by 4 goals against Serbia. A 3 - 0 score-line would mean we have to by 2 goals.
2. A draw - If there's a draw then we would need to win by 7 goals, maybe 8 if the draw is a 3-3 score-line. So it is possible but terribly unlikely.
3. Ghana win - We would only need to win against Serbia if Ghana manage to upset Germany.

Of course Serbia have a say in all this too, it's not just pure will on account of our Socceroos. But in sport it never is. But all is not lost yet, and it's not purely on the hope that things will go our way (unlike France who will be knocked out regardless of their result if Mexico and Uruguay draw). We can qualify regardless of the result in the other game and that's enough to give me hope. A fool's hope, but hope nonetheless.


Unlike fans of England, inevitable exit is an expectation rather than seen as a perpetual failure. Truth be told, I'm just happy our team is there. The performance last night was enough to show that we did deserve our place in the final 32 even if we don't go beyond that. Playing with 10 men for over half a man and holding our own against one of the best African nations going while showing the resolve we normally characterise with being Australian, it was something positive to take away. And when we do go out, there's still going to be enough great football to watch, but it will be different. Aussies are used to being passive observers of the world up, which is what we will go back to being the moment we lose. Until that time, I reserve my right as a spectator to engage in all the highs and lows and feeling robbed by dodgy refs that comes with being one!

Cannot Prove A Negative?

Recently, upon several recommendations, I picked up Gödel, Escher, Bach by Douglas Hofstadter. I figured given the size of the book, if I start now I should finish before the end of the year. So last night when I had a spare 30 minutes or so before dinner, I settled down to read and the first thing he does is gives a puzzle for the reader. So much for just sitting and reading, I scrambled to get a pen and paper then follow his very simple system in order to solve the puzzle.

The idea was that in the system there were just letters: M, I, and U. And there were four rules to go with the letters

1. If the string ended with an I, then a U could be added. e.g. UMI -> UMIU, MUIIUI -> MUIIUIU
2. Anything following an M could be doubled. e.g. MI -> MII, MIU -> MIUIU, MUIIU -> MUIIUUIIU
3. Three I's could be replaced with a U e.g.IIIIUI -> IUUI, UIIIUII -> UUUII
4. Two U's in a row could be removed e.g.IUUMI -> IMI, UUIU -> IU

Now that those are out of the way, Hofstadter gives the seemingly simple challenge of getting from MI to MU. Pen and paper come out and I sketch what I think is a solution. All finished, man it was easy. Then reading on a few more paragraphs, I realise that I made a mistake. Sure enough, I look back and there was a misapplication of rule 2. Okay, try again.

The first thing is that you can work out the first few steps. To get anywhere, you first need to apply rule two twice. Otherwise you'll forever be caught in an infinitely increase sequence of MIU(IU(IU(...))). So one goes from MI to MIIII before some interesting things can happen.

20 minutes of trying different things and no luck. Sit down to eat dinner and watch TV and still no luck. Had the pen and paper sitting next to me, and even when I thought I had a revelation on how to do it, I just couldn't get there. I tried working backwards, hoping I would be able to see a solution if I could come from the other angle, but still no luck. Final throw of the dice was to think about it mathematically.

With the rules as above, I derived values. I is worth 1 and U is worth 3 (rule 3). So with rule one, It is a +3. Rule two is a x2, or a doubling. Rule four is a -6. M is completely irrelevant as it will always be the front.


The thing is I could go to infinity and not find a solution. Yet I don't have infinite time nor patience. If I want to say it's impossible to get from MI to MU, then I can't use my inability to derive a solution as evidence. It might just be I'm a moron or I've missed something tricky. If I want to say that it is impossible (as I was beginning to suspect), I need a means of demonstrating that. Hence mathematics.

In the last move, you need something that is divisible by 3. But with the operations allowed by the system, such a number could never come about. If you look at something derivable like MUIU, it is 3+1+3. Which is not divisible by 3 (to get a whole number). +3 or -6 will only ever land you on something that is divisible by 3 if the number was already divisible by three to begin with. Likewise, doubling a number will never get you to something divisible by 3 unless it is already divisible by 3.

So given the starting point is MI, one can never get to MU given the rules allowed in the system. Of course my demonstration rests on axioms that I do not care to prove in the same way, and for the sake of argument I'll call both axioms about doubling and adding subtracting multiples of threes to be self-evident.


So why write this up on the blog? Firstly, he won't give an answer in the book just yet. So instead of maybe having to wait several hundred pages by which time I've forgotten my working to see if I was correct, if I'm flawed in my thinking I want to have a record of it where there is the possibility of being shown I'm wrong.

Secondly, it demonstrates something about human reasoning. And I think this is what Douglas Hofstadter is trying to get across. That we can see patterns such as MIUIU as leading to infinities despite not having direct domain knowledge nor having the time to write out the infinite sequence to demonstrate it.

In about the same time as it took for me to give up on trying to find a solution, I could have written a program to do it all for me. It could have brute-forced, making a tree of all possible moves from each position and hopefully getting to a solution if one existed. But at what stage could I get the computer to recognise the point of futility? When it runs out of memory? When strings get passed a certain size?

This isn't a finite search space, it's an infinite one. The string MIU will increasingly get higher and higher with the only rule that can apply to it (rule 2). Such a brute force strategy would not be able to recognise such a situation without an explicit check for such circumstances.


So to bring this to a final point, consider the scenario. While I was looking for a proof, instead what I wound up with is a proof of impossibility. Now this is fine in mathematics, but it is not fine in matters empirical. Take the Douglas Adams concept of fairies at the bottom of my garden. Now I can't disprove there are fairies by digging and digging, nor can I disprove the existence of fairies logically. Does this mean I should believe in the fairies or at the very least be a fairy-agnostic?

No! The very fact that I cannot give an absolute guarantee that fairies aren't there in no way compels me to even consider that there are. Why am I meant to consider the possibility of fairies in the first place? To posit that I should be a fairy-agnostic or a believer in fairies seems to me to necessitate first a reason to consider that there might be fairies in the first place. The lack of philosophical or logical impossibility to the concept is not sufficient to place the notion of fairies as anything to worry about in the first place.

There's a monkey sitting at a typewriter

Mathematics is the language of science, so having a grasp on the mathematical concepts used is vital in order to understand much of what is written. Understanding the difference between coincidental and causal events is vital in order to understand statistics. Our brains work on linking causal events, if I press the 'x' key on my keyboard I expect there to be an 'x' written in my text editor. Likewise, all the keys on the keyboard have function and using that same causal relationship I can write entire blog posts. I am conveying information in a causal manner. Now what if it were random? Could a random generator recreate a post of mine, or even a single sentence?


Generating improbability
Now there's a few ways of going about this, take the sentence "mathematics is the language of science", taking the lower-case alphabet and the space character, there are 38 spaces and 27 different characters to go in each. Note that Dawkins did a similar computational experiment in The Blind Watchmaker.

• random chance - suppose you tried to generate every position and every character at once. To get the first character correctly would be a 1 in 27 chance. As would generating the second character. To generate both characters correctly would be (1/27)² or 1 in 729. To generate three characters correctly would be (1/27)³ or 1 in 19,683. To generate all 38 characters correctly would be 1 in 27³⁸ or 1 in 2.5*10⁵⁴. So for this one off event to happen, it would take an extraordinary amount of time to generate it by chance with purely random input.


• cumulative chance - instead of trying to generate it all in one go, generating each character individually could work better. Start with the first character, and there's a 1 in 27 chance of generating 'm'. So when 'm' is finally generated, move onto trying to generate the 'a'. Now each subsequent character generation is dependant on earlier chance encounters. To generate 'math' now becomes (1/27) + (1/27) + (1/27) + (1/27), or 1 in 108. For all 38 characters, it's (1/27) * 38 or 1 in 1026. So by progressively doing each step along the way, it takes away an extreme amount of improbability.


• evolving chance - back to generating in one go. By starting at an arbitrary point and tweaking the string, eventually it will come up with the right answer. The mathematics for this is not easily expressed, though it can be expressed in code.

The results
I wrote a java program to simulate these different processes. The source code is available here for anyone wishing to run it themselves. Feel free to modify it, and push it to it's limits. It's very much a cobbled together hack-job, there wasn't much focus on having a clean interface. It's there to show I didn't make the results up, and while the randomness of the PC will mean that the numbers will not turn out the exactly same as mine, they are a good approximation of the procedure.

• random chance will not generate a computational answer, computer randomness is based on seeds so it will run infinitely without ever finding the answer. If it were truly random, then it would still take an almost infinitely long time. I ran the program quite a few times and there wasn't even a fragment of any word that could be considered English.


• cumulative chance has yielded similar results to the mathematical prediction of an average of 1026 iterations. Running it 10 times, I had the following results: 1058, 867, 1077, 1403, 776, 943, 1081, 893, 945, 880. This is an average of 992 iterations for the result. Doing it again for 10 iterations yielded the result 1028. A third time with 100 iterations yielded an average of 1008. A few more times and I did get 1026 as the average over 100 iterations. The practical application of statistics correlated with the theoretical application.


• evolutionary chance brought an even quicker result. By adjusting the amount of mutation (a mutation rate of 1 would mean 'd' could only change to either 'e' or 'c', 2 would cover the spread from 'b' to 'f'), the length of time could decrease. The results for running it 100 times on different mutation rates were as follows:
  

A run through with a mutation variance of 5
Iteration: 1 tptvelwhiqt irsirfpokxpub skrjcgrhcslt
Iteration: 2 - qrtyekzgimy iunhtirkibrubetjuhelueerot
Iteration: 3 - nqt efxfiru irmkojmmkdquddqesjeoxieoov
Iteration: 4 - rmtzedthiov ivmoohqrkdsufencsfhquiesly
Iteration: 5 - whteedtiity iyktnkpulfnudjmcrfgnuiewpz
Iteration: 10 - tftjeclaiww ivdtocswahguajjo fodwieurb
Iteration: 20 - hvtheixaifs in tfwlladguarexffqjpievcr
Iteration: 30 - natheoetias is thyhlamguadeohfinsieucx
Iteration: 40 - mathematigs is th tlacguaoepcflnniescg
Iteration: 50 - mathematics is th uladguauewdformiemce
Iteration: 60 - mathematics is thdilajguabe lfdskiebce
Iteration: 70 - mathematics is thwtlacguaje ofksniefce
Iteration: 80 - mathematics is thkjlauguape of syievce
Iteration: 90 - mathematics is the language of snience
Found iteration 97 - mathematics is the language of science

And what of those monkeys?
The first two methods would be simulations of how a monkey would type: the first method would be the equivalent of letting a monkey type the entire post and have it start from scratch over and over if there would be any errors. The 2^nd method is like the monkey using the backspace key each time it got something wrong. The evolving algorithm is unlike random chance, it's to illustrate that information of almost infinite improbability can emerge over a far shorter space of time.

Including white space, my posts average around 7,000 characters. By the time a post is finished, the amount of characters I press is probably a lot higher when taking into account typos, spelling and grammatical errors, deletion of poor sentences, and proof reading. All up, it wouldn't be entirely unfair to say I do about 10,000 key strokes per post. Now if I do 200 keystrokes a minute, then it would still take me 50 minutes or so to get the post to where it is now. To evolve or generate something like this by chance is theoretically possible, but practically impossible.

This is why when we see a code or information we know there's intelligence behind it. To look on the great pyramids, the symbols contained therein are the product of intelligence and intent. Anyone who has had previous dealings with the written word would be able to understand the symbols are the same construct. To go back further into human history, the same could be said of cave paintings. It is not the refined symbolism of the written word, but it's evidently communication. Other forms of communication do exist that are not so obvious, smoke signals for example. There are times too when we can mistake natural order and randomness as communication, the stars say astrology is a joke and our futures are not etched into the palms of our hands.

We can infer meaning from non-meaningful processes, this is the problem with the statement "all codes are a product of intelligence". We see patterns all through nature, improbable shapes, repetition, improbable assortment, all of which come from natural processes. One of these patterns is the pattern of DNA, the double-helix structure that has the instructions on the building blocks of life. How could this occur naturally? Well, that's for another entry. The importance of the tests above what to highlight the difference between random chance and a cumulative or an evolutionary process. It was to show that improbable events can be created quite quickly using select processes.