Todos los periódicos y la radio, en unoEscrito por IA a partir de Hacker News · Cómo se hace
Hacker News
Programación · pron.github.io
Por qué escribir software correcto es difícil
Ensayo de Ron Pressler (pron), versión ampliada de una charla en Curry On, que reúne resultados de computabilidad y complejidad para explicar por qué verificar programas es intrínsecamente costoso. Sostiene que la corrección tiene un precio que no puede evitarse con mejores herramientas.
Foto: vía pron.github.io
1 medio · MadridPublicada 12 nov, 11:55Actualizada 12 nov, 22:20· Ya no está en portadaEscrita por IA · cómo funciona
El autor parte de su experiencia especificando y verificando formalmente la nueva versión de Galaxy. Su motivación son las afirmaciones, que dice haber leído en internet, según las cuales la corrección del software es fácil de lograr con las herramientas adecuadas. Admite que algunas herramientas ayudan, pero defiende que la corrección tiene un coste significativo, comparable al coste energético de reducir la entropía, y consecuencia de las «leyes naturales» de la computación.
El primer capítulo repasa los fundamentos: el programa de Hilbert (consistencia, completitud y decidibilidad), su lema «Wir müssen wissen. Wir werden wissen», los teoremas de incompletitud de Gödel y el teorema de la parada de Church y Turing en 1936. Incluye la demostración por diagonalización y señala que el teorema de la parada da directamente una versión del primer teorema de Gödel.
De ahí deriva corolarios ligados a la verificación: no existe un algoritmo general que decida si un programa alcanza un estado dado, y el teorema de Rice dice que ninguna propiedad no trivial de la función que calcula un programa es decidible (por ejemplo, saber si siempre devuelve el cuadrado de su entrada).
Por último presenta lo que llama el «teorema del Busy Beaver»: la función f(n), el máximo número de pasos de una máquina de Turing que termina con n estados, no es computable, ni tampoco ninguna función que la supere. Aplica el mismo argumento a la vista estática con g(n), el tamaño máximo de la prueba mínima de terminación, que tampoco es computable.
«Why Writing Correct Software Is Hard» · puesto 16 · 359 puntos · enviado por AriFordsham
Lo que dicen los comentarios
Los comentarios discuten sobre todo qué significa «correcto» y cuándo compensa verificar formalmente. Varios señalan que el software real convive con las incertidumbres del mundo y que las especificaciones cambian, y defienden pruebas más ligeras salvo en el núcleo crítico. Otros matizan el uso de los teoremas de Rice y Gödel: lo que prohíben es un método general, no probar propiedades de programas concretos y bien estructurados. También aparece el debate entre la CS más matemática y la más empírica, y una mención al papel de los LLM en la formalización.
Hay una distinción clara entre la corrección matemática abstracta y funcionar en el mundo real. El software que procesa entradas de humanos tiene que lidiar con las infinitas rarezas de la realidad.
El artículo confunde el teorema de Rice con la idea de que no se puede probar algo sobre un programa pequeño concreto. Lo que dice es que no hay un método general que decida sí o no para todos los programas.
Por Rice, ningún programa decide si una función arbitraria suma sus dos entradas, pero solo porque admitimos implementaciones difíciles de analizar. Para escribir software correcto en tiempo razonable hay que usar lenguajes y estilos fáciles de analizar.
El software es en la práctica derecho contractual: si uno tuviera solución, el otro también. No podemos fijar a la vez qué entradas, salidas y estados intermedios son aceptables, y eso es lo que exige el software correcto.
Gödel no demostró que ningún problema matemático pueda resolverse, sino que no hay un único sistema formal efectivo que los resuelva todos. Cada problema podría resolverse con algún razonamiento distinto.
Esta noticia la ha redactado una inteligencia artificial a partir de las fuentes citadas, con el criterio editorial de El Autómata (equilibrio, atribución y solo hechos publicados). Puede contener errores: consulta las fuentes originales. Modelo: claude-sonnet-5.5.