Build a MU puzzle solver The MU puzzle is a puzzle in which you find out whether you can turn MI into MU given the following operations:


If your string ends in I, you may add a U to the end. (e.g. MI -&gt; MIU)
If your string begins with M, you may append a copy of the part after M to the string.
(e.g. MII -&gt; MIIII)
If your string contains three consecutive I's, you may change them into a U.
(e.g. MIII -&gt; MU)
If your string contains two consecutive U's, you may delete them. (e.g. MUUU -&gt; MU).


Your task is to build a program that determines whether this is doable for any start and finish strings.

Your program will take two strings as input. Each string will consist of the following:


one M.
a string of up to twenty-nine I's and U's.


Your program will then return true (or your programming language's representation thereof/YPLRT) if the second string is reachable from the first string, and false (or YPLRT) if it is not.

Example inputs and outputs:

MI  MII
true

MI  MU
false

MIIIIU  MI
true


The shortest code in any language to do this wins.
SWI Prolog, 183 characters

m(A,A).
m([i],[i,u]).
m([i,i,i|T],B):-m([u|T],B).
m([u,u|T],B):-m(T,B).
n([m|A],[m|B]):-(m(A,B);append(A,A,X),m(X,B)).
n(A,B):-m(A,B).
s(A,B):-atom_chars(A,X),atom_chars(B,Y),n(X,Y).


How about some Prolog, (since nobody has answered in 6 months).
To run, just use "s(mi,mu)."  The code breaks up atoms into chars, then searches for the solution.