Start with MI. Using four simple rules, can you ever reach MU?
Douglas Hofstadter's 'MIU system' has just one starting string, MI, and four rules for rewriting strings of M, I and U: add a U to the end of any string ending in I, double everything after the initial M, replace any III with a U, or delete any UU. Apply the rules in any order, as many times as you like, always starting from MI. The challenge: can you ever produce the string MU?
Reveal the answer
No — it's impossible, because every rule preserves a hidden invariant: the number of I's in the string, modulo 3, can never become 0 (MI starts with one I, MU has zero). Hofstadter uses the puzzle in 'Godel, Escher, Bach' (1979) to show the difference between working inside a formal system and reasoning about it from outside, foreshadowing his discussion of Godel's incompleteness theorems.
— Douglas Hofstadter, Godel, Escher, Bach: An Eternal Golden Braid — Chapter I, 'The MU Puzzle', 1979
Go deeper: get the book →