Validez y completud

Nota:quería titular este texto correctud y completud pero, al no encontrar ninguna referencia a que la palabra correctud es correcta [;)], decidí cambiarlo por el actual.
Permítanme comenzar con unas definiciones. Un problema de decisión es aquel donde las únicas respuestas posibles, para cualquier entrada, son SI o NO. Un problema de decisión es decidible si existe un algoritmo que da la respuesta a cualquier entrada en tiempo finito. Es semi-decidible si existe un algoritmo que, siempre que la respuesta es positiva, contesta acertadamente en tiempo finito, pero que puede no contestar en caso de respuestas negativas.
Por ejemplo, decidir si un algoritmo concluye sus operaciones dada una entrada para el mismo, es semidecidible pues simplemente podemos correr el algoritmo sobre esa entrada y, si termina, contestar SI, pero si no termina, no podremos contestar nada.
Ahora, un mismo problema se puede resolver con distintos algoritmos. Un algoritmo es correcto si siempre que contesta SI lo hace acertadamente, y es completo si siempre que la respuesta es SI este la contesta adecuadamente. Obviamente, el algoritmo ideal sería aquel que es a la vez correcto y completo, pues eso significa que jamás comete errores (cuando contesta).
Un ejemplo trivial de un algoritmo completo es el que siempre, ante cualquier entrada, contesta SI. Sobre algoritmos correctos hay dos ejemplos triviales: uno, el que siempre contesta NO, y otro el que siempre se cicla y no da nunca una solución. [Recuerdo haber leído un ejemplo similar hace poco en Planeta Linux, pero no puedo encontrar la referencia adecuada].
En algunos casos, en especial cuando se quiere implementar algo eficientemente, no se puede tener un algoritmo correcto y completo, pues este demoraría demasiado tiempo. En esos casos hay que hacer una elección: completo e incorrecto, o correcto e incompleto. Históricamente, esta cuestión se ha resuelto fácilmente y con poca controversia: que sea correcto, aunque resulte incompleto.
Hace poco, ante una implementación de Lógica Descriptiva Difusa, un computólogo expresó su duda al respecto entre sus colegas. Muchos de ellos se mostraron incluso sorprendidos ante la pregunta, y contestaron como lo dije antes: "es mejor que sea correcto". Yo por mi parte, me puse a buscar problemas y me resultó dificil encontrar casos en que prefiriera que fuera correcto sobre la completud; de hecho, los únicos tales casos que hallé pertenecían a lógica: satisfacibilidad, subsuma, inclusión. Todos los problemas de "la vida real" que pude pensar era mejor que fueran completos a correctos. Por supuesto, el mismo algoritmo cambia de completo a correcto, y viceversa, si se resuelve el dual del problema inicial, pero los humanos tenemos una forma de expresar esos problemas (generalmente en forma negativa, como: ¿la planta nuclear va a estallar?) que hace que los problemas duales suenen muy irreales (¿es la planta nuclear segura?).
Para entender esto, volví la mirada a la estadística. Ahí, cuando se hacen pruebas de hipótesis, siempre (o generalmente) se elije como hipótesis inicial aquella que está del lado seguro, pues de acuerdo con estas pruebas, sólo vas a rechazar tu hipótesis si tienes evidencia suficiente para ello.
Así, siempre voy a asumir que la planta va a estallar, que el acusado es culpable (aunque esto contradiga las iniciativas judiciales de muchos países), que el león va a atacar, y un muy largo etcétera. Bajo esta perspectiva, si asumimos que nuestro problema de decisión está relacionado con una hipótesis inicial de una prueba de hipótesis como esta, en el caso general preferiríamos errar contestando SI cuando era NO, pues no había evidencia suficiente para refutar la hipótesis inicial, pero que siempre que la respuesta sea SI sea esa la respuesta. En otras palabras, a pesar de lo que digan los lógicos y computólogos, en general, y siempre y cuando el problema esté planteado en forma segura, es preferible un algoritmo completo sobre uno correcto.