Blog

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:

Possiamo adattare questa ricetta in termini di struttura di controllo:

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

👇 Contenuti da non perdere 👇

• Cellulari 📱
• Domini Internet 🌍
• Lavoro 🔧
• Marketing & SEO 🌪
• Scrivere 🖋
• Sicurezza & Privacy 👁
• 💬 Il nostro canale Telegram: iscriviti
• 🟠 ERR_NETWORK_CHANGED: come risolverlo e da cosa dipende
• 🔴 Come bloccare i commenti in WordPress
• 🔵 Significato “on the edge” – Wikilost

Numero di visualizzazioni (dal 21 agosto 2024): 90

Pubblicità - Continua a leggere sotto :-)

Seguici su Telegram: @trovalost