rompecabezas MU

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

El rompecabezas MU es un rompecabezas planteado 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) con el razonamiento sobre el sistema formal mismo. MIU es un ejemplo de un sistema Post canónico y puede reformularse como un sistema de reescritura de cadenas .

El rompecabezas

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

Solución

El rompecabezas no se puede resolver: es imposible cambiar la cadena MIaplicando MUrepetidamente 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, suele ser beneficioso buscar una invariante ; es decir, alguna cantidad o propiedad que no cambia al aplicar las reglas.

En este caso, se puede observar el número total de Ien una cadena. Sólo la segunda y tercera reglas cambian este número. En particular, la regla dos lo duplicará mientras que la regla tres lo reducirá por 3. Ahora, 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 puede derivarse MImediante las cuatro reglas anteriores si, y solo si , x respeta las tres propiedades siguientes:

1. x solo está compuesto por uno My cualquier número de Iy U,
2. x comienza con My
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, sea 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. Eso es, . Deja tal eso y . ^{[nota 2]} Partiendo del axioma , aplicando la segunda regla multiplicada se obtiene ... con . Como es divisible por 3, por construcción de , aplicando la tercera regla de tiempos se obtendrá ... ... , con exactamente , seguido de algún número de . El conteo siempre se puede hacer parejo, aplicando la primera regla una vez, si es necesario. Aplicando la cuarta regla con suficiente frecuencia, se pueden eliminar todos, obteniendo así ... con . Al aplicar la tercera regla para reducir tripletes de 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. Primero, cada cadena MIU se puede traducir a un número entero asignando las letras M, Iy 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 cuerda MI, se convierte en el número 31.

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

( NB: La interpretación de la primera regla anterior difiere superficialmente de la del libro, donde está escrito como "[s]i hemos hecho 10 m  + 1, entonces podemos hacer 10 × (10 m  + 1)". Aquí, sin embargo, la variable m estaba reservada para uso en exponentes de 10 únicamente y, por lo tanto, fue reemplazada 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 la otra. tres reglas.)

Relación con la lógica

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

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 axioma único , y las cuatro reglas de transformación son similares a reglas de inferencia .

La cadena MU y la imposibilidad de su derivación es entonces análoga a una declaración de lógica matemática que no puede ser probada o refutada 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. A nivel sintáctico, no se conoce la insolubilidad del rompecabezas MU. El sistema no se refiere a nada: es simplemente un juego de cadenas sin sentido. 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 tendría éxito, buscaría para siempre, sin deducir nunca que la búsqueda era inútil. Sin embargo, para un jugador humano, después de varios intentos, pronto comienza a sospechar que el rompecabezas puede ser imposible. Entonces uno "salta fuera del sistema" y comienza a razonar sobre el sistema, en lugar de trabajar dentro de él. Con el tiempo, uno se da cuenta de que el sistema se trata de alguna manera de divisibilidad por tres. Éste es el nivel "semántico" del sistema: un nivel de significado que el sistema alcanza naturalmente. En este nivel, el rompecabezas MU puede parecer imposible.

La incapacidad del sistema MIU para expresar o deducir hechos sobre sí mismo, como la incapacidad de derivar MU, es consecuencia de su simplicidad. Sin embargo, sistemas formales más complejos, como los sistemas de lógica matemática, pueden poseer esta capacidad. Ésta 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 presentar el concepto de definiciones recursivas y comienza el capítulo correspondiente con una cita del GEB. ^[3]

Ver también

• Invariante (matemáticas)
• Gramática ilimitada

Notas

1. Aquí, xey son variables y representan cadenas de símbolos. Una regla sólo se puede aplicar a toda la cadena, no a una subcadena arbitraria.
2. Esto siempre existe, ya que las potencias de 2 se evalúan alternativamente como 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 hecho x podemos hacer y ". Como ilustra la columna Ejemplo, una regla sólo se puede aplicar 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 mental en el espacio. MIT OpenCourseWare .
2. Hofstadter, Douglas R. (1999) [1979], Gödel, Escher, Bach: An Eternal Golden Braid , Libros básicos, 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. 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.
• "Rompecabezas MU". 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.