sábado, 21 de mayo de 2016

El acertijo MU

Un sistema formal, es un sistema con el que se pretende capturar y abstraer la esencia de determinadas características del mundo real, con un modelo conceptual expresado en un determinado lenguaje formal.
Para definir un sistema formal, se requieren cuatro elementos:

Un alfabeto de símbolos.
Un conjunto de cadenas bien formadas llamadas axiomas.
Un conjunto finito de reglas de deducción.
Un conjunto de cadenas finitas bien formadas llamadas teoremas.

El acertijo MU, representa un pequeño sistema formal. Este acertijo fue planteado por Douglas Hofstadter en 1979 en su libro Godel, Escher, Bach. An Eternal Golden Braid 

Carácter MU en japonés
Carácter MU en japonés. Wikipedia.


Planteamiento del acertijo MU


El objetivo del acertijo es producir la cadena MU dentro del sistema formal MIU, el nombre del sistema se toma del hecho de que emplea tres letras: M, I, U. Esto significa que las cadenas del sistema MIU estarán formadas exclusivamente por esas tres letras.

El sistema MIU parte de una cadena inicial, la cadena MI, es decir, MI será  el único axioma del sistema.

Las cadenas deberán conseguirse aplicando las reglas que se muestran a continuación:

• Regla 1: Si se tiene una cadena cuya última letra sea I, se le puede agregar una U al final. Es decir, si xI es un teorema, también lo es xIU. En este caso x representa cualquier cadena del sistema.

• Regla 2: Si Mx es un teorema,  Mxx también es un teorema.

Por ejemplo:
Si se tiene MIU se puede obtener MIUIU
Si se tiene MU se puede obtener MUU
Si se tiene MUIU se puede obtener MUIUUIU

• Regla 3: Si en uno de los teoremas aparece la secuencia III puede generarse  una nueva cadena sustituyendo III por U.

Por ejemplo:
Si se tiene la cadena MIIIMU se puede elaborar MUMU 
Si se tiene la cadena MIIII se puede elaborar MUI o también MIU. 
Dado IIMII la aplicación de esta regla no permite ninguna transformación. (Las tres III deben ser consecutivas)
Si se tiene MIII se puede elaborar MU.
Bajo ninguna circunstancia se podrá emplear la regla en sentido contrario (las reglas son unidireccionales) como en el ejemplo siguiente:
Dado MU obtener MIII (esto es un error).

• Regla 4: Si aparece UU en el interior de un teorema está permitida su eliminación.
Dado MUUU se puede obtener MU
Dado MUUUIII se puede obtener MUIII

Desarrollo del acertijo

Un intento sistemático para resolver este acertijo consiste en generar un árbol a partir del primer axioma de tal forma que no se escape ningún teorema a nuestra lista de teoremas válidos del sistema.

A partir del axioma MI y aplicando las reglas, sólo se pueden obtener dos teoremas válidos:
1. MIU
2. MII

La primera cadena se obtiene al aplicar la regla 1, y la segunda después de aplicar la regla 2. No se pueden aplicar las reglas 3 y 4 a MI.

Después de este paso se tiene que ver que cadenas se pueden generar a partir de MIU y cuáles a partir de MII. De MIU solo es posible generar MIUIU, sin embargo, de MII se pueden generar MIIU y MIIII. Si continuamos aplicando este proceso el número de teoremas válidos de cada teorema inicial o padre puede ser muy grande.

Implementación automática del sistema

Si no queremos cansarnos sacando teoremas y teoremas podemos diseñar un pequeño programa de ordenador que nos calcule todos los teoremas posibles del sistema, por ejemplo en VB.NET las cuatro reglas especificadas quedarían del siguiente modo:

 'Regla1 Si MxI añade U quedando MxIU
    Public Function Regla1(ByVal Cadena As String) As String
        Cadena = Cadena & "U"
        Return Cadena
    End Function

    'Regla 2 Añade x a Mx devolviendo Mxx
    Public Function Regla2(ByVal Cadena As String) As String
        Cadena = Cadena + Mid(Cadena, 2)
        Return Cadena
    End Function

    'Regla 3 sustituye III por U en cualquier lugar de la cadena
    Public Function Regla3(ByVal Cadena As String) As String
        Cadena = Replace(Cadena, "III", "U")
        Return Cadena
    End Function

    'Regla 4 elimina UU en cualquier lugar de la cadena
    Public Function Regla4(ByVal Cadena As String) As String
        Cadena = Replace(Cadena, "UU", "")
        Return Cadena

    End Function

Podemos diseñar un pequeño formulario tal que al pulsar el botón comenzar calcule todos los teoremas válidos y los muestre en la ventana.

formulario para el acertijo MU


