MU puzzle -- from Gödel Escher Bach by Douglas R. Hofstadter -- https://en.wikipedia.org/wiki/MU_puzzle

mu_puzzle.rb

# MU puzzle
# From Gödel Escher Bach by Douglas R. Hofstadter
# https://en.wikipedia.org/wiki/MU_puzzle

# Nr.  Formal rule   Informal explanation                            Example
# -----------------------------------------------------------------------------------
# 1.   xI → xIU      Add a U to the end of any string ending in I    MI  to  MIU
# 2.   Mx → Mxx      Double the string after the M                   MIU to  MIUIU
# 3.   xIIIy → xUy   Replace any III with a U                        MUIIIU  to  MUUU
# 4.   xUUy → xy     Remove any UU                                   MUUU  to  MU


def rule1(str)
  str[-1] == 'I' ?  str + 'U' : str
end

def rule2(str) # assumes our strings start with 'M'
  str == 'M' ? 'M' : 'M' + str[1..-1]*2
end

def rule3(str)
  positions = str.enum_for(:scan, /III/).map { Regexp.last_match.begin(0) }
  if positions.empty?
    str
  else
    pos = positions.sample
    str[0..(pos-1)] + str[(pos+3)..-1]
  end
end

def rule4(str)
  str[-2..-1] == 'UU' ? str[0..-3] : str
end

set = ['MI']
LIMIT = 100

while set.size < LIMIT
  element = set.sample
  result = case rand(4) + 1
           when 1
             rule1(element)
           when 2
             rule2(element)
           when 3
             rule3(element)
           when 4
             rule4(element)
           end
  set << result unless set.include?(result)
end

puts set.sort

__END__

Example output

