Control-flow graphs with 3 types of control structures can compute any computable function
The structured program theorem, also called the Böhm–Jacopini theorem,[1][2] is a result in programming language theory. It states that a class of control-flow graphs (historically called flowcharts in this context) can compute any computable function if it combines subprograms in only three specific ways (control structures). These are
Executing one subprogram, and then another subprogram (sequence)
Executing one of two subprograms according to the value of a boolean expression (selection)
Repeatedly executing a subprogram as long as a boolean expression is true (iteration)
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. The construction was based on Böhm's programming language P′′.
The theorem forms the basis of structured programming, a programming paradigm which eschews goto commands and exclusively uses subroutines, sequences, selection and iteration.
Graphical representation of the three basic patterns of the structured program theorem — sequence, selection, and repetition — using NS diagrams (blue) and flow charts (green).
^Dexter Kozen and Wei-Lung Dustin Tseng (2008). "The Böhm–Jacopini Theorem is False, Propositionally". Mathematics of Program Construction(PDF). Lecture Notes in Computer Science. Vol. 5133. pp. 177–192. CiteSeerX 10.1.1.218.9241. doi:10.1007/978-3-540-70594-9_11. ISBN 978-3-540-70593-2. {{cite book}}: |journal= ignored (help)
^"CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM". Cse.buffalo.edu. 2004-11-22. Retrieved 2013-08-24.
and 22 Related for: Structured program theorem information
The structuredprogramtheorem, also called the Böhm–Jacopini theorem, is a result in programming language theory. It states that a class of control-flow...
modify. The structuredprogramtheorem provides the theoretical basis of structuredprogramming. It states that three ways of combining programs—sequencing...
Structuretheorem may refer to: Structuredprogramtheorem, a result in programming language theory Structuretheorem for finitely generated modules over...
(see § language support). The structuredprogramtheorem proved that the goto statement is not necessary to write programs that can be expressed as flow...
Kosaraju refined the structuredprogramtheorem by proving that it is possible to avoid adding additional variables in structuredprogramming, as long as arbitrary-depth...
(CFGs) of non-structuredprograms look like in terms of their subgraphs, which McCabe identified. (For details, see structuredprogramtheorem.) McCabe concluded...
the structuredness of a program" in his words) rather than a yes/no answer to the question of whether a program's control-flow graph is structured or not...
In mathematics, a theorem is a statement that has been proved, or can be proved. The proof of a theorem is a logical argument that uses the inference...
In topology, the Jordan curve theorem asserts that every Jordan curve (a plane simple closed curve) divides the plane into an "interior" region bounded...
diagonal argument, Gödel's incompleteness theorem, and Turing's halting problem. In particular, no program P computing a lower bound for each text's Kolmogorov...
engineering economics, spiral development Corrado Böhm – author of the structuredprogramtheorem Kurt Bollacker Jeff Bonwick – invented slab allocation and ZFS...
(RTMs), laying the foundation for reversible programming. The reversible variant of the structuredprogramtheorem, for instance, can be effectively analyzed...
Prolog is a logic programming language that has its origins in artificial intelligence, automated theorem proving and computational linguistics. Prolog...
language, the first meta-circular evaluator, contributed the structuredprogramtheorem Grady Booch, developer of Unified Modeling Language (UML) Kathleen...
index is a data structure to facilitate fast lookup of terms and clauses in a logic program, deductive database, or automated theorem prover. Many operations...
"sporadic groups" The classification theorem has applications in many branches of mathematics, as questions about the structure of finite groups (and their action...
be tested in the next table entry. See Structuredprogramtheorem) Multiway branching is an important programming technique which is all too often replaced...
The infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type...
the Bondy–Chvátal theorem, which generalizes earlier results by G. A. Dirac (1952) and Øystein Ore. Both Dirac's and Ore's theorems can also be derived...
Global Information