Rompecabezas MU

Plantilla:Referencias 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í. 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 Plantilla:Code, Plantilla:Code, y Plantilla:Code que se pueden combinar para producir cadenas de símbolos. El rompecabezas MU le pide a uno que comience con la cadena "axiomática" Plantilla:Code y la transformes en la cadena Plantilla:Code usando en cada paso una de las siguientes reglas de transformación:

Aquí:caracter I.

Nr.	Regla formal			Explicación informal	Ejemplo
1.	xPlantilla:Code	→	xPlantilla:Code	Agregue la Plantilla:Code al final de cualquier cadena que termine en Plantilla:Code	Plantilla:Code	a	Plantilla:Code
2.	Plantilla:Codex	→	Plantilla:Codexx	Duplica la secuencia después de Plantilla:Code	Plantilla:Code	a	Plantilla:Code
3.	xPlantilla:Codey	→	xPlantilla:Codey	Reemplaza cualquier Plantilla:Code con una Plantilla:Code	Plantilla:Code	a	Plantilla:Code
4.	xPlantilla:Codey	→	xy	Elimina cualquier Plantilla:Code	Plantilla:Code	a	Plantilla:Code

Solución

El rompecabezas no se puede resolver: es imposible cambiar la cadena Plantilla:Code a Plantilla:Code 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 Plantilla:Code 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 Plantilla:Code's no es divisible por 3:

• Al principio, el número de Plantilla:Code'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 Plantilla:Code con cero Plantilla:Code no se puede lograr porque 0 es divisible por 3.

En el lenguaje de la aritmética modular , el número n de Plantilla:Code obedece a la congruencia

$n\equiv 2^a\equiv ̸0(\mathrm{mod}3).$

donde a cuenta con qué frecuencia se aplica la segunda regla.

Un criterio decidible para la derivabilidad

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:

1. x solo se compone de una Plantilla:Code y cualquier cantidad de Plantilla:Code y Plantilla:Code,
2. x comienza con Plantilla:Code, y
3. el número de Plantilla:Code en x no es divisible por 3.

Prueba

Sólo si: No hay ninguna regla que mueva la Plantilla:Code, cambie el número de Plantilla:Code, o introduzca cualquier carácter de Plantilla:Code,Plantilla:Code,Plantilla:Code. Por lo tanto, cada x deriva de Plantilla:Code respecto a las propiedades 1 y 2. Como se mostró anteriormente, también respeta la propiedad 3.

Si: Si x respeta las propiedades de la 1 a la 3,deja a $N_I$ y $N_U$ ser el número de Plantilla:Code y Plantilla:Code en x, respectivamente, y deja a $N=N_I+3N_U$.Por la propiedad 3, el número de $N_I$ no puede ser divisible por 3, por lo tanto, $N$ tampoco lo puede ser. Es decir, $N\equiv 1\text{ or }N\equiv 2(\mathrm{mod}3)$. $n\in \mathbb{N}$ such that $2^n>N$ and $2^n\equiv N(\mathrm{mod}3)$. Comenzando desde el axioma Plantilla:Code, aplicando la segunda regla $n$ veces, se obtiene Plantilla:Code...Plantilla:Code con $2^n$ Plantilla:Code.Ya que $2^n-N$ es divisible por 3, por la interpretación de $n$, aplicando la tercera regla $\frac{2^n-N}{3}$ se obtendrán Plantilla:Code...Plantilla:Code...Plantilla:Code, con exactamente $N$ Plantilla:Code, seguidos de algún número de Plantilla:Code. El recuento de Plantilla:Code siempre se puede hacer de manera uniforme, aplicando la primera regla si es necesario. Aplicando la cuarta regla con la suficiente frecuencia, todo Plantilla:Code se puede eliminar, obteniendo así Plantilla:Code...Plantilla:Code with $N_I+3N_U$ Plantilla:Code.Aplicando la tercera regla para reducir las triples Plantilla:Code a Plantilla:Code en los lugares correctos obtendrá x. x se ha derivado de Plantilla:Code.

Ejemplo

Para ilustrar la interpretación del Si, la cadena Plantilla:Code, que respeta las propiedades de la 1 a la 3, conduce a $N_I=4$, $N_U=1$, $N=7$, $n=4$; por tanto, puede derivarse de la siguiente manera:

Plantilla:Code $\stackrel{2}{\to }$ Plantilla:Code $\stackrel{2}{\to }$ Plantilla:Code $\stackrel{2}{\to }$ Plantilla:Code $\stackrel{2}{\to }$ Plantilla:Code $\stackrel{3}{\to }$ Plantilla:Code $\stackrel{3}{\to }$ Plantilla:Code $\stackrel{3}{\to }$ Plantilla:Code $\stackrel{1}{\to }$ Plantilla:Code $\stackrel{4}{\to }$ Plantilla:Code $\stackrel{4}{\to }$ Plantilla:Code $\stackrel{3}{\to }$ Plantilla:Code.

Aritmetización

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 Plantilla:Code, Plantilla:Code, y Plantilla:Code a los números 3,1 y 0, respectivamente. (Por ejemplo, la cadena Plantilla:Code se asignaría a 31010.) En segundo lugar, el axioma único del sistema MIU, es decir, la cadena Plantilla:Code, se convierte en el número 31 Tercero, las cuatro reglas dadas arriba se convierten en las siguientes

Nr.	Regla formal			Ejemplo
1.	k × 10 + 1	→	10 × (k × 10 + 1)	31	→	310	(k = 3)
2.	3 × 10m + n	→	10m × (3 × 10m + n) + n	310	→	31010	(m = 2, n = 10)
3.	k × 10m + 3 + 111 × 10m + n	→	k × 10m + 1 + n	3111011	→	30011	(k = 3, m = 3, n = 11)
4.	k × 10m + 2 + n	→	k × 10m + n	30011	→	311	(k = 3, m = 2, n = 11)

(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. Además, en esta representación, la disposición de los factores en esta regla se hizo consistente con la de las otras tres.)

Notas

Plantilla:Control de autoridades