Gödel Escher Bach - MIU System

I'm currently reading Gödel Escher Bach. His first formal system he introduces is the MIU system. It follows four rules.

  1. If you posses a string whose last letter is I, you can add on a U at the end.
  2. Suppose you have Mx. Then you may add Mxx to your collection.
  3. If III occurs in one of the string in your collection, you may make a new string with U in place of III
  4. If UU occurs inside one of your strings, you can drop it.
The Goal of the Book is to get from MI to MU. You can use the applet below to apply the rules, for feedback, check the console.

MIU System Applet

So how to get from the I to the U?

The only rule that can reduce the number of I the the 3rd rule, so we should focus on that. To remove all I, we need to fullfill count(I) mod 3 = 0, which means that the number of I must be divisible by 3. count represents the number of I, mod is the mathematical operation modulo.

With the second rule, we can duplicate the starting I. But doubling a number that is not divisible by 3 will never make it divisible by 3.

Proof sketch:

Suppose you have a number n that is not divisible by 3, so n mod 3 != 0, which means that n = x * 3 + y, where x can be any number and y is 1 or 2. When doubling the number we get n * 2 = x * 6 + y * 2. y * 2 is now 2 or 4, both numbers are still not divisible by 2. x * 6 is divisible by 3, so adding 2 or 4 will make it not divisible by 3.

Reducing the number of I by 3 obviously won't help, we can only use this rule in a useful way when we already have a number that is divisible by 3. All other rules don't affect the number of I.

So the first exercise given by Douglas Hofstadter in Gödel Escher Bach is impossible to solve.

When you don't believe this proof, simply try it out and check if you're able to find a solution. You won't.

The code for this page can be found at https://github.com/TN1ck/MIU.