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).

generationderivations foundderivation in this generationdistinct derivationsequivalent derivations
11111
23222
36333
411666
525151616
669486060
7282232356356
81730154432273222
915885149594431044187
10210105203333928650925845

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:

generationderivations foundderivation in this generationdistinct derivationsequivalent derivations
11111
23222
310788
436264949
5138102397397
654140439873987
7214816134801148011
885716452673683673637
934263258341079705910796173
10137058103415194598689194578607

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