jueves, marzo 29, 2007

Sinónimos y meta-lenguaje

Comúnmente consideramos que dos expresiones que son sinónimas, son completamente intercambiables; pero hay ocasiones en que esto no es así.
Sólo para poner todo claro, llamo sinónimo a aquello que cumple con la definición estricta de la palabra: dos expresiones son sinónimas si expresan exactamente el mismo concepto o idea. En ese sentido, siempre que estemos tratando problemas dentro del lenguaje del que estas expresiones forman parte, son intercambiables. Pero, ¿qué pasa con cuestiones del meta-lenguaje? Por ejemplo, si queremos saber si nos dedicamos a contar la longitud de la expresión, es posible que, aunque sean sinónimos, tengan distintas longitudes y por tanto, en ese contexto no son intercambiables.
Permítanme adentrarme a un lenguaje no-natural: las matemáticas; en particular, los conjuntos, en un contexto muy sencillo. Supongamos que nuestro lenguaje sólo permite expresiones de la forma "A en B" donde A y B son conjuntos, y el significado es que A es un subconjunto de B. Con este lenguaje sólo podemos expresar relaciones entre conjuntos, sin conocer sus elementos específicos. Consideren también otro escenario, donde permitimos también expresiones de la forma "A y B en C" significando que ambos A y B son subconjuntos de C. Es claro que "A y B en C" es sinónimo de "A en C" y "B en C". Dentro de nuestro lenguaje, ambas expresiones tienen el mismo significado.
Pero pasamos al problema dentro del meta-lenguaje. Queremos expresar de forma mínima las relaciones entre conjuntos: queremos dar la lista más pequeña que podamos encontrar para la que una relación de la forma "X contenido en Y" se de. Por ejemplo, si tenemos "A en B", "A en C", "B en C" y "C en D", una forma mínima de expresar que A es subconjunto de D es usando la segunda y la última expresión; no necesitamos las otras dos para obtener la relación.
Bueno, pues resulta que si permitimos las expresiones de la segunda forma, o sea "A y B en C", entonces, es fácil demostrar que no se puede encontrar estas expresiones mínimas en un tiempo razonable. Pero, ¿qué pasa si usamos sólo elementos de la forma "A en B"? Pues resulta que, aunque tengan la misma expresividad, aunque sean sinónimos perfectos e incluso ocupen el mismo espacio, es todavía un problema abierto si podemos expresar las relaciones de pertenencia de forma mínima usando un tiempo razonablemente corto.
Todo parece indicar, obviamente, que no es posible, pero hasta ahora no hay ninguna demostración que lo formalice.
Y este problema de meta-lenguaje está empezando a ser muy importante en estos últimos años.

3 comentarios:

Saffog Tochtli dijo...

Cómo demostrar que no se puede encontrar en un tiempo razonable. Os referis a un tiempo no polinomial, suponiendo que no dije una reverenda pasguatez.

Rafael Peñaloza dijo...

Mas o menos, goofas. El problema en este caso es que puede haber muchas expresiones minimas (exponencialmente muchas) y queremos escribirlas todas. Entonces, no podemos medir el tiempo con respecto a la instancia del problema, pero mas bien con respecto al numero de soluciones. Nos gustaria que si hay pocas soluciones, se tarde poco y que si hay muchas, se tarde mucho.
Pero aqui surge el problema: tienes que tambien poder decidir si ya tienes todas las soluciones, para asi detenerte.
Resulta que hacer esa decision, si ya tienes todas las soluciones, es un problema NP-duro. Esto quiere decir que, muy probablemente, no lo puedes hacer en tiempo polinomial.
No se si aclare tu duda, o te deje peor :P

Ing. Cardioide dijo...

Es lo mismo acaso estar durmiendo que estar dormido? jaja...

Bastante interesante!

Aloha! Saludos!

Lalo.