(from Gödel, Escher, Bach: an Eternal Golden Braid by Douglas R. Hofstadter)

Start with a single sequence of letters: MI

The goal is to apply a series of manipulations to this sequence to produce MU.

The allowable manipulations are:

1. If the sequence ends in I, you can append U

2. If the sequence begins with M, you can duplicate the string after M, e.g. MIII can be replaced by MIIIIII or MIMU can be replaced by MIMUIMU

3. If the sequence contains III, you can replace the III with U, e.g. UIIIM can be replaced by UUM.

4.If the sequence contains UU, you can delete the UU, e.g. UUM can be replaced by M or MIUUI can be replaced by MII.

These rules are all one-way; you can't take a U and replace it with III.

Is it possible to reach MU from MI? If so, what series of steps would you take to get there? If not, why not?

It's impossible. Look at what each rule does to the number of I's in the string:

Rule 1: Leaves number of I's unchanged.
Rule 2: Doubles number of I's.
Rule 3: Reduces number of I's by 3.
Rule 4: Leaves number of I's unchanged.

If the initial number of I's isn't a multiple of 3, then you'll never create a string where the number of I's is a multiple of 3. Hence, you can't get from MI to MU.

Posted by Jim Lyon on 2002-06-21 07:46:05