Rompecabezas MU

Puzzle in Douglas Hofstadter's book "Gödel, Escher, Bach"

El rompecabezas MU es un rompecabezas planteado por Douglas Hofstadter y que se encuentra en Gödel, Escher y 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) con el razonamiento sobre el sistema formal en sí. MIU es un ejemplo de un sistema postcanónico y puede reformularse como un sistema de reescritura de cadenas .

El rompecabezas

Supongamos que existen los símbolos M, I, y Uque pueden combinarse para producir cadenas de símbolos. El rompecabezas MU pide que se comience con la cadena "axiomática" MIy se la transforme en la cadena MUutilizando en cada paso una de las siguientes reglas de transformación: ^{[1] [2]}

Solución

El problema no se puede resolver: es imposible transformar la cadena MIen MUmediante la aplicación repetida de las reglas dadas. En otras palabras, MU no es un teorema del sistema formal MIU. Para demostrarlo, hay que salir "fuera" del propio sistema formal.

Para probar afirmaciones como ésta, a menudo es beneficioso buscar un invariante , es decir, alguna cantidad o propiedad que no cambie al aplicar las reglas.

En este caso, se puede observar el número total de Ien una cadena. Solo la segunda y la tercera reglas cambian este número. En particular, la regla dos lo duplicará, mientras que la regla tres lo reducirá en 3. Ahora bien, la propiedad invariante es que el número de Ino es divisible por 3:

• Al principio, el número de Is es 1, que no es divisible por 3.
• Duplicar un número que no es divisible por 3 no lo hace divisible por 3.
• Restar 3 a un número que no es divisible por 3 tampoco lo hace divisible por 3.

Por lo tanto, el objetivo de MUcero Ino se puede lograr porque 0 es divisible por 3.

En el lenguaje de la aritmética modular , el número n de Iobedece a la congruencia

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

donde a cuenta la frecuencia con la que se aplica la segunda regla.

Un criterio decidible para la derivabilidad

De manera más general, una cadena x dada arbitrariamente se puede derivar MImediante las cuatro reglas anteriores si, y solo si , x respeta las tres propiedades siguientes:

1. x solo se compone de uno My cualquier número de Iy U,
2. x comienza con M, y
3. el número de Ien x no es divisible por 3.

Prueba

Sólo si: Ninguna regla mueve M, cambia el número de M, o introduce algún carácter fuera de M, I, U. Por lo tanto, cada x derivada de MIrespeta las propiedades 1 y 2. Como se mostró antes, también respeta la propiedad 3.

Si: Si x respeta las propiedades 1 a 3, sean y el número de y en x , respectivamente, y sea . Por la propiedad 3, el número no puede ser divisible por 3, por lo tanto, tampoco puede serlo. Es decir, . Sea tal que y . ^{[nota 2]} Partiendo del axioma , aplicando la segunda regla veces se obtiene ... con . Como es divisible por 3, por construcción de , aplicando la tercera regla veces se obtendrá ... ... , con exactamente , seguido de algún número de . El recuento siempre se puede hacer par, aplicando la primera regla una vez, si es necesario. Aplicando la cuarta regla con la suficiente frecuencia, se pueden eliminar todos, obteniendo así ... con . Aplicando la tercera regla para reducir los tripletes de en a en los lugares correctos se obtendrá x . En total, x se ha derivado de . ${\displaystyle N_{I}}$ ${\displaystyle N_{U}}$IU ${\displaystyle N=N_{I}+3N_{U}}$ ${\displaystyle N_{I}}$ ${\displaystyle N}$ ${\displaystyle N\equiv 1{\text{ or }}N\equiv 2{\pmod {3}}}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle 2^{n}>N}$ ${\displaystyle 2^{n}\equiv N{\pmod {3}}}$MI ${\displaystyle n}$MIIII ${\displaystyle 2^{n}}$ I ${\displaystyle 2^{n}-N}$ ${\displaystyle n}$ ${\displaystyle {\frac {2^{n}-N}{3}}}$MIIIIUU ${\displaystyle N}$ IUUUMIIII ${\displaystyle N_{I}+3N_{U}}$ IIUMI

Ejemplo

Para ilustrar la construcción en la parte If de la prueba, la cadena MIIUII, que respeta las propiedades 1 a 3, conduce a , , , ; por lo tanto, se puede derivar de la siguiente manera: ${\displaystyle N_{I}=4}$ ${\displaystyle N_{U}=1}$ ${\displaystyle N=7}$ ${\displaystyle n=4}$

MI 2→ MII 2→ MIIII 2→ MIIIIIIII 2→ MIIIIIIIIIIIIIIII 3→ MIIIIIIIUIIIIII 3→ MIIIIIIIUUIII 1→ MIIIIIIIUUIIIU 3→ MIIIIIIIUUUU 4→ MIIIIIIIUU 4→ MIIIIIII 3→ MIIUII.

