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 aU
at the end.Suppose you have
Mx.
Then you may addMxx
to your collection.If
III
occurs in one of the strings in your collection, you may make a new string withU
in place ofIII
.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.