MI
MII
MIIII
MIIIII
MIIIIIII
MIIIIIIII
MIIIIIIIIII
MIIIIIIIIIIIII
MIIIIIIIIIIIIIIII
MIIIIIIIIIIIIIIIIIIIIIIIIII
MIIIIIIIIIIIIIIIIIIIIIIIIIIIII
MIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
MIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
MIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
MIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIU
MIIIIIIIIIIIIIIIIIIIIIIIIIIU
MIIIIIIIIIIIIIIIIU
MIIIIIIIIIIIIIU
MIIIIIIIIIIIIIUIIIIIIIIIIIIIU
MIIIIIIIIIIIIIUIIIIIIIIIIIIIUIIIIIIIIIIIIIUIIIIIIIIIIIIIU
MIIIIIIIIIIIIIUIIIIIIIIIIIIIUIIIIIIIIIIIIIUIIIIIIIIIIIIIUIIIIIIIIIIIIIUIIIIIIIIIIIIIUIIIIIIIIIIIIIUIIIIIIIIIIIIIU
MIIIIIIIIIIU
MIIIIIIIIIIUIIIIIIIIIIU
MIIIIIIIIIIUIIIIIIIIIIUIIIIIIIIIIUIIIIIIIIIIU
MIIIIIIIIIIUIIIIIIIIIIUIIIIIIIUIIIIIIIIIIU
MIIIIIIIIIIUIIIIIIIIIIUIIIIIIIUIIIIIIIIIIUIIIIIIIIIIUIIIIIIIIIIUIIIIIIIUIIIIIIIIIIU
MIIIIIIIIU
MIIIIIIIIUIIIIIIIIU
MIIIIIIIIUIIIIIIIIUIIIIIIIIUIIIIIIIIU
MIIIIIIIIUIIIIIIIIUIIIIIIIIUIIIIIIIIUIIIIIIIIUIIIIIIIIUIIIIIIIIUIIIIIIIIU
MIIIIIIIU
MIIIIIIIUIIIIIIIIIIUIIIIIIIIIIUIIIIIIIIIIU
MIIIIIIIUIIIIIIIIIIUIIIIIIIIIIUIIIIIIIIIIUIIIIIIIUIIIIIIIIIIUIIIIIIIIIIUIIIIIIIIIIU
MIIIIIIIUIIIIIIIIIIUIIIIIIIIIIUIIIIIIIIIIUIIIIIIIUIIIIIIIIIIUIIIIIIIIIIUIIIIIIIIIIUIIIIIIIUIIIIIIIIIIUIIIIIIIIIIUIIIIIIIIIIUIIIIIIIUIIIIIIIIIIUIIIIIIIIIIUIIIIIIIIIIU
MIIIIIU
MIIIIIUIIIIIIIIUIIIIIIIIUIIIIIIIIUIIIIIIIIUIIIIIIIIUIIIIIIIIUIIIIIIIIU
MIIIIU
MIIIIUIIIIU
MIIIIUIIIIUIIIIUIIIIU
MIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIU
MIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIU
MIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIU
MIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIU
MIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIU
MIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIU
MIIIIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIU
MIIIIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIU
MIIIIUIIIIUIUIIIIU
MIIIIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIU
MIIIIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIU
MIIIIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIU
MIIIIUIIIIUIUIIIIUIUIIIIUIUIIIIU
MIIIIUIIIIUIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIUIIIIU
MIIIIUIIIIUIUIU
MIIIIUIIIIUIUIUIIIIUIIIIUIUIU
MIIIIUIU
MIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIU
MIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIU
MIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIU
MIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIU
MIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIU
MIIIIUIUIIIIUIU
MIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIU
MIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIIIIUIIIIUIU
MIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIU
MIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIUIIIIUIUIIIIUIUIIIIUIIIIUIIIIUIU
MIIIIUIUIIIIUIUIIIIUIUIIIIUIU
MIIIIUIUIUIIIIU
MIIIIUIUIUIIIIUIIIIUIUIUIIIIU
MIIIIUIUIUIU
MIIIIUIUIUIUIIIIUIUIUIU
MIIIIUIUIUIUIIIIUIUIUIUIIIIUIUIUIUIIIIUIUIUIU
MIIIIUIUIUIUIIIIUIUIUIUIIIIUIUIUIUIIIIUIUIUIUIIIIUIUIUIUIIIIUIUIUIUIIIIUIUIUIUIIIIUIUIUIU
MIIIIUIUIUIUIUIUIUIU
MIIU
MIIUIIU
MIIUIIUIIUIIU
MIIUIIUIIUIIUIIUIIUIIUIIU
MIU
MIUIIIIU
MIUIIIIUIIIIUIIIIU
MIUIIIIUIIIIUIIIIUIUIIIIUIIIIUIIIIU
MIUIIIIUIUIIIIU
MIUIIIIUIUIIIIUIUIIIIUIUIIIIU
MIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIU
MIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIUIUIIIIU
MIUIIIIUIUIIIIUIUIUIUIIIIU
MIUIIIIUIUIIIIUIUIUIUIIIIUIUIIIIUIUIIIIUIUIUIUIIIIU
MIUIIIIUIUIIIIUIUIUIUIIIIUIUIUIUIIIIUIUIUIUIIIIU
MIUIIIIUIUIIIIUIUIUIUIIIIUIUIUIUIIIIUIUIUIUIIIIUIUIIIIUIUIIIIUIUIUIUIIIIUIUIUIUIIIIUIUIUIUIIIIU
MIUIIIIUIUIU
MIUIIIIUIUIUIUIIIIUIUIIIIU
MIUIIIIUIUIUIUIIIIUIUIIIIUIUIIIIUIUIUIUIIIIUIUIIIIU
MIUIU
MIUIUIUIIIIU
MIUIUIUIIIIUIUIUIUIIIIU
MIUIUIUIU
MIUIUIUIUIUIUIUIIIIU
MIUIUIUIUIUIUIUIU
MIUIUIUIUIUIUIUIUIUIUIUIUIUIUIUIU