Teorema di Böhm-Jacopini

Da Wikipedia, l'enciclopedia libera.

Il teorema di Böhm-Jacopini, enunciato nel 1966[1] dagli informatici Corrado Böhm e Giuseppe Jacopini, afferma che qualunque algoritmo può essere implementato in codice sorgente, pseudocodice o diagramma di flusso, utilizzando tre sole strutture dette strutture di controllo: la sequenza, la selezione ed il ciclo (iterazione), da applicare ricorsivamente alla composizione di istruzioni elementari (ad es. di istruzioni eseguibili con il modello di base della macchina di Turing).

Strutture[modifica | modifica sorgente]

Sequenza[modifica | modifica sorgente]

La sequenza o blocco è la normale elencazione di istruzioni perché vengano eseguite una di seguito all'altra nell'ordine in cui sono state scritte dal programmatore.

Selezione[modifica | modifica sorgente]

La selezione è la scelta fra due percorsi da seguire successivamente, che dipende da una condizione che può essere vera o falsa. Nei linguaggi di programmazione questa struttura viene definita di solito con l'uso di parole chiave come if ... then ... else. La condizione può essere una semplice variabile informatica booleana, cioè una variabile che può avere i soli valori "vero" e "falso". Nella pratica della programmazione vengono normalmente usati costrutti selettivi come if (a > 10) nei quali l'espressione tra parentesi è un'espressione booleana. Questo costrutto però si può considerare un'abbreviazione di una sequenza di assegnazioni preliminari conclusa da una selezione su una semplice variabile booleana. Nella pratica sono utilizzate anche selezioni a più di due vie, come quella implicita nell'operatore ?: del linguaggio C, lo storico IF a tre vie del FORTRAN 2 (istruzioni come: IF(numero)100,200,300) e i vari selettori a più vie come un'antica forma di GOTO del FORTRAN 2 e i costrutti come quello del C basato su switch e case. Anche tutti questi costrutti si possono ridurre senza difficoltà alla selezione dicotomica di base.

Ciclo (o iterazione)[modifica | modifica sorgente]

Il ciclo, detto anche iterazione, è un blocco di istruzioni che vengono ripetutamente eseguite fino a che una certa condizione cambia di stato. Nella pratica si utilizzano diversi tipi di ciclo: quelli con la clausola sulla condizione in testa, quelli con la clausola in coda, quelli con la clausola in mezzo e quelli che prevedono lo scorrimento di una sequenza enumerativa (strettamente numerica o meno). Per l'implementazione si usano parole chiave come: while ... do, do ... until, for ... do, o similari. Anche tutti questi costrutti si possono ridurre ad un costrutto base.

Conseguenze[modifica | modifica sorgente]

Questo teorema ha un interesse soprattutto teorico, in quanto i linguaggi di programmazione tendono a dotarsi di più tipi di istruzioni di larga portata per evitare che i programmatori debbano occuparsi di istruzioni di portata molto minuta e quindi dispersive per quanto attiene alla padronanza delle finalità dell'algoritmo (esistono però linguaggi minimalisti, come Brainfuck, che si attengono alla lettera al teorema). Il suo valore va visto nella sua capacità di fornire indicazioni generali per le attività di progettazione di nuovi linguaggi e di strategie di programmazione. In effetti esso ha contribuito alla critica dell'uso sconsiderato delle istruzioni go to e alla definizione delle linee guida della programmazione strutturata che si sono avuti intorno al 1970.

Note[modifica | modifica sorgente]

  1. ^ C. Bohm, e G. Jacopini, Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules in Communications of the ACM, vol. 9, nº 5, maggio 1966, pp. 366–371, DOI:10.1145/355592.365646.

Collegamenti esterni[modifica | modifica sorgente]