Structured program theorem: Difference between revisions

Revision as of 10:37, 22 January 2025

Revision as of 21:57, 27 May 2025

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 journalbook|chapter-url= http://www.cs.cornell.edu/~kozen/papers/bohmjacopini.pdf |author=[[Dexter Kozen]] and Wei-Lung Dustin Tseng|titlechapter=Mathematics of Program Construction - The Böhm–Jacopini Theorem is False, Propositionally |doi=10.1007/978-3-540-70594-9_11|journaltitle=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)