En esta ocasión se hará una breve introdución a el acertijo $MU$; el cual representa un pequeño sistema formal. Este acertijo fue planteado por Hofstadter en 1979 en su libro Godel, Escher, Bach. An Eternal Golden Braid. El objetivo del acertijo propuesto por Hofstadter es producir la cadena MU (de ahí su nombre de Acertijo $MU$) dentro de un sistema formal conocido como el sistema $MIU$; el nombre del sistema se toma del hecho de que sólo emplea tres letras del alfabeto: $M$, $I$, $U$. Esto significa que las cadenas del sistema $MIU$ estarán formadas exclusivamente por esas tres letras. Para comenzar, el sistema $MIU$ parte de una cadena inicial, la cadena $MI$, es decir, $MI$ es el único axioma del sistema en cuestión. Las cadenas que sean producidas deberán conseguirse aplicando las reglas que se mencionan a continuación:
Regla 1. Si se tiene una cadena cuya última letra sea $I$, se le puede agregar una $U$ al final. Dicho en otras palabras, si $xI$ es un teorema, también lo es $xIU$. En este caso $x$ representa cualquier cadena arbitraria. Por ejemplo, si se tiene la cadena $MII$, entonces se puede obtener $MIIU$.
Regla 2. Suponga que $Mx$ es un teorema. En tal caso también $Mxx$ es un teorema. Por ejemplo, si se tiene la cadena $MIU$ se puede obtener la cadena $MIUIU$.
Regla 3. Si en una de las cadenas de la colección aparece la secuencia $III$, puede elaborarse una nueva cadena sustituyendo $III$ por $U$. Por ejemplo, si se tiene la cadena $UMIIIMU$ se puede elaborar $UMUMU$. Observe que las tres $III$ deben ser consecutivas.
Regla 4. Si aparece $UU$ en el interior de una de las cadenas, está permitida su eliminación. Por ejemplo, dado $MUUUIII$ se puede obtener $MUIII$.
Un primer intento para resolver este acertijo, es proceder a generar de manera manual algunas cadenas, como primer paso, se observa que a partir de el axioma $MI$ y aplicando las reglas, se pueden obtener las siguientes cadenas:
- $MIU$
- $MII$
La primera cadena se obtiene después de aplicar la regla 1, y la segunda, casualmente después de aplicar la regla 2. Es posible observar que no se pueden aplicar las reglas 3 y 4 a $MI$.
Después se tiene que ver qué cadenas se pueden generar de $MIU$ y cuáles de $MII$. De $MIU$ solo es posible generar $MIUIU$; sin embargo, de $MII$ se pueden generar $MIIU$ y $MIIII$. Si se sigue aplicando este proceso, se tendrá que buscar qué cadenas ahora se pueden formar de $MIUIU$, $MIIU$ y $MIII$, y seguir así secuencialmente hasta que en alguna de esas generaciones se encuentre la cadena $MU$.
De lo anterior se puede deducir que, esta búsqueda nos lleva a la generación de un árbol de teoremas como el mostrado en la Figura 1 , y como puede observarse, cada nodo puede tener una cantidad variada de hijos. En un principio, se podría pensar que cada nodo solo puede tener a lo máximo cuatro hijos, pero si se analiza detenidamente el problema, se puede llegar a la conclusión de que no necesariamente será así, por ejemplo, de la cadena $MIIIIIIIU$ aplicando solamente la regla 3 se pueden obtener las siguientes cadenas:
- $MUIIIIU$
- $MIUIIIU$
- $MIIUIIU$
- $MIIIUIU$
- $MIIIIUU$
De aquí se deduce que el número de hijos de cada nodo es variable y puede ser muy grande.
Para facilitar el ejercicio se puede hacer uso de algún lenguaje de programación como por ejemplo python y hacer una codificación de las reglas del sistema formal MIU, algo como lo que se muestra a continuación:
import reclass MIU: def __init__(self): # Definition of the primary chain. self.state = 'MI' def get_state(self): # Check the game status. return self.state def reset(self): # Restart the game state. self.state = 'MI' def rule_one(self): # Definition of rule one of the MIU system. if self.state[-1] == 'I': self.state = self.state + 'U' else: print('Can not use this rule...') return self.state def rule_two(self): # Definition of rule two of the MIU system. self.state = self.state + self.state[1:] return self.state def rule_three(self): # Definition of rule three of the MIU system. word = self.state result = re.finditer(r'(?=(III))', word) words = dict() for i, j in enumerate(result): slices = [word[:j.start(1)], word[j.end(1):]] chain = 'U'.join(slices) words[i] = chain print('Option {}:'.format(i), new_chain) if words.keys(): option = int(input('Choose an option: ')) self.state = words.get(option) else: print('Can not use this rule...') return self.state
def rule_four(self): # Definition of rule four of the MIU system. word = self.state result = re.finditer(r'(?=(UU))', word) words = dict() for i, j in enumerate(result): new_chain = word[:j.start(1)] + word[j.end(1):] words[i] = new_chain print('Option {}:'.format(i), new_chain) if words.keys(): option = int(input('Choose an option: ')) self.state = words.get(option) else: print('Can not use this rule...') return self.state Para utilizarlo, solo tienes que hacer una instancia del clase MIU:
game = MIU()
Luego sería usar cada uno de los métodos de la clase:
rule_one(),rule_two(),rule_three()yrule_four()para hacer uso de cualquiera de las reglas del sistema MIU.get_state()para ver el estado del juego.reset()para reiniciar el juego.
A continuación algunos ejemplos del uso:
game.rule_one()
game.rule_one()
game.rule_four()
game.rule_two()
game.rule_two()
game.reset()
game.get_state()
Finalmente, la pregunta es ¿Puedes encontrar MU? ¿Puedes construir un nuevo algoritmo que permita decidir si una cadena $x$ es demostrable dentro del sistema MIU? ¿Qué quiere decir que una cadena es demostrable en MIU? Espero seguir discutiendo estas preguntas en el futuro, por ahora les recomiendo que se pasen por la referencia que motivo esta entrada.
Referencias¶
- Hofstadter. 1979. Godel, Escher, Bach. An Eternal Golden Braid.
0 comments:
Publicar un comentario