Teorema del programa estructurat

El teorema del programa estructurat és un resultat de la teoria de llenguatges de programació. Aquest teorema estableix que tota funció computable pot ser implementada per un llenguatge de programació que combini subrutines de només 3 tipus. Aquestes 3 formes també anomenades estructures de control són:

• Executar una subrutina i després una altra (estructures de seqüència)
• Executar una subrutina seleccionada d'entre 2 rutines possibles depenent d'un valor boolea (estructures de selecció com IF-THEN-ELSE)
• Executar una subrutina durant el temps que una variable booleana sigui certa (estructures d'iteració, cicle o bucle)

Aquest teorema demostra que la instrucció GOTO no és estrictament necessària i que per a tot programa existeix un programa equivalent que no utilitza aquesta instrucció.

El experts en computació acrediten aquest teorema a un article escrit per Corrado Böhm i Giuseppe Jacopini. Tot i això, David Harel va rastrejar els orígens d'aquest teorema fins a arribar a la descripció de 1946 de l'arquitectura de Von Neumann i el teorema formal de Kleene.

Vegeu també

• Estructures de control
• Bucle (programació)
• Bucle For
• Bucle While
• Bucle repetir
• Cicle infinit
• Programació estructurada
• Llenguatge de programació

Enllaços externs

• Ashcroft, Edward; and Zohar Manna «The translation of go to programs to 'while' programs». Proceedings of IFIP Congress, 1971.
• Bohm, Corrado; and Giuseppe Jacopini «Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules». Communications of the ACM, 9, 5, maig 1966.
• Harel, David «On Folk Theorems». Communications of the ACM, 23, 1980.
• Dijkstra, Edsger «Go To Statement Considered Harmful». Communications of the ACM, 3 http://www.acm.org/classics/oct95/, 1968.