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
- The set of symbols is { M, I, U }.
- 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? 🙂