Structured program theorem
These are The structured chart subject to these constraints, particularly the loop constraint implying a single exit (as described later in this article), may however use additional variables in the form of bits (stored in an extra integer variable in the original proof) in order to keep track of information that the original program represents by the program location.
Harel notes that the single loop used by the folk version of the structured programming theorem basically just provides operational semantics for the execution of a flowchart on a von Neumann computer.
[3]: 383 Donald Knuth criticized this form of the proof, which results in pseudocode like the one below, by pointing out that the structure of the original program is completely lost in this transformation.
[6]: 274 Similarly, Bruce Ian Mills wrote about this approach that "The spirit of block structure is a style, not a language.
By simulating a Von Neumann machine, we can produce the behavior of any spaghetti code within the confines of a block-structured language.
[3]: 381 Because it employed pattern matching in graphs, the proof of Böhm and Jacopini's was not really practical as a program transformation algorithm, and thus opened the door for additional research in this direction.
This theorem lays the foundational principles for constructing reversible algorithms within a structured programming framework.
However, for its reversible version, while a global method of proof is recognized, a local approach similar to that undertaken by Böhm and Jacopini[4] is not yet known.
[13] In 1973, S. Rao Kosaraju proved that it's possible to avoid adding additional variables in structured programming, as long as arbitrary-depth, multi-level breaks from loops are allowed.
Reducibility was defined by Kosaraju, loosely speaking, as computing the same function and using the same "primitive actions" and predicates as the original program, but possibly using different control flow structures.
Inspired by this result, in section VI of his highly-cited paper that introduced the notion of cyclomatic complexity, Thomas J. McCabe described an analogue of Kuratowski's theorem for the control-flow graphs (CFG) of non-structured programs, which is to say, the minimal subgraphs that make the CFG of a program non-structured.
This latter result helps explain how the control flow of non-structured program becomes entangled in what is popularly called "spaghetti code".
The strictness of the chosen notion of equivalence dictates the minimal set of control flow structures needed.
