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.