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`

.

`Mx -> Mxx`

, where`x`

can be any string`xIIIy -> xUy`

, where`x`

and`y`

can be any strings`xUUy -> xy`

, where`x`

and`y`

can be any strings`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.

- `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
`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 rules 2, 3, and 4 preserve value of a string modulo 3. The only operation
which changes the number of `I`

s 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)
```

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.

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

. - Append
`U`

if`value(My) != value(Mx) (mod 6)`

. - Merge
`IIIIII`

to`UU`

and delete until the value of`My`

is the value of`Mx`

. - 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 `U`

s 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 `UU`

s, 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 `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.