# The MU-puzzle

Gunar Gessner

May 14, 2020

Onf of the most central notions in the books isthat of a *formal system* (most especifically, the Post production system).
To provoke curiosity, Dr. Hofstadter proposes a puzzle.
The MIU-system
Only the letter M I U
Start with MI

This is a puzzle proposed by Dr. Douglas Hofstadter in his book Gödel, Escher, Bach. The intention is that by paying with this puzzle the reader familiarizes themself with the concept of formal methods. If you write code, as a hobby or professionally, you might think to skip it. Assuming we've seen such formal methods countless times. But I suggest that you take a second look.

The rules:^{1}

If you possess a string whose last letter is

`I`

, you can add on a`U`

at the end.Suppose you have

`Mx.`

Then you may add`Mxx`

to your collection.If

`III`

occurs in one of the strings in your collection, you may make a new string with`U`

in place of`III`

.If

`UU`

occurs inside one of your strings, you can drop it.

## # Can you produce `MU`

?

Assuming you've played a little with the above,
each of the strings you may have reached
are called a "theorem".
Not in the mathematical sense of someone proving something
but in *formal systems*, instead of being *proven*,
theorems are merely *produced*, as if by a machine.

MI was a theorem given for free such a "free" theorem is called an axiom

Hofstadter's argument is that there are two modes of thinking. Thinking *in* the system and thinking *on* the system.