The real first chapter of Gödel, Escher, Bach is an introduction to Formal Systems^[?] (what I previously thought was Chapter 1 was actually an introduction to the entire book).

Here's a puzzle from that chapter:

Given the starting string "MI", what is the quickest way to turn it into the string "MU" using only the following rules: (where x and y represent any string)

1. Any string ending in I may have U appended to the end:
   xI → xIU (e.g. MI → MIU)
2. Any string beginning with M can have the following letters doubled:
   Mx → Mxx (e.g. MIU → MIUIU)
3. Any occurrence of III may be replaced with U:
   xIIIy → xUy (e.g. MIUIII → MIUU)
4. Any occurrence of UU may be removed:
   xUUy → xy (e.g. MIUU → MI)

Answers on the back of a postcard; Prizes for the correct solution.