Structured program theorem

A theorem stating that every computable function can be implemented using sequence, selection, and iteration, without unrestricted jumps such as GOTO.

Connect

Sequence: A control structure that executes statements in a specified order. It is one of the three primitives sufficient to express every computable function.
Corrado Böhm: An Italian computer scientist known for work in programming languages and computability. Böhm co-authored the 1966 paper that established the theorem.
GOTO statement: A programming statement that transfers control directly to a labeled location. The theorem establishes that unrestricted transfers are unnecessary for computability.
Structured programming theorem and program complexity: A line of analysis examining the size costs of converting arbitrary programs into structured ones. The theorem permits transformations that can produce substantial code expansion.
Selection: A control structure that chooses among actions according to a condition. Conditional branching supplies the theorem’s choice primitive without arbitrary jumps.
Giuseppe Jacopini: An Italian computer scientist whose work included programming-language theory. Jacopini co-authored the result that showed structured control suffices.
Structured programming: A programming paradigm organized around structured control flow and modular procedures. The theorem supports this broader discipline but does not by itself prescribe its practices.
Böhm–Jacopini theorem with one loop and one exit: A refinement showing that structured computation can be encoded with a single while-loop form and auxiliary state. The refinement illustrates how far the theorem’s minimal control repertoire can be compressed.
Iteration: Repeated execution of a statement or block, usually controlled by a condition. Loops provide the theorem’s repetition primitive.
Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules: A 1966 paper by Corrado Böhm and Giuseppe Jacopini on structured representations of computation. This paper is the theorem’s original publication.