The MU-puzzle

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.

2. Suppose you have Mx. Then you may add Mxx to your collection.

3. If III occurs in one of the strings 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.

# 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.

---