MU puzzle

The MU puzzle is an example of a Formal system we will take a look at, as described by Douglas Hofstadter in his book Gödel, Escher, Bach.

We’re given a starting string MI, and some transformation rules.

Here are the transformation rules:

Nr.	Formal rule			Informal explanation	Example
1.	x`I`	→	x`IU`	Add a `U` to the end of any string ending in `I`	`MI`	to	`MIU`
2.	`M`x	→	`M`xx	Double the string after the `M`	`MIU`	to	`MIUIU`
3.	x`III`y	→	x`U`y	Replace any `III` with a `U`	`MUIIIU`	to	`MUUU`
4.	x`UU`y	→	xy	Remove any `UU`	`MUUU`	to	`MU`

Here is an example usage to derive MIIU from MII for some of the transformation rules:

MI (an axiom)
MII (by rule 2)
MIIII (by rule 2)
MIIIIIIII (by rule 2)
MUIIIII (by rule 3)
MUUII (by rule 3)
MII (by rule 4)
MIIU (by rule 1)

More formally, we can represent the MU puzzle as follows:

Language
1. The set of symbols is { M, I, U }.
2. A string is a grammatical sentence (wff) if its first word is M, and no other words are Ms. E.g.: The following strings are grammatical sentences: M, MIUIU, MUUUIII.
MI is the starting string, thus an axiom.
The inference rules are the transformation rules we’ve just defined above.

The question now is, can we convert MI to MU using the transformation rules?

In order to answer this, we will use invariant (a property that holds true whenever we apply some of the rules) with induction to prove our claim.

What would be a good invariant here?

Let’s suppose we can somehow get to MUIIIU. Now, if we apply rule 3 to it, we get MUUU. Apply rule 4, and pure win!

Note that, in order to be able to apply rule 3, we need to have the number of subsequent I’s to be divisible by 3. So let’s have our invariant say that “There are no subsequent I’s in the string that are divisible by 3”.

1. For the starting axiom, we have one I. Invariant OK.
2. Applying rule 2 will be doubling the number of I’s, so we can have: I, II, IIII, IIIIIII (in particular, 2^n I’s). Invariant OK.
3. Applying rule 3 will be reducing the number of I’s by 3. But note that 2^n – 3 is still not divisible by 3. Invariant OK.

So we’ve shown that with the starting axiom MI it is not possible to get to MU. But, what if we have a different starting axiom? Or even, different rules? 🙂

But if we look carefully, we’ve used a different formal system to reason about MU (i.e. divisibility by 3). This is because the puzzle cannot be solved in its own system. Otherwise, an algorithm would keep trying different inference rules of MU indifinitely (not knowing that MU is impossible).

In general, for any formal system there’s this limitation. Gödel’s theorem shows that there’s no formal system that can contain all possible truths, because it cannot prove some truths about its own structure.

So, having experience with different formal systems and combining them as needed can be useful 🙂