Newtonpedia EN
Inicio › Informática › Teorema del programa estructurado
Informática · 1966

Teorema del programa estructurado

Resultado teórico que afirma que cualquier cálculo puede expresarse usando solo secuencia, selección e iteración, sin necesidad de saltos GOTO.

Año
1966
Protagonistas
Corrado Böhm
Sección
Informática

Historia

El teorema del programa estructurado responde a una pregunta de fondo en la informática: si todo programa puede escribirse sin saltos arbitrarios en el código. Un programa de ordenador puede describirse como un diagrama de flujo, es decir, una red de pasos conectados por flechas que indican qué se ejecuta después. Cuando esas flechas pueden saltar a cualquier lugar, el código resulta difícil de seguir, lo que los programadores llaman a veces código espagueti. El teorema afirma que basta con tres estructuras para combinar instrucciones: ejecutar una tras otra (secuencia), elegir entre dos caminos según si una condición es verdadera o falsa (selección) y repetir un bloque mientras una condición se cumpla (iteración).

Antes de 1966 ya existían ideas cercanas. En 1964 Corrado Böhm había definido un lenguaje de programación sencillo, llamado P′′, capaz de expresar cualquier cálculo usando solo secuencia e iteración. Ese mismo año se conocían resultados de la teoría de la computación, como el teorema de la forma normal de Kleene de 1936 y la descripción de la arquitectura de von Neumann de 1946, en la que un contador de programa recorre las instrucciones de manera ordenada. Con ellos se podía demostrar que un programa cualquiera puede reescribirse como un único gran bucle, aunque el resultado tuviera poco valor práctico.

En 1966 Böhm y Giuseppe Jacopini publicaron un artículo en el que demostraban que cualquier diagrama de flujo puede transformarse en otro estructurado. Para lograrlo emplearon bits de una variable entera auxiliar que registran en qué punto del programa original se encuentra la ejecución. La demostración es correcta, pero el programa resultante suele ser más difícil de leer que el original, así que no resolvió si la programación estructurada mejoraba realmente el desarrollo de software. Esa duda fue el origen del debate. En 1968 Edsger Dijkstra publicó la carta «La sentencia Go To considerada dañina», que impulsó el abandono del GOTO y la adopción de estructuras de control claras. Posteriormente aparecieron demostraciones más prácticas que mantenían, e incluso mejoraban, la claridad del código original.

El teorema tiene hoy un impacto muy amplio. Los lenguajes actuales, desde los usados en la enseñanza hasta los de sistemas y aplicaciones web, se basan en estas estructuras de control, y los compiladores aprovechan transformaciones similares para optimizar código. Además, la idea se ha extendido a la computación reversible, donde cada paso puede deshacerse, y sigue siendo un punto de partida para pensar sobre cómo organizar los programas.

Cronología

  • 1964Corrado Böhm define el lenguaje P′′, basado en secuencia e iteración.
  • 1966Böhm y Giuseppe Jacopini publican la demostración de que cualquier diagrama de flujo puede estructurarse.
  • 1968Edsger Dijkstra publica la carta «La sentencia Go To considerada dañina».
  • 1973S. Rao Kosaraju demuestra que se pueden evitar variables adicionales si se permiten saltos de salida múltiples desde bucles.

Curiosidades y anécdotas

Un teorema citado más de lo leído

Según David Harel, el artículo de 1966 se cita con frecuencia, pero se lee poco en detalle por su estilo técnico.

Otros hitos de informática