Back Teorema del programa estructurat Catalan Teorema del programa estructurado Spanish Teorema di Böhm-Jacopini Italian 構造化定理 Japanese Teorema de Böhm-Jacopini LMO Twierdzenie Böhma-Jacopiniego Polish Теорема Бёма — Якопини Russian Structured program theorem SIMPLE Структурна теорема Бьома — Якопіні Ukrainian 結構化程式理論 Chinese
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.
- ^ 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.