Build a MU puzzle solver

Question

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

1. If your string ends in I, you may add a U to the end. (e.g. MI -> MIU)

2. If your string begins with M, you may append a copy of the part after M to the string.
   (e.g. MII -> MIIII)

3. If your string contains three consecutive I's, you may change them into a U.
   (e.g. MIII -> MU)

4. If your string contains two consecutive U's, you may delete them. (e.g. MUUU -> 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.

Answer 1

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.