Twierdzenie Böhma-Jacopiniego

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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[edytuj | edytuj kod]

  1. Dexter Kozen, Wei-Lung Dustin Tseng, The Böhm–Jacopini Theorem Is False, Propositionally, „Mpc 2008” (Lecture Notes in Computer Science), DOI10.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 David Harel, On Folk Theorems, „Communications of the ACM”, 23, 1980, s. 379–389, DOI10.1145/358886.358892.
  4. Corrado Bohm, Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules, „Communications of the ACM”, 9, 1966, s. 366–371, DOI10.1145/355592.365646.