--- title: "On Decidability and the MU puzzle" date: 2020-12-13T00:00:00+00:00 tags: [math, decidability, short-and-sweet] --- [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` matches the rest of the string 1. `Mx -> Mxx`, where `x` matches the rest of the string 1. `xIIIy -> xUy`, where `x` and `y` match the rest of the string 1. `xUUy -> xy`, where `x` and `y` match the rest of the string 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