Editing Structured program theorem (section)

{{short description|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''',<ref name="kozen">{{cite book|chapter-url= http://www.cs.cornell.edu/~kozen/papers/bohmjacopini.pdf |author=[[Dexter Kozen]] and Wei-Lung Dustin Tseng|chapter=Mathematics of Program Construction - The Böhm–Jacopini Theorem is False, Propositionally |doi=10.1007/978-3-540-70594-9_11|title=MPC 2008|volume=5133|pages=177–192|series=Lecture Notes in Computer Science|year=2008|isbn=978-3-540-70593-2|citeseerx=10.1.1.218.9241}}</ref><ref>{{cite web|url=http://www.cse.buffalo.edu/~rapaport/111F04/greatidea3.html |title=CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM |publisher=Cse.buffalo.edu |date=2004-11-22 |access-date=2013-08-24}}</ref> is a result in [[programming language theory]]. It states that a class of [[control-flow graph]]s (historically called [[flowchart]]s in this context) can compute any [[computable function]] if it combines subprograms in only three specific ways ([[control structure]]s). These are
#Executing one subprogram, and then another subprogram (sequence)
#Executing one of two subprograms according to the value of a [[Boolean data type|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 [[bit]]s (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|goto commands]] and exclusively uses subroutines, sequences, selection and iteration.[[File:Structured program patterns.svg|Graphical representation of the three basic patterns of the structured program theorem — sequence, selection, and repetition — using [[Nassi–Shneiderman diagram|NS diagrams]] (blue) and [[flow chart]]s (green).|thumb|center|border|700px]]