Content deleted Content added
Changing short description from "Control flow graph with 3 types of controls can compute any computable function" to "Control flow graphs with 3 types of control structures can compute any computable function" (Shortdesc helper) |
Add illustration |
||
Line 1:
[[File:Structured program patterns.png|thumb|700px|center|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).]]
{{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 |accessdate=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
| |||