0 98765432 and 1
MI MII rule 2 MIIII rule 2 MIIIIIIII rule 2 MIIIIIU rule 3 MIIUU rule 3 MIIUUI rule 1 MIII rule 4 MU rule 3Many thanks to several solvers who pointed out that this problem is very similar to one posed in Douglas Hofstadter's Godel, Escher, Bach. In that book, rule 1 was changed to read "You can add 'U' at the end of a string ending with 'I'". In this case, the problem is not solvable. A few people sent proofs of that, but I'll leave it unproven here for others to think about.