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:

  1. Wykonanie jednego podprogramu, a następnie kolejnego podprogramu (sekwencja);
  2. Wykonywanie jednego z dwóch podprogramów zgodnie z wartością wyrażenia logicznego (selekcja);
  3. 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

  1. ↑ DexterD. Kozen DexterD., Wei-Lung DustinW.L.D. Tseng Wei-Lung DustinW.L.D., 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 .
  2. ↑ CSE 111, Fall 2004, BOEHM-JACOPINI THEOREM, Cse.buffalo.edu, 22 listopada 2004 .
  3. ↑ a b DavidD. Harel DavidD., On Folk Theorems, „Communications of the ACM”, 23, 1980, s. 379–389, DOI: 10.1145/358886.358892 .
  4. ↑ CorradoC. Bohm CorradoC., 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 .