MU puzzle: Difference between revisions

Source: Wikipedia, the free encyclopedia.
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Extended confirmed users
610 edits
repaired broken link to MU-Puzzle pdf
Extended confirmed users
23,283 edits
→‎The puzzle: deleted religious ref.s unrelated to the puzzle
Line 3: Line 3:
==The puzzle==
==The puzzle==
{{Quotation|Has the dog Buddha-nature? MU!|[[Zen Koan]]<ref>{{cite web| url=http://ocw.mit.edu/high-school/humanities-and-social-sciences/godel-escher-bach/lecture-notes/MITHFH_geb_v3_5.pdf | title=The MU–Puzzle | accessdate=31 March 2015}}
{{Quotation|Has the dog Buddha-nature? MU!|[[Zen Koan]]<ref>{{cite web| url=http://ocw.mit.edu/high-school/humanities-and-social-sciences/godel-escher-bach/lecture-notes/MITHFH_geb_v3_5.pdf | title=The MU–Puzzle | accessdate=31 March 2015}}
</ref>}}
</ref><ref>If the previous footnote is a [[dead link]]{{dead link|date=October 2014}}, -- as it seemed to be on Oct. 31, 2014! -- then this might help: {{cite web
| url = http://buddhism.about.com/od/chanandzenbuddhism/a/What-Is-Mu.htm
| title = What Is Mu? / The Barrier Gate of Zen
| author = O'Brien, Barbara (Buddhism Expert)
| accessdate = October 31, 2014
}}
</ref><ref>See also "Ch'an and Zen Buddhism" at http://buddhism.about.com/od/chanandzenbuddhism/</ref>||}}
Suppose there are the symbols <code>M</code>, <code>I</code>, and <code>U</code> which can be combined to produce strings of symbols called "words". The MU puzzle asks one to start with the "axiomatic" word <code>MI</code> and transform it into the word <code>MU</code> using in each step one of the following transformation rules:
Suppose there are the symbols <code>M</code>, <code>I</code>, and <code>U</code> which can be combined to produce strings of symbols called "words". The MU puzzle asks one to start with the "axiomatic" word <code>MI</code> and transform it into the word <code>MU</code> using in each step one of the following transformation rules:
# Add a <code>U</code> to the end of any string ending in <code>I</code>. For example: <code>MI</code> to <code>MIU</code>.
# Add a <code>U</code> to the end of any string ending in <code>I</code>. For example: <code>MI</code> to <code>MIU</code>.

Revision as of 21:51, 31 March 2015

The MU puzzle is a puzzle stated by

string rewriting system
.

The puzzle

Has the dog Buddha-nature? MU!

— 
Zen Koan[1]

Suppose there are the symbols M, I, and U which can be combined to produce strings of symbols called "words". The MU puzzle asks one to start with the "axiomatic" word MI and transform it into the word MU using in each step one of the following transformation rules:

  1. Add a U to the end of any string ending in I. For example: MI to MIU.
  2. Double the string after the M (that is, change Mx, to Mxx). 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.

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

The production rules can be written in a more schematic way. Suppose x and y behave as variables (standing for strings of symbols). Then the production rules can be written as:

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

Is it possible to obtain the word MU using these rules? [2][3]

Solution

The puzzle's solution is no. It is impossible to change the string MI into MU by repeatedly applying the given rules.

In order to prove assertions like this, it is often beneficial to look for an invariant, that is some quantity or property that doesn't change while applying the rules.

In this case, one can look at the total number of I in a string. Only the second and third rules change this number. In particular, rule two will double it while rule three will reduce it by 3. Now, the invariant property is that the number of I is not

divisible
by 3:

  • In the beginning, the number of Is is 1 which is not divisible by 3.
  • Doubling a number that is not divisible by 3 does not make it divisible by 3.
  • Subtracting 3 from a number that is not divisible by 3 does not make it divisible by 3 either.

Thus, the goal of MU with zero I cannot be achieved because 0 is divisible by 3.

In the language of modular arithmetic, the number of I obeys the congruence

where counts how often the second rule is applied.

Relationship to provability

The result that MU cannot be obtained with these rules demonstrates the notion of independence in mathematical logic. The MIU system can be viewed as a formal logic in which a string is considered provable if it can be derived by application of the rules starting from MI. In this interpretation, the question is phrased as "Is MU provable in the MIU logic?".

Finding an invariant of the inference rules is a common method for establishing independence results.

See also

References

  1. ^ "The MU–Puzzle" (PDF). Retrieved 31 March 2015.
  2. ^ Justin Curry / Curran Kelleher (2007). Gödel, Escher, Bach: A Mental Space Odyssey. MIT OpenCourseWare.
  3. ISBN 0-465-02656-7
    Here: Chapter I.
Retrieved from "https://en.wikipedia.org/w/index.php?title=MU_puzzle&oldid=654404082"