(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?

MI

duplicate MI by rule 2

MII

dupilcate MII by rule 2

MIII

use rule 3 to replace III with U

MU

Posted by quddous behrouzi on 2002-06-21 09:03:57