Il sistema MIU

Avete a disposizione un alfabeto che comprende solo tre lettere: M, I, U. Potete comporre stringhe con queste lettere a partire da una stringa già presente, ma seguendo queste regole obbligatorie:
(a) Se una stringa termina con una I, si può aggiungere una U; quindi da UMI si ottiene UMIU, o in generale xI → xIU, dove x è una stringa qualunque (anche nulla).
(b) Se una stringa comincia con M, si può raddoppiare la parte dopo la M; quindi da MUMMI si ottiene MUMMIUMMI, o in generale Mx → Mxx.
(c) Se una stringa contiene tre I consecutive, le si possono sostituire con una U; quindi da MIIIM si ottiene MUM, o in generale xIIIy → xUy.
(d) Se una stringa contiene due U consecutive, le si possono togliere; quindi da UUIMI si ottiene IMI, o in generale xUUy → xy.

All'inizio avete solo a disposizione la stringa MI. Quale successione di operazioni è necessaria per arrivare a ottenere la stringa MU?

   

   

Problema presentato da Douglas Hofstadter in Gödel, Escher, Bach.