#title: "The MIU system" date: 2020-12-12T00:00:00+01:00 tags: math draft: true

In Gödel, Escher, Bach, 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. Mx -> Mxx, where x can be any string
2. xIIIy -> xUy, where x and y can be any strings
3. xUUy -> xy, where x and y can be any strings
4. xI -> xIU, where x can be any 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.

Hofstadter asks the following:

Given the initial string MI, is it possible to construct the string MU using only the four rules above?

Take a few minutes and try for yourself. Many people quickly suspect that it is impossible, but why?

Let us add an additional, imaginary rule.

1. `xUy -> xIIIy`, where `x` and `y` can be any strings

Each string Mx in the new system now has a form using only an M followed by Is, constructed by expanding all Us.

   MUIU
=> MIIIIIII

   MU
=> MIII

   MI
=> MI

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

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

The rules 2, 3, and 4 preserve value of a string modulo 3. The only operation which changes the number of Is is rule 1: it duplicates x, hence it doubles the value of a string.

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.

Our goal is to show that, starting with a string of value not divisible by 3, every rule application cannot create a string with value divisible 3.

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

Rule 1 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 is divisible by 3 iff 3 is one of its (unique) prime factors. By doubling a number the only prime factor we potentially add is 2, hence the resulting number also cannot have 3 as a prime factor, and is not divisible by 3.

We can express this more succinctly as

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

#Characterizing all generatable strings

We have just shown that any string with value divisible by three cannot be generated in the MIU system if starting from MI. The question remains: Which strings can we generate? Is it possible to generate all other strings Mx, i.e. those with value not divisible by three?

The answer turns out to be yes, using a simple 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 the value of My is the value of 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 odd, 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 Us in pairs. This is where rule 2 comes into play: if value(My) != value(Mx) (mod 6), then there would be one U left over. (Note: since these values are congruent modulo 3 the only possible case is that value(Mx) + 3 == value(My) (modulo 6)). Appending an additional U before deleting UUs, increases value(My) be 3, and everything works out.

Step 4 is simple: Mx has the same value as My and we can use rule 2 to convert IIIs to Us, 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.