Teorema del programa estructurado

El teorema del programa estructurado es un resultado en la teoría de lenguajes de programación. Establece que toda función computable puede ser implementada en un lenguaje de programación que combine sólo tres estructuras lógicas. Esas tres formas (también llamadas estructuras de control) específicamente son:

1. Secuencia: ejecución de una instrucción tras otra.
2. Selección: ejecución de una de dos instrucciones (o conjuntos), según el valor de una variable booleana.
3. Iteración: ejecución de una instrucción (o conjunto) mientras una variable booleana sea 'verdadera'. Esta estructura lógica también se conoce como ciclo o bucle.

Este teorema demuestra que la instrucción GOTO no es estrictamente necesaria y que para todo programa que la utilice existe otro equivalente que no hace uso de dicha instrucción.

Los científicos de la computación usualmente acreditan el teorema a un artículo de 1966 escrito por Corrado Böhm y Giuseppe Jacopini. Sin embargo, David Harel rastreó sus orígenes hasta la descripción de 1946 de la arquitectura de von Neumann y el teorema de la forma normal de Kleene.

La demostración de Böhm-Jacopini describe cómo construir diagramas de flujo estructurados a partir de cualquier diagrama de flujo, usando los bits de una variable entera extra para dar seguimiento a la información que el programa original representa mediante puntos de entrada en el código. Esta construcción estuvo basada en el lenguaje de programación P′′ de Böhm. La demostración de Böhm-Jacopini no esclareció la cuestión sobre cuándo convendría usar programación estructurada para el desarrollo de software, en parte porque la construcción ofuscaba el código del programa en lugar de mejorarlo. Por otro lado, fue el punto de partida para iniciar el debate. Edsger Dijkstra escribió una importante carta titulada "La sentencia Go To considerada dañina" en el año 1968. Posteriores estudios agregaron aproximaciones más prácticas a la demostración de Böhm-Jacopini, que mantenían o mejoraban la claridad del programa original.​

Bibliografía

• Ashcroft, Edward; and Zohar Manna (1971). «The translation of go to programs to 'while' programs». Proceedings of IFIP Congress. 
• Bohm, Corrado; and Giuseppe Jacopini (mayo de 1966). «Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules». Communications of the ACM 9 (5): 366-371. doi:10.1145/355592.365646. 
• Harel, David (1980). «On Folk Theorems». Communications of the ACM 23 (7): 379-389. doi:10.1145/358886.358892. 
• Dijkstra, Edsger (1968). «Go To Statement Considered Harmful». Communications of the ACM 11 (3): 147-148. doi:10.1145/362929.362947.  https://web.archive.org/web/20070703050443/http://www.acm.org/classics/oct95/
• (en inglés) The Böhm–Jacopini Theorem is False, Propositionally

Véase también

• Programación estructurada
• Diagrama Nassi-Shneiderman
• Estructuras de control
  • Bloque de código
  • Bucle
  • Bucle for
  • Bucle while
  • Bucle repetir
  • Ciclo infinito
• Turing completo

• Datos: Q2635326