# 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:

- If the string 'MxI' can be derived, so can the string 'MxIU'.
- If the string 'Mx' can be derived, so can the string 'Mxx'.
- If the string 'MxIIIy' can be derived, so can the string 'MxUy'.
- 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 |

## MU^{n}

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