# On Decidability and the MU puzzle

Gödel, 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
2. `Mx -> Mxx`, where `x` matches the rest of the string
3. `xIIIy -> xUy`, where `x` and `y` match the rest of the string
4. `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`.

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

Each string `Mx` in the new system now has a form using only an `M` followed by `I`s, constructed by expanding all `U`s.

``````   MUIU
=> MIIIIIII

MU
=> MIII

MI
=> MI
``````

Define the value of a string to be the number of `I`s in it, after transforming it to its `MIIIIII...III` form.

``````value(MUIU) = 7
value(MU) = 3
value(MI) = 1
``````

The value of our target `MU` is 3, which is divisible by 3, while the value of our starting string `MI` is 1, which is not divisible by 3. If we can show that, starting with a string of value not divisible by 3, every rule application cannot create a string with value divisible 3, then it is also impossible to get `MU` by starting with `MI`.

So take a string `Mx` whose value is not divisible by 3. Rules 1, 3 and 4 preserve the value of `Mx` modulo 3, so by assumption the resulting string also has value not divisible by 3.

Rule 2 doubles the value of a string. However, by doubling any number which is not a multiple of 3 we can never create a number divisible by 3: a number `n` is divisible by 3 iff 3 is one of its prime factors. When doubling `n` the only prime factor we add is 2, hence the resulting number also cannot have 3 as a prime factor. We can express this more succinctly as

``````∀x. x ≠ 0 (mod 3) --> 2x ≠ 0 (mod 3)
``````

Thus `2*n` is not divisible by 3, and we can never construct the string `MU`, starting from `MI`.

# Characterizing all generatable strings

Not only have we shown that `MU` is not constructible, starting from `MI`, but also any other string with a value divisible by 3. The question remains: which strings can we generate? Is it possible to generate all other strings, i.e. all strings `Mx` such that `value(Mx) != 0 (mod 3)`?

The answer turns out to be yes, using the following algorithm.

1. Generate `My = MIIIIII...III` by applying rule 1 to `MI`, such that the following holds: the value of `My` is larger than `Mx` and `value(My) = value(Mx) (mod 3)`.
2. Append `U` if `value(My) != value(Mx) (mod 6)`.
3. Merge `IIIIII` to `UU` and delete until `value(My) == value(Mx)`.
4. Replace the `MIIII...III` with `Mx` by applications of rules 2 and 3.

It is always possible to apply step 1: the infinite sequence of strings generated by repeatedly applying rule 1 to `MI` has values `1, 2, 4, 8, 16, 32, ...`, generating all powers of 2. Taking these values modulo 3 we get `1, 2, 1, 2, 1, 2, 1, 2, ...`, i.e. `2^i (mod 3)` is `1` if `i` is even, and `2` otherwise. Since `value(Mx) != 0` by assumption, there always exists a longer string `My` such that `value(My) = value(Mx) (mod 3)`.

In step 3 we need to delete `U` pairs until we have that `value(My) = value(Mx)`. Unfortunately, we can only decrease `value(My)` in steps of six, since we can only remove `U`s in pairs. This is where rule 2 comes into play: if `value(My) != value(Mx) (mod 6)`, then there would always be one `U` left over. (Note: since these values are congruent modulo 3, the only possible case is that `value(Mx) == value(My) + 3 (modulo 6)`). Appending an additional `U` before deleting `UU`s, increases `value(My)` by 3, and everything works out.

Step 4 is simple: `Mx` has the same value as `My` and we can use rule 2 to convert `III`s to `U`s, in the right positions. Thus we have shown that the `MIU` system lets us generate precisely the strings which have a value not divisible by 3.

# The MIU-system and decidability

The MIU-system isn’t just a neat puzzle to solve: Hofstadter shows the reader that some questions about formal systems cannot be answered solely from within. Rather, we had to step outside the restrictions placed upon us by the four rules to successfully answer the question.

Given infinite time we could have concluded this ourselves, by generating all possible strings: however, in this case there exists a solution which is finite. We have constructed a decision procedure which solves not only the MU-problem, but any decision problem of the form “Does candidate string `Mx` belong to the MIU-system, starting from `MI`?”.

It is not always possible to find a finite decision procedure. Take for example all strings which are valid C programs (or choose any other sufficiently powerful language, it doesn’t matter). The decision problem “Does a given C program terminate at some point?” is not solvable in finite time, as shown by Alan Turing (1936). This problem is also known as the halting problem, and is one of the most famous undecidable problems.

These abstract problems can even have real world consequences: this year it was shown that type-checking a Swift program is also an undecidable problem. The author shows that in order to type-check a program, the compiler must solve the word problem for finitely generated groups. I like how this example shows us that some abstract problems pop up in unexpected places, and why seemingly purely theoretical knowledge matters, even for applied problems such as building compilers.

If you have any questions or comments feel free to reach out to me via my public inbox. If you are interested in undecidability in other programming languages, you might also like this website I made: typing-is-hard.ch.

## Articles from blogs I follow

### What's cooking on Sourcehut? January 2021

Another year begins, and hopefully with better prospects for us all. SourceHut has emerged from 2020 relatively unscathed, thankfully, and I hope the same is true of most of our users. A body which, by the way, today numbers 19,647 strong, up 623 from Decemb…

via Blogs on Sourcehut on

### New PGP Key Fingerprint

New PGP Key Fingerprint This morning I got an encrypted email, and in the process of trying to decrypt it I discovered that I had lost my PGP key. I have no idea how I lost it. As such, I have created a new PGP key and replaced the one on my website with it. …

via Christine Dodrill's Blog on

### Status update, January 2021

Hello from the future! My previous status update was last year, but it feels like it was only a month ago. I hope you didn't miss my crappy jokes too much during the long wait. One of the advancements that I would like to mention this month is the genera…

via Drew DeVault's blog on