Seguici su Telegram, ne vale la pena ❤️ ➡ @trovalost
Vai al contenuto

Il teorema di Bohm-Jacopini spiegato in modo semplice

Tag:

Il Teorema di Bohm-Jacopini viene ideato dai matematici e informatici teorici Corrado Bohm e Giuseppe Jacopini negli anni ’60, rappresenta un risultato cruciale nell’ambito della teoria dei linguaggi di programmazione. Questo teorema dimostra infatti che qualsiasi programma in un linguaggio iterativo (come PHP, Javascript, Python, C++, …) può essere espresso utilizzando esclusivamente tre tipi di strutture di controllo fondamentali: sequenza, selezione/condizione, ciclo.

Nello specifico, la sequenza indica una sequenza o blocco di istruzioni, da eseguire una di seguito all’altra; la selezione / condizionale indica un bivio in cui si deve scegliere se fare una cosa oppure un’altra; il ciclo che indica un blocco di istruzioni che viene ripetuto. Nel teorema originale si applicava il ragionamento ad una macchina di Turing, modello ideale di qualsiasi computer programmabile. La dimostrazione avviene per induzione e viene affidata ad un formalismo di decomposizione matematica, che si può consultare ad esempio qui.

A livello informale, possiamo utilizzare l’esempio delle ricette per dimostrare il teorema di Bohm-Jacopini. Immaginiamo di dover scrivere un algoritmo per preparare una ricetta: la ricetta contiene istruzioni sequenziali, decisioni basate su condizioni (selezioni) e iterazioni (cicli). Dimostreremo che qualsiasi algoritmo di questo tipo può essere riscritto utilizzando solo sequenze, selezioni e cicli.

Supponiamo di avere la seguente ricetta:

1. Prepara gli ingredienti.
2. Mescola gli ingredienti.
3. Se la miscela sembra troppo densa, aggiungi un po' di liquido.
4. Cuoci sulla griglia finché dorato.
5. Servi caldo.

Possiamo adattare questa ricetta in termini di struttura di controllo:

markdown
Sequenza
Prepara gli ingredienti
Mescola gli ingredienti
Seleziona
Condizione: la miscela sembra troppo densa
Aggiungi un po' di liquido
Fine
Cuoci sulla griglia finché dorato
Servi caldo

Ora dimostreremo come trasformare ogni parte di questa struttura in selezioni annidate:

  1. Prepara gli ingredienti è un’istruzione semplice, quindi è già nella forma desiderata.
  2. Mescola gli ingredienti è un’altra istruzione semplice.
  3. Condizione: la miscela sembra troppo densa è una selezione.
  4. Aggiungi un po’ di liquido è un’istruzione semplice.
  5. Cuoci sulla griglia finché dorato è un ciclo (iterazione) mentre la condizione “finché dorato” è un’istruzione di selezione.
  6. Servi caldo è un’altra istruzione semplice.

In questa dimostrazione dell’esempio delle ricette, abbiamo mostrato come una sequenza di istruzioni, decisioni basate su condizioni (selezioni) e iterazioni (cicli) possano essere rappresentate utilizzando solo selezioni annidate. Questo esemplifica il teorema di Bohm-Jacopini, che afferma che qualsiasi algoritmo può essere implementato utilizzando solo sequenze, selezioni e cicli.

Non è difficile immaginare, a livello pratico, che la sequenza sia la sequenza di istruzioni di un linguaggio, la selezione rappresenti una condizione if dicotomica o binaria (del tipo vero o falso, a cui eventuali condizioni a n possibilità si possono sempre ricondurre), mentre il ciclo sia di fatto il loop che si implementa mediante for oppure while. Questo rende l’idea dell’importanza teorica del teorema, ampiamente sottovalutato e dato un po’ per scontato, ed estremamente utile per le ricerche successive in informatica teorica.

https://www.youtube.com/watch?v=dApO05KlzPM

👇 Da non perdere 👇

Questo portale web esiste da 4469 giorni (12 anni), e contiene ad oggi 7519 articoli (circa 6.015.200 parole in tutto) e 14 servizi online gratuiti. – Leggi un altro articolo a caso
5/5 (1)

Ti sembra utile o interessante? Vota e fammelo sapere.

Leggi anche:
Questo sito contribuisce alla audience di sè stesso.
Il nostro network informativo: Lipercubo.it - Pagare.online - Trovalost.it.