La complejidad matemática que impide verificar el software correctamente

Fuentes: The mathematical complexity that prevents correct software verification

El artículo explora por qué la escritura de software correcto es inherentemente difícil, argumentando que la matemática por sí sola no puede resolver esta limitación. El autor, basándose en resultados de la teoría de la computabilidad y la complejidad, demuestra que los programas y la comprensión completa necesaria para garantizar la corrección están en conflicto fundamental. Se analiza cómo los teoremas de incompletitud de Gödel y el teorema de la parada de Church y Turing desmontan la idea de que existe un algoritmo universal capaz de decidir la verdad de cualquier afirmación formal o la terminación de cualquier programa. El texto detalla cómo el teorema de la parada implica directamente la imposibilidad de resolver problemas de alcanzabilidad y de propiedades de funciones parciales, como establece el teorema de Rice. Además, se introduce el teorema del 'Busy Beaver' para cuantificar la complejidad de analizar programas, mostrando que la dificultad de verificación no es un fallo de herramientas, sino una consecuencia de las leyes naturales de la computación. El autor concluye que, aunque las herramientas pueden asistir, el coste de la corrección es significativo y evitable solo mediante la aceptación de estas limitaciones teóricas.