La implementación del motor principal del programa que se ejecutará al pulsar el botón de comienzo es esta:

Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
        Dim Cadena, CadenaSal As String

        Cadena = "MI" 'axioma
        ListView1.Items.Add("MI")
        While CadenaSal <> "MU"
            GeneraMU(arrCadenas(i))
            ListView1.Items.Add(arrCadenas(i))
            i = i + 1
        End While
End Sub

Ojo, porque si no se han dado cuenta ya, el programa entrará en un bucle infinito, para evitarlo, podemos limitar las iteraciones a 100 salidas o las que deseemos. Más adelante veremos que esto es una implementación muy descafeinada del “aburrimiento”.

Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
        Dim i As Integer

        ReDim Preserve arrCadenas(0)
        arrCadenas(0) = "MI" 'axioma
        ListView1.Items.Add("MI")
        While i < 100  'implementación del "aburrimiento". Lo lógico sería preguntar while ArrCadenas(i) <> "MU" 
            GeneraMU(arrCadenas(i))
            ListView1.Items.Add(arrCadenas(i))
            i = i + 1
        End While
    End Sub


Si queremos que recorra concienzudamente todas y cada una de las posibilidades deberemos implementar un programa que siga este diagrama de flujo:

Diagrama de flujo del acertijo MU
Esto es una tentativa de cómo podría ser la función principal GeneraMU que se ajusta al diagrama de arriba.


'toma una cadena de entrada y la pasa por las 4 reglas con el objetivo de saber cual de ellas es aplicable
    Public Sub GeneraMU(ByVal Cadena As String)

        Dim cad As String
        Dim longitud As Integer
        Dim CadenaSal1, CadenaSal2, CadenaSal3, CadenaSal4 As String

        longitud = Len(Cadena)
        'toma último caracter de la cadena
        cad = Mid(Cadena, longitud)

        If cad = "I" Then
            CadenaSal1 = Regla1(Cadena)
            BuscaMU(Cadena, CadenaSal1)
        End If
        CadenaSal2 = Regla2(Cadena)
        BuscaMU(Cadena, CadenaSal2)
        If InStr(Cadena, "III", CompareMethod.Text) = True Then
            'puede aplicarse regla 3
            CadenaSal3 = Regla3(Cadena)
            BuscaMU(Cadena, CadenaSal3)
        End If
        If InStr(Cadena, "UU", CompareMethod.Text) = True Then
            'Puede aplicar regla 4
            CadenaSal4 = Regla4(Cadena)
            BuscaMU(Cadena, CadenaSal4)
        End If
    End Sub

 'Compara la cadena obtenida con la cadena de entrada y busca si es MU, si no es, la añade al array para usarla posteriormente 
    'como parámetro de entrada
    Private Sub BuscaMU(ByVal Cadena As String, ByVal CadenaSal As String)
        If CadenaSal <> Cadena Then  'si la cadena es igual es que no hubo transformación por la regla y no se tiene en cuenta.
            If CadenaSal <> "MU" Then

                mIndice = mIndice + 1  'actualiza el indice del array
                ReDim Preserve arrCadenas(mIndice)
                arrCadenas(mIndice) = CadenaSal
            Else
                MsgBox("¡¡¡MU ENCONTRADO!!!", CadenaSal)
            End If
        End If
    End Sub

En este caso como vemos, puede darse el caso que por cada entrada se generen hasta 4 salidas por lo que nos vemos obligados a almacenar dichas salidas en una memoria de tipo FIFO (First Imput First Output) y alimentar el programa con las salidas que vaya obteniendo. Esto es lo que hacemos con el array arrCadenas. Si no encuentra MU rápidamente la memoria FIFO puede hacerse enormemente grande.

Para completar el programa hay que definir el array y el índice visibles para todo el programa.

Dim arrCadenas() As String

Dim mIndice As Integer

Discusión


El 100 del bucle del programa se ha añadido por que el programa nunca llegará a MU y por tanto nunca se detendrá. (También podemos hacer que cuando la memoria FIFO alcance cierto valor se pare el programa).
¿Cómo sabemos que MU no es deducible? Se puede demostrar mediante un sencillo razonamiento matemático. Después de varias decenas de intentos comienzan a hacerse evidentes ciertas “normas” matemáticas subyacentes:

La ‘M’ es irrelevante. Nunca se quita ni se pone ni se modifica. (Es como un 0 a la izquierda) 
El número de ‘I’ solo lo podemos aumentar multiplicándolas por 2 (regla 2). No importa su distribución con las ‘U’.
El número de ‘I’ solo lo podemos disminuir por múltiplos de 3 (regla 3), por tanto, para eliminar todas las ‘I’ tenemos que conseguir que aparezca un múltiplo de 3 ‘I’.
Un número que no es divisible por 3, sigue sin serlo después de multiplicarlo por 2.
Un número que no es divisible por 3, sigue sin serlo después de restarle un múltiplo de 3.
1 no es divisible por 3.

