jueves, 2 de enero de 2014

Una explicación divertida del problema de la parada

El otro día estaba haciendo una toma de requisitos para un cliente, una empresa de seguridad en informática. Mi cliente dispone un producto de seguridad muy interesante: tu le envías el binario de tu programa, y él te dice si el programa es seguro o presenta vulnerabilidades. La plataforma es muy modular, y tiene una serie de plugins, programas independientes, que realizan los análisis. Así, el plugin1 realiza un tipo de análisis sobre el programa, el plugin2 realiza otro tipo de análisis diferente, etc. El problema es que ciertos plugins pueden requerir mucho tiempo de cálculo. Y lo que es peor, a veces puede incluso que no terminen nunca. Así, si un análisis concreto lleva una semana ejecutándose, no sabemos si es porque está tardando mucho, o simplemente porque se ha atascado y nunca terminará. Y si tenemos en cuenta que mi cliente cobra por hora de cálculo, son muchos los usuarios de su plataforma que se quejan, y que preferirían tener la seguridad a priori de que el análisis terminará en algún momento.

Así que mi cliente lo que quería es que escribiese un nuevo módulo, llamado Parada(A, P), que dado un plugin de análisis A y un programa P, devolviera CIERTO si el análisis iba a terminar, o FALSO si no (no era necesario hacer ningún tipo de estimación del tiempo que iba a requerir el análisis, soló saber si iba a terminar). El problema es que el cliente me pedia también que el modulo Parada() fuese lo suficientemente genérico, no sólo para poder trabajar con los plugins de análisis existentes acualmente, sino también sobre cualquier otro plugin que incorporase en el futuro, sin que fuera necesario modificar el códogo de Parada(), lo cual es, simplemente, imposible. Ya que nos encontramos con el famoso Problema de la Parada.

Supongamos que conseguimos implementar el módulo Parada(A, P) genérico que nos piden. Parada recibiría dos argumentos: el análisis o plugin a aplicar A, y el programa P a analizar (recordemos que los análisis se aplican sobre los programas, es decir A(P)). Y escribimos un nuevo plugin de análisis llamado C que intentará forzar la contradicción. A diferencia de los demás plugins, C recibe como argumento uno de los otros plugins, y no un programa, y simplemente lo que hace es llamar a Parada(A, A), es decir, lo que C se plantea es si un plugin concreto se parará si analizara la seguridad de su propio binario A(A). Pero C es muy travieso, y si Parada(A, A) retorna FALSO, C retorna CIERTO, y si Parada(A, A) es CIERTO, C se mete en un bucle infinito y no para nunca.

Ahora nos preguntamos ¿cual sería el resultado de C aplicado sobre sí mismo C(C)? ¿Se parará? Supongamos que C(C) no se para nunca, en este caso Parada(C, C) retorna FALSO, y C debería retornar CIERTO, es decir, sí que se para. Pero si C(C) se para, tendremos que Parada(C, C) es CIERTO, pero en este caso C se metería en un bucle infinito y no debería parar. Esta contradicción de que C(C) se para sí y sólo si si no se para nos lleva a la conclusión de que nuestra hipótesis, la existencia de la función Para(A, P) genérica, es falsa.

Al final mi cliente le contrató el proyecto a un programador chino que le prometió que se lo hacía por 500 dólares.

No hay comentarios:

Publicar un comentario