El rompecabezas MU es un rompecabezas formulado por Douglas Hofstadter y encontrado en Gödel, Escher, Bach que involucra un sistema formal simple llamado "MIU".
La motivación de Hofstadter es contrastar el razonamiento dentro de un sistema formal (es decir, derivar teoremas) contra el razonamiento sobre el sistema formal en sí.
El rompecabezas MU le pide a uno que comience con la cadena "axiomática" MI y la transformes en la cadena MU usando en cada paso una de las siguientes reglas de transformación: Aquí:caracter I.
El rompecabezas no se puede resolver: es imposible cambiar la cadena MI a MU aplicando repetidamente las reglas dadas.
En otras palabras, MU no es un teorema del sistema formal MIU.
Para probar esto, uno debe salir "fuera" del sistema formal en sí.
Para probar afirmaciones como esta, a menudo es beneficioso buscar una invariante ; es decir, alguna propiedad que no cambia mientras se aplican las reglas.
En este caso, se puede ver el número total de I en una cadena.
Solo las reglas segunda y tercera cambian este número.
En particular, la regla dos lo duplicará mientras que la regla tres lo reducirá en 3.Ahora, la propiedad invariable es que el número de I's no es divisible por 3: Por lo tanto, el objetivo de MU con cero I no se puede lograr porque 0 es divisible por 3.
En el lenguaje de la aritmética modular , el número n de I obedece a la congruencia donde a cuenta con qué frecuencia se aplica la segunda regla.
En términos más generales, las cuatro reglas anteriores pueden derivar una cadena x dada de manera arbitraria si, y solo si , x respeta las tres propiedades siguientes: Sólo si: No hay ninguna regla que mueva la M, cambie el número de M, o introduzca cualquier carácter de M,I,U.
Por lo tanto, cada x deriva de MI respecto a las propiedades 1 y 2.
[nota 2] Comenzando desde el axioma MI, aplicando la segunda regla
Aplicando la cuarta regla con la suficiente frecuencia, todo U se puede eliminar, obteniendo así MIII...I with
I.Aplicando la tercera regla para reducir las triples I a U en los lugares correctos obtendrá x. x se ha derivado de MI.
; por tanto, puede derivarse de la siguiente manera: El Capítulo XIX de Gödel, Escher, Bach ofrece un plano del sistema MIU a la aritmética, de la siguiente manera: En primer lugar, cada secuencia MIU se puede traducir a un número entero mediante la asignación de las letras M, I, y U a los números 3,1 y 0, respectivamente.
En segundo lugar, el axioma único del sistema MIU, es decir, la cadena MI, se convierte en el número 31 Tercero, las cuatro reglas dadas arriba se convierten en las siguientes (NB: La representación de las reglas anteriores concretamente la primera, difiere superficialmente de la del libro,donde está escrita como "[i]f hemos hecho 10m + 1, entonces podemos hacer 10 × (10m + 1)".
Aquí, sin embargo, la variable m estaba reservada para su uso solamente en exponentes de 10, y por lo tanto, se reemplazó por k en la primera regla.