Por tanto nunca podremos obtener MU a partir de MI, pero lo que realmente nos interesa es la manera en que llegamos a la conclusión de que no es deducible.
Cuando llevamos un tiempo intentando resolver el acertijo nos damos cuenta de que no es sencillo deducir MU. En vez de seguir deduciendo expresiones (bien al azar o bien siguiendo estrategias como la mostrada en el diagrama de flujo) es probable que nos “aburramos” y empecemos a plantearnos qué tipo de expresiones se pueden deducir del juego.
Como acabamos de ver, al analizar con detenimiento las reglas llegamos a la conclusión de que MU no es deducible. Y es aquí donde está lo importante:

Mientras estamos deduciendo cadenas de inferencia (como lo haría el programa de ordenador) estamos dentro del sistema formal.

Cuando analizamos qué cadenas son deducibles y cuales no, nos hemos situado fuera del sistema. Es como si hubiéramos dado un salto hacia fuera: ya no estamos simplemente deduciendo cadenas, sino contemplando el acertijo globalmente, analizando sus características y limitaciones.

El objetivo de Hofstadter


Hofstadter ideó este acertijo con el objetivo de hacer una pequeña introducción a los sistemas formales, pero ya de paso lo aprovechó como ejemplo bastante consistente de lo que diferencia a los seres humanos de las máquinas y nos da una idea del tipo de problemas que debería ser capaz de resolver una máquina para considerarla tan inteligente como los seres humanos. Aquí pues la cuestión radica en obtener máquinas que sean capaces de “saltar” fuera del sistema y decidir si el problema que se le ha propuesto es finalizable o no (Esto nos lleva al famoso problema de la detención de Turing). 

Un ordenador puede jugar dentro del sistema igual que lo haríamos nosotros (incluso más rápidamente). Sin embargo, ¿puede la máquina situarse fuera del sistema? Podría estar indefinidamente calculando cadenas del juego. Su cálculo no tendría fin, puesto que es imposible deducir MU. Pero no puede situarse fuera del sistema porque para ello debería ser consciente de sus propios cálculos. Una máquina puede calcular rápidamente, pero no ser consciente de sí misma.

Como hemos visto más arriba, no sería muy difícil implementar el “aburrimiento” en el programa y decirle que si ha calculado n cadenas y no ha dado con la solución, abandone el sistema y salte “fuera de su sistema” a otra subrutina que en este caso concreto podría ser algo más compleja que la primera pero no mucho más. Pero ojo, porque esta solución lleva varios engaños implícitos:

En primer lugar el “aburrimiento” se me antoja como algo mucho más sutil que una simple cifra en un bucle pues el programa saldrá del bucle sin más, es decir sin plantearse nada mientras que nosotros saldremos del bucle por “aburrimiento” con la sospecha de que hay que utilizar otra estrategia para llegar a una solución satisfactoria. Por otra parte la orden de “saltar fuera del sistema” no sería más que la llamada a otra subrutina y que por supuesto está dentro del sistema del ordenador que lo ejecuta. Por tanto en realidad no está saltando fuera del sistema.

Pero en este caso, los defensores de la Inteligencia Artificial fuerte argumentan y con razón, que los seres humanos tampoco somos capaces de saltar fuera de nuestro sistema, sólo que este es mucho más complejo que el de un ordenador.
Otra cosa a tener en cuenta es que para este acertijo MU concreto, resulta relativamente fácil implementar una segunda subrutina que analice las reglas y dé la solución tal cual se ha planteado arriba. De este modo el programa, una vez “aburrido” saltaría a la segunda subrutina y lo resolvería. 

Pero la verdadera cuestión del asunto sería implementar esta estrategia para todo tipo de acertijos genéricos, es decir que el programa en cuestión tomara la decisión de cuando continuar dentro de las reglas o analizarlas para ver si existe o no la solución y fuese capaz de analizar las reglas independientemente de lo sencillas o complejas que fueran, esto hoy por hoy se me antoja extremadamente complicado.

Una última cuestión consistiría en si esto último propuesto es realizable siguiendo un algoritmo convencional (Turing demostró que no es posible) y utilizando hardware convencional o si habría que implementar algo más complejo con un hardware diferente (cuántico) tal cual argumenta Penrose.

Como Curiosidad, Hofstadter tomó el nombre del acertijo del carácter japonés MU que significa ninguno y da respuesta a muchos Koan


No hay comentarios:

Publicar un comentario