Teorema del programa estructurat

De Viquipèdia

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 un altre (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 arribar a la descripció de 1946 de la arquitectura de Von Neumann i el teorema formal de Kleene.

[edita] Enllaços externs

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