Il teorema di Böhm-Jacopini

I sistemi di programmazione sono numerosi e, oltre ad aggiornarsi mese per mese, cambiano e spesso è necessario imparare a dialogare con più software, molto diversi fra loro. All'inizio dell'era informatica, però, questo campo era una landa libera dove vari "esploratori" hanno costruito le basi di tutto ciò che conosciamo oggi. Tra i pionieri della ricerca informatica ricordiamo due matematici italiani: Corrado Böhm e Giuseppe Jacopini. Essi spesero gran parte della loro vita nello studio della macchina di Turing e dell'architettura di Von Neumann arrivando ad enunciare, nel 1966, il famoso Teorema di Böhm-Jacopini, base dei moderni linguaggi di programmazione strutturati.

• Conoscenze di base di fondamenti di informatica

Prima di enunciare il suddetto teorema andiamo ad effettuare un breve excursus sul concetto di algoritmo: è detto algoritmo una sequenza di istruzioni (o passi) chiare per il simulatore, tali che, se espresse e codificate in ordine preciso, portano alla soluzione istantanea di un dato problema. Un algoritmo può essere espresso, a seconda del campo in cui ci si muove, con un linguaggio testuale (codice o linguaggio di programmazione) o con un linguaggio grafico (schemi di flusso o flow-chart). Ora che abbiamo compreso il tema che stiamo trattando procediamo con il teorema in se.

Il teorema di Böhm-Jacopini afferma che qualsiasi algoritmo, in qualsiasi linguaggio, può essere implementato in codice di programmazione utilizzando tre sole strutture di controllo: sequenza, selezione e iterazione del ciclo. Per sequenza si intende la normale scrittura dell'elenco di informazioni e ordini, così come è stata pensata ed espressa dal programmatore. È fondamentale a garantirne il corretto utilizzo che le informazioni siano nell'ordine corretto. La selezione è, invece, una condizione che dividerà il flusso in due direzioni a seconda di un data risposta ad una domanda. La suddetta condizione è molto spesso una variabile booleana e si caratterizza, nella maggior parte dei casi, di comandi del tipo "if" (se) o "or" (oppure). Nei sistemi più moderni può essere molto più complicata e permette la scelta fra tre o più vie. L'ultima struttura di controllo di cui necessita un algoritmo per funzionare e l'iterazione, la ripetizione di una certa operazione fino a quando una delle condizioni non cambia di stato. Un tipico comando che sfrutta l'iterazione è "while" (mentre) o "until" (fino a).

La nascita di questo enunciato portò, alla fine degli anni '60 e all'inizio dei '70, un notevole cambiamento rispetto al comportamento che si seguiva riguardo alla programmazione. L'uso sconsiderato di alcuni comandi come "go to" fu fermato, mentre furono garantiti tre benefici fondamentali per il successo dell'industria informatica:

- La leggibilità, che permetteva a tutti i calcolatori, una volta implementato il codice, di capire univocamente gli ordini;

- La modificabilità, ovvero la possibilità di entrare all'interno del codice e modificarlo in ogni momento, secondo necessità;

- La semplicità di codifica, ovvero la facilità di sapere quali informazioni usare e quando, senza dubbi.

• Critica al teorema
• Cos'è un linguaggio di programmazione?

• Come calcolare un algoritmo
• Appunti sugli algoritmi
• Algoritmi: le proprietà