Quinta puntata del nostro viaggio
In questo post proseguiamo il discorso sugli automi, cioè gli esecutori meccanici delle elaborazioni, modello astratto dei nostri computer. Come visto nel precedente post, un automa a stati finiti non possiede tutto il potere computazionale che ci serve. A questo scopo è necessario un esecutore più potente e la macchina universale di Turing (MUT), un modello formale di un automa definito dal matematico inglese Alan Turing nel 1936, è quello che fa al caso nostro. Il suo autore ha evidenziato che essa è in grado di calcolare tutto ciò che noi esseri umani riteniamo calcolabile. È importante fare attenzione al fatto che questa affermazione non è un teorema matematico: si chiama infatti “tesi di Turing” e non “teorema di Turing” proprio perché non esiste una definizione matematicamente precisa di “calcolabilità” che sia indipendente dall’esecutore usato. Si è visto però che è un approccio robusto, perché altri modelli formali di esecutori meccanici hanno portato agli stessi risultati.
L’esposizione della MUT richiederebbe complicazioni eccessive per i nostri scopi, per cui presento una sua versione più facilmente comprensibile che ha lo stesso potere computazionale, la macchina a registri (MR), nella versione minimale che ci serve per capirne i princìpi di funzionamento. I computer che usiamo ogni giorno, anche quelli annidati all’interno dei dispositivi più o meno smart che sempre di più fanno parte della nostra vista, sono tutti esempi di MR, tecnologicamente molto sofisticati, ma con il suo stesso potere computazionale.
La MR ha le componenti illustrate nella figura sotto e descritte nel seguito:
– una prima serie di celle di memoria, ognuna delle quali ha un indirizzo numerico, che è un intero positivo, ed è in grado di contenere un’istruzione del linguaggio che la macchina è in grado di eseguire. L’insieme delle istruzioni che in un certo momento si trovano nelle celle di memoria costituisce il programma che la macchina sta eseguendo.
– una seconda serie di celle di memoria, dette registri, che contengono i dati. Anche queste celle hanno un indirizzo numerico costituito da un intero positivo e assumiamo che i dati contenuti in esse siano soltanto interi non negativi.
– un registro particolare (di indirizzo prefissato che indichiamo con il nome simbolico IC) che contiene l’Indirizzo Corrente della prossima istruzione da eseguire.
– un’Unità di Controllo (UC) che dirige il funzionamento generale della macchina.
– un’Unità Aritmetico-Logica (UAL) che esegue le computazioni aritmetiche e logiche di base.
Quella appena descritta è quindi la struttura (o architettura) della MR, chiamata anche “architettura di von Neumann”, dal nome del matematico di origine ungherese John von Neumann che la propose nel 1945. Nella nostra descrizione prescindiamo dall’interazione tra la MR e il mondo esterno, che avviene tramite i dispositivi di ingresso e uscita (input e output), fondamentali per il suo effettivo utilizzo, ma trascurabili ai fini di questa presentazione. Osserviamo che abbiamo distinto le celle di memoria che contengono il programma e quelle che contengono i dati solo per semplicità concettuale. In realtà questa distinzione non esiste, in linea generale, ed è alla base di quella dualità tra dati e programmi che rappresenta una delle conquiste culturali più importanti dell’informatica.
Il comportamento della MR è determinato dalla UC, che esegue quanto descritto dall’automa a stati finiti della figura sottostante.
In altre parole, la macchina a registri ha un “motore” (cioè la UC) che ripete sempre le stesse due semplici azioni: leggere l’istruzione presente nella cella di memoria il cui indirizzo è il nome simbolico IC ed eseguirla. Nel seguito, useremo più semplicemente “IC” per indicare “la cella di memoria il cui indirizzo è il nome simbolico IC”, come già fatto nella figura sopra.
La prima domanda che viene in mente riflettendo su questo comportamento è: dal momento che il contenuto di IC viene incrementato ogni volta di 1, come può la macchina fare qualcosa di diverso dall’eseguire una semplice lista sequenziale di istruzioni? La risposta è che una delle istruzioni della MR è in grado di scrivere dentro IC un valore determinato da chi ha realizzato il programma, in modo tale che l’istruzione eseguita dopo quella corrente non sia più quella di indirizzo immediatamente successivo ad essa ma una qualunque altra.
La seconda domanda è: chi effettua davvero i calcoli che servono? La risposta è che i passi elementari che sono necessari vengono svolti dalla UAL, la quale ha bisogno, in ultima analisi, di saper fare, di tutte le operazioni matematiche, solo l’addizione. Senza entrare in dettagli tecnici complicati, ricordiamo infatti che la sottrazione può essere ricondotta all’addizione, la moltiplicazione e la divisione possono essere ricondotte alla ripetizione di, rispettivamente, addizioni e sottrazioni. Altre operazioni matematiche possono essere ottenute a partire dalle quattro operazioni aritmetiche. Allo stesso modo ogni operazione logica può essere ottenuta a partire da una sola. Opportuni programmi consentono, ripetendo in opportuna combinazione i passi elementari che è in grado di svolgere la UAL, di eseguire tutti i calcoli di cui abbiamo bisogno.
Nel post successivo vedremo come si fa a dare le istruzioni alla MR, ovvero qual è il linguaggio che la MR è in grado di “comprendere”, e un programma per la MR che risolve il problema enunciato alla fine del precedente post (cioè contare quanti “2” ci sono in una sequenza).
( I post di questa serie sono basati sul libro dell’Autore La rivoluzione informatica: conoscenza, consapevolezza e potere nella società digitale, al quale si rimanda per approfondimenti. I lettori interessati al tema possono anche dialogare con l’Autore, su questo blog interdisciplinare.)