Aritmetización

El capítulo XIX de Gödel, Escher, Bach ofrece una aplicación del sistema MIU a la aritmética, de la siguiente manera. En primer lugar, cada cadena MIU se puede traducir a un entero asignando las letras M, I, y Ua los números 3, 1 y 0, respectivamente. (Por ejemplo, la cadena MIUIUse asignaría a 31010).

En segundo lugar, el único axioma del sistema MIU, es decir la cadena MI, se convierte en el número 31.

En tercer lugar, las cuatro reglas formales expuestas anteriormente se convierten en las siguientes:

( NB: La interpretación de la primera regla anterior difiere superficialmente de la del libro, donde está escrita como "[s]i hemos hecho 10 m  + 1, entonces podemos hacer 10 × (10 m  + 1)". Aquí, sin embargo, la variable m se reservó para su uso en exponentes de 10 solamente, y por lo tanto se reemplazó por k en la primera regla. Además, en esta interpretación, la disposición de los factores en esta regla se hizo consistente con la de las otras tres reglas).

Relación con la lógica

El sistema MIU ilustra varios conceptos importantes en lógica por medio de analogía.

Puede interpretarse como una analogía de un sistema formal : una encapsulación de conceptos matemáticos y lógicos mediante símbolos. La cadena MI es similar a un único axioma y las cuatro reglas de transformación son similares a las reglas de inferencia .

La cadena MU y la imposibilidad de su derivación son entonces análogas a un enunciado de lógica matemática que no puede ser probado o refutado por el sistema formal.

También demuestra el contraste entre la interpretación en el nivel "sintáctico" de los símbolos y en el nivel "semántico" de los significados. En el nivel sintáctico, no hay conocimiento de la insolubilidad del rompecabezas MU. El sistema no hace referencia a nada: es simplemente un juego que involucra cadenas sin significado. Trabajando dentro del sistema, un algoritmo podría generar sucesivamente cada cadena válida de símbolos en un intento de generar MU, y aunque nunca lo lograría, buscaría eternamente, sin deducir nunca que la búsqueda fue inútil. Para un jugador humano, sin embargo, después de varios intentos, uno pronto comienza a sospechar que el rompecabezas puede ser imposible. Uno entonces "salta fuera del sistema" y comienza a razonar sobre el sistema, en lugar de trabajar dentro de él. Finalmente, uno se da cuenta de que el sistema de alguna manera trata sobre la divisibilidad por tres. Este es el nivel "semántico" del sistema - un nivel de significado que el sistema alcanza naturalmente. En este nivel, el rompecabezas MU puede verse como imposible.

La incapacidad del sistema MIU para expresar o deducir hechos sobre sí mismo, como la incapacidad de derivar MU, es una consecuencia de su simplicidad. Sin embargo, sistemas formales más complejos, como los sistemas de lógica matemática, pueden poseer esta capacidad. Esta es la idea clave detrás del Teorema de Incompletitud de Gödel .

Usos pedagógicos

En su libro de texto, Matemáticas discretas con aplicaciones , Susanna S. Epp utiliza el rompecabezas MU para introducir el concepto de definiciones recursivas y comienza el capítulo relevante con una cita de GEB. ^[3]

Véase también

• Invariante (matemáticas)
• Gramática sin restricciones

Notas

1. Aquí, x e y son variables que representan cadenas de símbolos. Una regla puede aplicarse únicamente a la cadena completa, no a una subcadena arbitraria.
2. Tal cosa siempre existe, ya que las potencias de 2 evalúan alternativamente 1 y 2, módulo 3. ${\displaystyle n}$
3. Aquí, k y m representan números naturales arbitrarios, y n es cualquier número natural menor que 10 ^m . Cada regla de la forma " x  →  y " debe leerse como "si hemos creado x, podemos crear y ". Como lo ilustra la columna de Ejemplos, una regla puede aplicarse solo a un número MIU completo, no a una parte arbitraria de su representación decimal.

Referencias

1. Justin Curry / Curran Kelleher (2007). Gödel, Escher, Bach: Una odisea del espacio mental. MIT OpenCourseWare .
2. Hofstadter, Douglas R. (1999) [1979], Gödel, Escher, Bach: Una eterna trenza dorada , Basic Books, ISBN 0-465-02656-7Aquí: Capítulo I.
3. Matemáticas discretas con aplicaciones , tercera edición, Brooks/Cole, 2004. Capítulo 8.4, "Definiciones recursivas generales", pág. 501.

Enlaces externos

• «Sistema MIU de Hofstadter». Archivado desde el original el 4 de marzo de 2016. Consultado el 29 de noviembre de 2016 .Una interfaz en línea para producir derivaciones en el Sistema MIU.
• «MU Puzzle». Archivado desde el original el 14 de mayo de 2018. Consultado el 13 de mayo de 2018 .Una implementación de JavaScript en línea del sistema de producción MIU.