My very first attempt. (Note, Masem, your first example should be "MUUUU" => "M".)

sub mu {
# 43*5 + 15 = 230 chars
# 123456789_123456789_123456789_123456789_123
  my($f,$t,$s)=@_;return 0if$f eq$t;@_=$f;for
  my$i(1..$s){@_=map{(my$A=$_)=~s/I$/IU/;(my$
  B=$_)=~s/^M(.*)/M$1$1/;(my$C=$_)=~s/III/U/;
  (my$D=$_)=~s/UU//;grep{$_ ne$t||return$i}$A
  ,$B,$C,$D}@_;}0
}
[download]

japhy -- Perl and Regex Hacker