Proofs and Logic

We are going to play a game with strings of symbols.  This game was invented by a man named Douglas Hofstadter and found in his book Gödel, Escher, Bach. Here are the rules:

Suppose there are the symbols ‘M’, ‘I’, and ‘U’, which can be combined to produce strings of symbols called “words”, like MUI or MIUUU. The MIU game asks one to start with the “axiomatic” word MI and transform it using the following four rules, to obtain some “goal” word.  The rules state that you may:

1. Add a U to the end of any string ending in I. For example: MI to MIU, or MUUII to MUUIIU.
2. Double any string after the M (that is, change Mx, to Mxx, where ‘x’ represents any string of symbols). For example: MIU to MIUIU
3. Replace any III with a U. For example: MUIIIU to MUUU
4. Remove any UU. For example: MUUU to MU

WARM UP.  In each example, start with the axiomatic word MI and show, step-by-step, how to obtain the goal word (in each step, state which of the rules you used). These are just for practice (you do NOT need to submit your answers).

Example 1: Goal word MIU
Example 2: Goal word MIIU
Example 3: Goal word MIIUIIU
Example 4: Goal word MUUII
Example 5: Goal word MUUIIUIIU

Here is a sample solution to Example 2:
MI to MII (rule 1)
MII to MIIU (rule 2)

Assignment (due Tuesday, 10/29): Your assignment has three parts.

PART 1.  First, create an MIU puzzle — that is, make up a goal word, and post it in the comments.  Try to create a goal word that balances the following two requirements:

1. The goal word should not be too long – definitely not more than 10 letters (but the shorter the better).
2. The goal word should be tricky to reach, requiring at least four steps to reach (but the more the better).  See if you can find a clever use of the rules!

PART 2.  The second part of your assignment is to solve someone else’s puzzle.   Type your solution step-by-step, indicating which rule you used at each step.  Leave your comment as a response to their puzzle.  Only one solution per puzzle!

PART 3.  The third part of your assignment is to write a short paragraph (at least 3 sentences) responding to the following prompt.  Be sure to respond to each part:

Writing Prompt, MIU puzzle:  Did you enjoy this assignment? Why or why not?  Describe a connection between this assignment and our work in the class.  (If you don’t believe there is a connection, try to imagine why we are doing this).  Leave your response in the comments.