Twierdzenie Böhma-Jacopiniego
Twierdzenie o programie strukturalnym (ang. Structured program theorem), nazywane także Twierdzeniem Böhma-Jacopiniego (ang. Böhm–Jacopini theorem)[1][2] – twierdzenie w teorii języków programowania mówiące o tym że grafy przepływu sterowania mogą obliczyć dowolną funkcję obliczalną, jeżeli kombinują podprogramy tylko na 3 sposoby:
- Wykonanie jednego podprogramu, a następnie kolejnego podprogramu (sekwencja);
- Wykonywanie jednego z dwóch podprogramów zgodnie z wartością wyrażenia logicznego (selekcja);
- Wielokrotne wykonywanie podprogramu, o ile prawdziwe jest wyrażenie boolowskie (iteracja).
Pochodzenie tego twierdzenia jest zwyczajowo przypisywane[3] publikacji z roku 1966 której autorami byli Corrado Böhm and Giuseppe Jacopini[4]. David Harel napisał w 1980 że publikacja Böhma-Jacopiniego cieszy się powszechną popularnością[3], szczególnie przez zwolenników paradygmatu programowania strukturalnego.
Przypisy[edytuj | edytuj kod]
- ↑ Dexter Kozen, Wei-Lung Dustin Tseng, The Böhm–Jacopini Theorem Is False, Propositionally, „Mpc 2008” (Lecture Notes in Computer Science), DOI: 10.1007/978-3-540-70594-9_11, ISBN 978-3-540-70593-2.
- ↑ CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM, Cse.buffalo.edu, 22 listopada 2004.
- ↑ a b David Harel, On Folk Theorems, „Communications of the ACM”, 23, 1980, s. 379–389, DOI: 10.1145/358886.358892.
- ↑ Corrado Bohm, Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules, „Communications of the ACM”, 9, 1966, s. 366–371, DOI: 10.1145/355592.365646.