Talk:MU puzzle

Okay. I am but a simple academic who has only been pestered with mathematics for ten years, so it is obviously my fault dat this lemma might as well have been written in Arabic. Now, the puzzle is explained in Math rather than English. Maybe someone who has read the book can elaborate, or translate? (Brrrtje 19:48, 24 December 2006 (UTC))

Explanation: Consider the number of "I"s in a string before / after the application of one of the rules. With rules 1 and 4, the number is not affected. With rule 2, the number is doubled. With rule 3, the number decreases by three.

Note that if the number of "I"s is a multiple of 3 before the application of one of those rules, it will be a multiple of 3 afterwards. Similarly, if the number is not a multiple of 3 before using a rule, it will not be a multiple of 3 afterwards.

That is, _whether or not the string has a multiple of three "I"s is not changed by any sequence of rules_, or _no sequence of rules can change a string with a nonmultiple of 3 "I"s to a string with a multiple of 3 "I"s, or vice versa_. Since "MI" has 1 "I" (not a multiple), and "MU" has 0 "I"s (a multiple), it is impossible to perform the change. Ralphmerridew 02:08, 17 January 2007 (UTC)

a and b

$i\cdot 2^{a}-3b$

a is the number production rule 2 is used and b is the number production rule 3 is used, right? --Abdull 11:25, 4 December 2007 (UTC)

Only if rule 2 is never used after rule 3. I think the article needs a better explanation. -- 195.4.179.51 (talk) 20:22, 14 November 2008 (UTC)

Proposed change

I would like to change the desription of the puzzle in a way that is more readable by common people. I was thinking about something like this:

Let's suppose to have the symbols M, I, and U which can be combined to produce strings of symbols or "words". The MU puzzle asks to start with a the "axiomatic" word MI and transform it into the word MU using in each step only the folowing transformation rules:

1. At the end of any string ending in I, you can add a U, such as changing MI to MIU.
2. You can double any string after the M (that is, change Mx, to Mxx), such as changing MIU to MIUIU.
3. You can replace any III with a U, such as changing MUIIIU to MUUU.
4. You can remove any UU, such as changing MUUU to MU.

Using these 4 rules is it possible to change MI into MU in a finite number of steps?

We can write the production rules in a more schematic way. Suppose x and y behave as variables (standing for a string of symbols) then the production rules can be written as:

1. xI → xIU
2. Mx → Mxx
3. xIIIy → xUy
4. xUUy → xy,

can we obtain the word MU, using these rules?

I'm not a native english speaker so I ask you if you for corrections. What do you think?--Pokipsy76 (talk) 12:04, 26 March 2008 (UTC)

Rule 1 incorrect?

I dont think this rule is entirely correct

1. xI → xIU

It seems to imply that you can replace any I with IU; it doesn't restrict it to I's that occur at the end of the string.

209.163.184.2 (talk) 19:42, 13 August 2015 (UTC)

According to Hofstadter (Godel, Escher, Bach, Ch.1), the rules are supposed to be applied to the whole string only, not to arbitrary substrings. Therefore, the I has to be the very last character of the string in order to be replacable by rule 1. This should be made more explicit in the article. - Jochen Burghardt (talk) 09:55, 17 August 2015 (UTC)

What's with the M?

I know we're not about to change the letters or logic of the puzzle, but I don't see what "M" has to do with it. It just seems like a spurious extra detail that the string begins (and always will begin) with an "M". 65.0.200.59 (talk) 06:40, 29 October 2010 (UTC)

The presence of the M is not relevant to the puzzle itself--it is relevant only to the "everything is interconnected" world of Hofstadter's book "Godel, Escher, Bach," in that it lets him tie the name of the puzzle to the Japanese word Mu and thence to Zen, and talk about the "M-Mode" versus the "I-Mode" of how humans think about formal systems. Hofstadter is a lot like Aristotle--he takes you on a hell of a wild ride through seemingly every sphere of human thought, but then he wants to draw these sweeping conclusions that never really quite add up. "Strange loops," indeed.--158.111.143.22 (talk) 14:48, 5 January 2011 (UTC)

Also, there's one point in the book that talks about Gödel-numbering, and observes that if "M", "I" and "U" are replaced by "3", "1" and "0", every derivation (chain of strings derived by the rules) can be transformed into a single number, and the question "Given two positive integers x, y, is x a valid derivation of y?" can be interpreted entirely arithmetically. The function of M/3 here is to act as a separator for successive strings. 2.25.141.152 (talk) 14:37, 8 July 2011 (UTC)

It's also a more accessible invariant: it's easy to see that no rule can remove or add the M. This paves the way for the subtler invariant. --82.40.89.223 (talk) 04:18, 16 October 2020 (UTC)