6.1. MU Puzzle.   

The following puzzle is part of the excellent book:

We shall use this to investigate Formal Systems
Our formal system :

1.      Uses only 3 letters      M,I,U

       i.e.  all strings of MIU formal system are comprised of

            these three letters.

      e.g      MU   MIU   UIM   UIIIIMIU

2.      Starts with MI.

3.      Has these rules:

      Rule (1)

       If you possess a string whose last character is I, you

      may add a U at the end.


                              (1)

                           MI -->  MIU


      Rule (2)

       If you possess Mx, you may create Mxx


            (2)                (2)

         MI -->  MII       MIU -->  MIUIU


      Rule (3)

       If III occurs in one of your strings in your collection,

       you may make a new string with U in place of III


              (3)               (3)

      UMIIIMU -->  UMUMU   MIII -->  MU


      Rule (4)

       If UU occurs in one of your strings, you can delete it


                              (4)

                          UUU -->  U

                    (4)       (3)     (4)

            MUUUIII --> MUIII --> MUU --> M