--- title: "On Decidability and the MU-puzzle" date: 2020-12-12T00:00:00+01:00 tags: math, decidability draft: true --- [Gödel, Escher, Bach](https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach) takes the reader on a journey through mind, music, machines and self-reference. In the first few chapters, Hofstadter introduces a formal system called the MIU-system. The MIU-system consists of four simple rules for manipulating strings consisting of the characters `M`, `I` and `U`. 1. `xI -> xIU`, where `x` can be any string 1. `Mx -> Mxx`, where `x` can be any string 1. `xIIIy -> xUy`, where `x` and `y` can be any strings 1. `xUUy -> xy`, where `x` and `y` can be any strings Note that the placeholders `x` and `y` must always match the entire string, i.e. the application `MII -> MIII`, choosing `x = I`, is not valid. The correct application is `MII -> MIIII`. Then Hofstadter asks the reader to answer the MU-puzzle: > Given the initial string `MI`, is it possible to construct the string `MU` using only the four above rules? Take a few minutes and try for yourself. Many people quickly suspect that it is impossible, but why? # The solution Let us add an additional, imaginary rule.
1. `xUy -> xIIIy`, where `x` and `y` can be any strings