Trencaclosques MU

El Trencaclosques MU és un trencaclosques formulat per Douglas Hofstadter i es troba en el llibre Gödel, Escher, Bach. És un exemple d'un sistema canònic i pot ser reformulada com un sistema de reescriptura de cadenes de caràcters.

El trencaclosques

Suposem que els símbols M , I , i U es poden combinar per produir cadenes de símbols anomenats "paraules". El trencaclosques MU demana que començant per la paraula MI , que és un "axioma", s'arribi a la paraula MU utilitzant en cada pas una de les regles de transformació següents:

1. Afegir un U al final de qualsevol cadena que acaba en I . Per exemple: MI per MIU .
2. Doblar qualsevol cadena després de la M (és a dir, canviar Mx per Mxx ). Per exemple: MIU per MIUIU .
3. Substituir qualsevol cadena III per una U . Per exemple: MUIIIU per MUUU .
4. Eliminar la cadena UU. Per exemple: MUUU per MU .

És possible transformar MI en MU usant aquestes quatre regles i en un nombre finit de passos?

Les normes de producció poden ser rescrites en una forma més esquemàtica. Suposem x i i es comporten com les variables (de peu per a cadenes de símbols). A continuació, la regles de producció del trencaclosques MU es pot escriure com:

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

És possible obtenir la paraula MU amb aquestes regles?

Solució

La solució del trencaclosques és que no, és impossible transformar la cadena MI en MU .

Per provar les afirmacions d'aquest tipus, sovint és beneficiós per buscar invariants, és a dir, una certa quantitat o propietat que no canvia, mentre que l'aplicació de les normes.

En aquest cas, un pot mirar el nombre total de I en una cadena. Només les regles segona i tercera modificar aquesta xifra. En particular, la regla dels dos serà el doble, mentre que regla de tres va a reduir en un 3. Ara, la propietat invariant és que el nombre de I no és divisible per 3:

• Al principi, el nombre de em s és 1, que no és divisible per 3.
• Duplicar un nombre que no és divisible per 3 no significa que sigui divisible per 3.
• Restar 3 d'un nombre que no és divisible per 3 no significa que sigui divisible per 3 tampoc.

Per tant, l'objectiu de MU amb zero I no es pot aconseguir, perquè és 0 divisible per 3.

En el llenguatge de l'aritmètica modular, el nombre $n$ de I obeeix a la congruència

$n\equiv 2^{a}\not \equiv 0{\pmod {3}}.\,$

on $a$ compte la freqüència amb la segona regla s'aplica.

Relació amb la demostrabilitat

El resultat que MU no pot obtenir amb aquestes regles demostra la noció d'independència en la lògica matemàtica. El sistema MIU es pot veure com una lògica formal en què es considera una cadena demostrable si es pot derivar mitjançant l'aplicació de les regles a partir de MI. En aquesta interpretació, la pregunta es formula com "És MU demostrable en la lògica MIU?".

Trobar un invariant de les regles d'inferència és un mètode comú per a l'establiment dels resultats de la independència.

Referències

• Hofstadter, Douglas R. (1999), Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books, ISBN 0-465-02656-7, (anglès).

Vegeu també

• invariant