Generalizaciones

Como comenté ayer, Torsten se graduó de la maestría con una tesis titulada Decomposition of Weighted Multi-operator Tree Automata. Aparte de ser una de las pocas pláticas técnicas que realmente he entendido en mi vida, la presentación de este trabajo me trajo unas ideas sobre las generalizaciones, que quiero compartir.
Por favor, no se espanten con los nombres, que los detalles de qué son o para qué sirven no son importantes para el punto que quiero mostrar.
La teoría de autómatas surge para reconocer un tipo de lenguajes. En este caso, un lenguaje es un conjunto de palabras. Pero, ¿por qué quedarse ahí? Hay aplicaciones para las que conjuntos de palabras no son interesantes, sino que se quieren distinguir conjuntos de árboles. Para esto, la teoría de autómatas fue generalizada, dando lugar a los autómatas de árboles.
En este caso, para un árbol dado, el autómata contesta "si" o "no"; o para los computólogos, 0 o 1. Pero, ¿es esto suficiente? Digamos que no solo queremos saber si el árbol tiene cierta propiedad, sino además asociar un costo al mismo; así surgen los autómatas de árboles con pesos. En ellos, dado un árbol, el autómata regresa un número, perteneciente a una estructura algebráica previamente definida.
Ahora generalicemos un poco más. En lugar de simplemente aceptar un árbol con un costo, creamos un mecanismo, que actúa de la misma forma que los autómatas, que dado un árbol da como resultado un conjunto de árboles junto con unos pesos. Estos son transformadores de árboles con pesos.
Un punto importante aquí, es que los transformadores pueden hacer estrictamente más cosas que los autómatas.
Pero, regresando por un momento a los autómatas, ¿qué pasa si en lugar de números usamos como pesos operadores? Bueno, pues eso es lo que en la tesis de Torsten se llama autómata multi-operador de árboles con pesos. Ahora, durante su plática, mientras estaba mostrando resultados de descomposición, Torsten muestra, casi sin notarlo, que un transformador de árboles es un caso particular de uno de estos autómatas. ¿A alguien le suena una campanita aquí?
Tenemos que los autómatas con pesos usando operadores son más generales que los transformadores que son estrictamente más generales que los autómatas con pesos. ¡Aquí hay un problema!
Obviamente, no existía tal problema, sino que yo estaba dejando de lado un hecho muy importante: el conjunto de operadores no es un semianillo, y por tanto, los autómatas multi-operador son también estrictamente más generales que los autómatas de pesos originales. Es decir que, lo que parecía un caso particular (usar la estructura de los operadores cuando puedes usar cualquier otra) era realmente una generalización.
La pregunta viene ahora: ¿se puede generalizar más?; ¿hay algo más que quisiéramos hacer con autómatas que no se pueda hacer ya? Bueno, pues la respuesta es: si la Tesis de Church es correcta, entonces no.
Torsten demostró que sus autómatas son capaces de simular una máquina de Turing. Y esto me regresa al punto que quería tomar: se comienza con la máquina de Turing, y se hace un caso particular para resolver un problemita: los autómatas. Poco a poco se va generalizando, agregando propiedades deseables y, de pronto, estamos de regreso en la máquina de Turing.
Yo siempre he sido adepto de las generalizaciones (vean mi tesis de maestría, o mis reportes técnicos como prueba de ello), pero cuando las generalizaciones se van de las manos, ¿sirven de algo?