Written on 21-May-2008 by asqui
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)
- Any string ending in I may have U appended to the end:
xI → xIU (e.g. MI → MIU)
- Any string beginning with M can have the following letters doubled:
Mx → Mxx (e.g. MIU → MIUIU)
- Any occurrence of III may be replaced with U:
xIIIy → xUy (e.g. MIUIII → MIUU)
- 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.