The structured program theorem [...] states that [...] any algorithm can be expressed using only three control structures. They are
- Executing one subprogram, and then another subprogram (sequence)
- Executing one of two subprograms according to the value of a boolean expression (selection)
- Executing a subprogram until a boolean expression is true (iteration)
This theorem is developed in the following papers:
- C. Böhm, "On a family of Turing machines and the related programming language", ICC Bull., 3, 185–194, July 1964.
- C. Böhm, G. Jacopini, "Flow diagrams, Turing Machines and Languages with only Two Formation Rules", Comm. of the ACM, 9(5): 366–371,1966.
Unfortunately, the first one is practically unavailable, and the second one, in addition to being a bit cryptic (at least for me), refers to the first, so I have problems to understand the proof. Can anyone help me? Is there a modern paper or book which presents the proof? Thanks.
UPDATE
To be exact, I would like to understand the second part of the CACM paper (section 3). The authors write in section 1 the following:
In the second part of the paper (by C. Böhm), some results of a previous paper are reported [8] and the results of the first part of this paper are then used to prove that every Turing machine is reducible into, or in a determined sense is equivalent to, a program written in a language which admits as formation rules only composition and iteration.
Here [8] refers to the unavailable ICC Bulletin paper. It is easy to see that the above quote from Wikipedia refers to this second part of the CACM paper (the Turing machine serves as a precise definition of algorithms; "composition" means sequence; an iteration can replace a selection).