Гёдель, Эшер, Бах кітабындағы MU жұмбағы

Puzzle in Douglas Hofstadter's book "Gödel, Escher, Bach"
The MU puzzle is a puzzle stated by Douglas Hofstadter and found in Gödel, Escher, Bach involving a simple formal system called "MIU". Hofstadter's motivation is to contrast reasoning within a formal system (i. e., deriving theorems) against reasoning about the formal system itself. MIU is an example of a Post canonical system and can be reformulated as a string rewriting system.

Only if: No rule moves the , changes the number of , or introduces any character out of , , Therefore, every x derived from respects properties 1 and 2. As shown before, it also respects property 3. If: If x respects properties 1 to 3, let and be the number of and in x, respectively, and let By property 3, the number cannot be divisible by 3, hence, cannot be, either. That is, Let such that and Beginning from the axiom , applying the second rule times obtains with Since is divisible by 3, by construction of , applying the third rule times will obtain , with exactly , followed by some number of The count can always be made even, by applying the first rule once, if necessary. Applying the fourth rule sufficiently often, all can then be deleted, thus obtaining with Applying the third rule to reduce triplets of into a in the right spots will obtain x. Altogether, x has been derived from .

The MIU system illustrates several important concepts in logic by means of analogy. It can be interpreted as an analogy for a formal system — an encapsulation of mathematical and logical concepts using symbols. The MI string is akin to a single axiom, and the four transformation rules are akin to rules of inference. The MU string and the impossibility of its derivation is then analogous to a statement of mathematical logic which cannot be proven or disproven by the formal system. It also demonstrates the contrast between interpretation on the "syntactic" level of symbols and on the "semantic" level of meanings. On the syntactic level, there is no knowledge of the MU puzzle's insolubility. The system does not refer to anything: it is simply a game involving meaningless strings. Working within the system, an algorithm could successively generate every valid string of symbols in an attempt to generate MU, and though it would never succeed, it would search forever, never deducing that the quest was futile. For a human player, however, after a number of attempts, one soon begins to suspect that the puzzle may be impossible. One then "jumps out of the system" and starts to reason about the system, rather than working within it. Eventually, one realises that the system is in some way about divisibility by three. This is the "semantic" level of the system — a level of meaning that the system naturally attains. On this level, the MU puzzle can be seen to be impossible. The inability of the MIU system to express or deduce facts about itself, such as the inability to derive MU, is a consequence of its simplicity. However, more complex formal systems, such as systems of mathematical logic, may possess this ability. This is the key idea behind Godel's Incompleteness Theorem.

In her textbook, Discrete Mathematics with Applications, Susanna S. Epp uses the MU puzzle to introduce the concept of recursive definitions, and begins the relevant chapter with a quote from GEB.