El rompecabezas MU es un rompecabezas establecido 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 en sí. MIU es un ejemplo de un sistema Post canónico y puede reformularse como un sistema de reescritura de cadenas .
El rompecabezas
Suponga que existen los símbolos M
, I
y U
que se pueden combinar para producir cadenas de símbolos. El acertijo MU le pide a uno que comience con la cadena "axiomática" MI
y la transforme en la cadena MU
usando en cada paso una de las siguientes reglas de transformación: [1] [2]
Nr. Regla formal [nota 1] Explicación informal Ejemplo 1. X I
→ X IU
Agregue un U
al final de cualquier cadena que termine enI
MI
a MIU
2. M
X→ M
xxDobla la cuerda después del M
MIU
a MIUIU
3. x III
y→ x U
yReemplace cualquiera III
con unU
MUIIIU
a MUUU
4. x UU
y→ xy Quitar cualquier UU
MUUU
a MU
Solución
El rompecabezas no se puede resolver: es imposible cambiar la cadena MI
en MU
aplicando repetidamente las reglas dadas. En otras palabras, MU no es un teorema del sistema formal MIU. Para probar esto, uno debe dar un paso "fuera" del propio sistema formal.
Para probar afirmaciones como esta, a menudo es beneficioso buscar una invariante ; es decir, alguna cantidad o propiedad que no cambia al aplicar las reglas.
En este caso, uno puede mirar el número total de I
en una cadena. Solo la segunda y tercera reglas cambian este número. En particular, la regla dos lo duplicará mientras que la regla tres lo reducirá en 3. Ahora, la propiedad invariante es que el número de I
s no es divisible por 3:
- Al principio, el número de
I
s 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 de un número que no es divisible por 3 tampoco lo hace 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 la frecuencia con la que se aplica la segunda regla.
Un criterio decidible de derivabilidad
De manera más general, una cadena x dada arbitrariamente puede derivarse de MI
las cuatro reglas anteriores si, y solo si , x respeta las tres propiedades siguientes:
- x solo se compone de uno
M
y cualquier número deI
yU
, - x comienza con
M
, y - el número de
I
en x no es divisible por 3.
Prueba
Sólo si: No hay ninguna regla mueve el M
, cambia el número de M
, o introduce cualquier carácter de M
, I
, U
. Por lo tanto, toda x derivada de MI
respeta 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 ser el número de I
y U
en x , respectivamente, y sea. Por propiedad 3, el número no puede ser divisible por 3, por lo tanto, tampoco puede ser. Es decir,. Dejar tal que y . [nota 2] Comenzando por el axioma MI
, aplicando la segunda reglalos tiempos se obtienen MIII
... I
con I
. Desde es divisible por 3, por construcción de , aplicando la tercera regla los tiempos obtendrán MIII
... IU
... U
, exactamente con I
, seguido de algún número de U
. El U
recuento siempre se puede hacer de manera uniforme, aplicando la primera regla una vez, si es necesario. Aplicando la cuarta regla con suficiente frecuencia, todos U
pueden eliminarse, obteniendo así MIII
... I
con I
. Al aplicar la tercera regla para reducir los tripletes de I
a U
en los lugares correctos, se obtendrá x . En total, x se ha derivado de MI
.
Ejemplo
Para ilustrar la construcción en la parte If de la demostración, la cadena MIIUII
, que respeta las propiedades 1 a 3, conduce a, , , ; por lo tanto, se puede derivar de la siguiente manera:
MI
MII
MIIII
MIIIIIIII
MIIIIIIIIIIIIIIII
MIIIIIIIUIIIIII
MIIIIIIIUUIII
MIIIIIIIUUIIIU
MIIIIIIIUUUU
MIIIIIIIUU
MIIIIIII
MIIUII
.
Aritmetización
El capítulo XIX de Gödel, Escher, Bach da un mapeo del sistema MIU a la aritmética, como sigue. En primer lugar, cada MIU-secuencia puede ser traducido 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. (Por ejemplo, la cadena MIUIU
se asignaría a 31010).
En segundo lugar, el axioma único del sistema MIU, a saber, la cuerda MI
, se convierte en el número 31.
En tercer lugar, las cuatro reglas formales dadas anteriormente se convierten en las siguientes:
Nr. Regla formal [nota 3] Ejemplo 1. k × 10 + 1 → 10 × ( k × 10 + 1) 31 → 310 ( k = 3) 2. 3 × 10 m + n → 10 m × (3 × 10 m + n ) + n 310 → 31010 ( m = 2, n = 10) 3. k × 10 m + 3 + 111 × 10 m + n → k × 10 m + 1 + n 3111011 → 30011 ( k = 3, m = 3, n = 11) 4. k × 10 m + 2 + n → k × 10 m + n 30011 → 311 ( k = 3, m = 2, n = 11)
( NB: La traducción de la primera regla anterior difiere superficialmente de la del libro, donde está escrita como "[i] si 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 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 regla. 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 utilizando símbolos. La cadena MI es similar a un solo 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 es entonces análoga 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 se refiere a nada: es simplemente un juego que involucra 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, nunca deduciendo 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 del sistema" y comienza a razonar sobre el sistema, en lugar de trabajar dentro de él. Al final, uno se da cuenta de que el sistema de alguna manera se trata de 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 parecer imposible.
La incapacidad del sistema MIU para expresar o deducir hechos sobre sí mismo, como la incapacidad para derivar MU, es una consecuencia de su simplicidad. Sin embargo, los 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ática Discreta con aplicaciones , Susanna S. Epp utiliza el rompecabezas MU para introducir el concepto de las definiciones recursivas , y comienza el capítulo correspondiente con una cita de GEB . [3]
Ver también
Notas
- ^ Aquí, x y y son variables, de pie para cadenas de símbolos. Una regla puede aplicarse solo a toda la cadena, no a una subcadena arbitraria.
- ^ Tal siempre existe, ya que las potencias de 2 se evalúan alternativamente a 1 y 2, módulo 3.
- ^ Aquí, k y m representan números naturales arbitrarios, y n es cualquier número natural más pequeño 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 puede aplicarse solo a un número MIU completo, no a una parte arbitraria de su representación decimal.
Referencias
- ^ Justin Curry / Curran Kelleher (2007). Gödel, Escher, Bach: una odisea del espacio mental. MIT OpenCourseWare .
- ^ Hofstadter, Douglas R. (1999) [1979], Gödel, Escher, Bach: An Eternal Golden Braid , Basic Books, ISBN 0-465-02656-7 Aquí: Capítulo I.
- ^ Matemáticas discretas con aplicaciones , tercera edición, Brooks / Cole, 2004. Capítulo 8.4, "Definiciones generales recursivas", 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.
- "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.