Content deleted Content added
→Implications and refinements: Used the correct link to the article about the letter, as in Goto#Criticism; bolded for the same reason |
unfloat image and move down, since it is almost my whole screen width |
||
Line 1:
{{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|url= http://www.cs.cornell.edu/~kozen/papers/bohmjacopini.pdf |title=The Böhm–Jacopini Theorem Is False, Propositionally|author=[[Dexter Kozen]] and Wei-Lung Dustin Tseng|doi=10.1007/978-3-540-70594-9_11|journal=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)
Line 8 ⟶ 7:
The structured chart subject to these constraints 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.png|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).|center|frame]]
== Origin and variants ==
The theorem is typically credited<ref name="Harel"/>{{rp|381}} to a 1966 paper by [[Corrado Böhm]] and [[Giuseppe Jacopini]].<ref>{{cite journal|last=Bohm|first=Corrado|author2=Giuseppe Jacopini |date=May 1966|title=Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules|journal=[[Communications of the ACM]]|volume=9|issue=5|pages=366–371|doi=10.1145/355592.365646|citeseerx=10.1.1.119.9119|s2cid=10236439 }}</ref> [[David Harel]] wrote in 1980 that the Böhm–Jacopini paper enjoyed "universal popularity",<ref name="Harel"/>{{rp|381}} particularly with proponents of structured programming. Harel also noted that "due to its rather technical style [the 1966 Böhm–Jacopini paper] is apparently more often cited than read in detail"<ref name="Harel"/>{{rp|381}} and, after reviewing a large number of papers published up to 1980, Harel argued that the contents of the Böhm–Jacopini proof were usually misrepresented as a [[Mathematical folklore|folk theorem]] that essentially contains a simpler result, a result which itself can be traced to the inception of modern computing theory in the papers of [[John von Neumann|von Neumann]] and [[Stephen Cole Kleene|Kleene]].<ref name="Harel"/>{{rp|383}}
| |||