Can you turn MI into MU using the following rules?
logic/mu.puzzle New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Can you turn MI into MU using the following rules? We are dealing with a formal system based on the following axiom: MI In this system, which contains strings of variable length formed only by M, U and I, there are three inference rules: 1) You can add an 'I' at the end of a string ending with 'U' (example: MUIU ====> MUIUI) 2) If you have a string Mx you can write also the string Mxx (example: MUI ====> MUIUI or MUIIU ====> MUIIUUIIU) 3) Whenever you find a 'III' you can turn it into 'U' (example: MUIIIUI ====> MUUUI). WARNING! The opposite is forbidden! (You can't turn a 'U' into 'III'.) Are you able to turn the base axiom MI into the string (theorem) MU following the 3 rules? Are you able to decide if it is possible to arrive at a given string without trying (only looking at the string)? -- Michele Borioli <actarus@digibank.it>, after D. R. Hofstadter, "Godel, Escher, Bach: an Eternal Golden Braid" [Editor: "Godel, Hescer, Bach" in the original]
Show solution
I guess I would try to work backwards. The only string you can get MU from is MIII. There is no string that will give you MIII. So, I would say no. Am I right, or? -- Rick Banghart <banghar4@pilot.msu.edu> [ Editor: the rules as posted differ from Hofstadter's MIU system, in which rule 1 adds a U to a string ending in I (MI ==> MIU) and a fourth rule deletes UU. Banghart's backward argument applies to the rules as posted here. The second question was not answered in the collected postings. ]