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 stringxIIIy -> xUy
, where x
and y
can be any stringsxUUy -> xy
, where x
and y
can be any stringsxI -> xIU
, where x
can be any stringNote 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 stringMU
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.
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.
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)
.U
if value(My) != value(Mx) (mod 6)
.IIIIII
to UU
and delete until the value of My
is the value of Mx
.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.