# MIU puzzle

The MIU puzzle (also known as the MIU system) was introduced in Gödel, Escher, Bach: an eternal golden braid by Doughlas Hofstadter (who I once saw on July 16, 1979). The remarks on this page are the result of Annabel borrowing the book from the library on May 8, 2004.

The MIU system consist of one axiom, and four rules for deriving strings over the alphabet 'M', 'I', and 'U'. The axiom is the string 'MI'. The rules are:

1. If the string 'MxI' can be derived, so can the string 'MxIU'.
2. If the string 'Mx' can be derived, so can the string 'Mxx'.
3. If the string 'MxIIIy' can be derived, so can the string 'MxUy'.
4. If the string 'MxUUy' can be derived, so can the string 'Mxy'.
The MIU puzzle consists of the question whether MU can be derived. The answer is no, but this can only be proven by stepping outside the system by realizing that in all string that can be derived the number of I's does not divide by three.

In an attempt to find a derivation, Annabel found a circular derivation. This made me wonder if more of such circular derivations existed. The smallest circular derivation starting with 'MI' is 'MI' -> 'MII' -> 'MIIII' -> 'MIIIIU' -> 'MIUU' -> 'MI'. It also made me think about the structure of the derivation tree. For this purpose I started to develop some small programs. Quickly, I noticed that the number of derivations grows very quickly, faster than any recurrence equation (more than exponential).

 generation derivations found derivation in this generation distinct derivations equivalent derivations 1 1 1 1 1 2 3 2 2 2 3 6 3 3 3 4 11 6 6 6 5 25 15 16 16 6 69 48 60 60 7 282 232 356 356 8 1730 1544 3227 3222 9 15885 14959 44310 44187 10 210105 203333 928650 925845

For the number of distinct derivations, we count each possible application of a rule. That means that if a sequence contains three U's in a row, replacing these three U's by one, is counted as two derivations, because it can be done by removing the first two and the last two U's. For the number of equivalent derivations we do not make such a difference, meaning that the derivation of three U's to one is counted as one, instead of two.

Also the number of derivations that result in 'MI' grows fast. See the following table for the numbers:

 generation derivations found derivation in this generation distinct derivations equivalent derivations 1 1 1 1 1 2 3 2 2 2 3 10 7 8 8 4 36 26 49 49 5 138 102 397 397 6 541 404 3987 3987 7 2148 1613 48011 48011 8 8571 6452 673683 673637 9 34263 25834 10797059 10796173 10 137058 103415 194598689 194578607

## MUn

When strings are restricted to only M and U, only two rules are applicable. The first and the third rule cannot be used because the include the use of I. As a result of this, the structure of the derivation graph becomes rather regular. For each string with an even number of U's there is a circular derivation of length n/4 + 3/2 rounded down to a whole number, where n is the number of U's. Note that this formulea even holds for the string M with n equal zero. the string M has a circular derivation of length 1, when the second rule is applied for an empty string, which is valid, because there is no mentioning of forbidding it. Strings with an odd number U's do not have a circular derivation. Applying the second rule will always result in an even number of U's. Application of the third rule will keep the number of U's odd, but through this way we can only increase the number of U's. There is thus no way to make a cycle.

Home and email