Capitolo 1

I Modelli Computazionali

L'alba dell'informatica moderna, negli anni immediatamente successivi alla Seconda Guerra Mondiale, fu caratterizzata non solo dall'ingegno pratico nella costruzione delle prime macchine calcolatrici, ma anche dalla definizione di solidi fondamenti teorici che avrebbero guidato lo sviluppo della disciplina per decenni a venire. In questo capitolo, esploreremo alcuni dei modelli computazionali più influenti che hanno gettato le basi per la comprensione e la realizzazione dei sistemi informatici.

1.1 La Macchina di Turing:
Definire i Limiti del Calcolo

Nel 1936, ben prima della costruzione dei primi computer elettronici, il matematico britannico Alan Turing pubblicò un articolo seminal dal titolo "On Computable Numbers, with an Application to the Entscheidungsproblem". In questo lavoro, Turing propose un modello astratto di calcolatore, oggi universalmente noto come Macchina di Turing. Questa non era una macchina fisica nel senso tradizionale del termine, bensì un costrutto teorico, un esperimento mentale ideato per rispondere a una domanda fondamentale e profondamente filosofica: quali problemi possono essere risolti mediante un processo algoritmico, ovvero attraverso una sequenza finita di istruzioni non ambigue?

Una Macchina di Turing è concettualmente composta da:

Un nastro infinito: Immaginate un nastro illimitato in entrambe le direzioni, suddiviso in celle contigue.

Ogni cella può contenere un singolo simbolo tratto da un alfabeto finito, che include almeno un simbolo speciale per indicare una cella vuota (spesso denotato con 'B' o '□').

Una testina: Un meccanismo in grado di posizionarsi su una specifica cella del nastro. Questa testina ha la capacità di leggere il simbolo presente nella cella corrente, scrivere un nuovo simbolo nella stessa cella e spostarsi di una posizione a destra o a sinistra lungo il nastro.
Un insieme finito di stati: La macchina si trova in uno stato specifico in ogni momento. Questo insieme di stati è finito e include uno stato iniziale (da cui la computazione ha inizio) e uno o più stati finali (o di accettazione), che indicano il termine di un calcolo con successo.
Una funzione di transizione: Il cuore della Macchina di Turing è la sua funzione di transizione. Questa funzione, che può essere rappresentata come una tabella o un insieme di regole, determina il comportamento della macchina in ogni passo. In base allo stato corrente della macchina e al simbolo letto dalla testina, la funzione di transizione specifica univocamente tre azioni: Il simbolo da scrivere sulla cella corrente (che potrebbe essere lo stesso simbolo letto). La direzione in cui la testina deve spostarsi (a sinistra, a destra o, in alcune definizioni, rimanere ferma). Il nuovo stato in cui la macchina deve passare.
Il simbolo da scrivere sulla cella corrente (che potrebbe essere lo stesso simbolo letto).
La direzione in cui la testina deve spostarsi (a sinistra, a destra o, in alcune definizioni, rimanere ferma).
Il nuovo stato in cui la macchina deve passare.

L'importanza concettuale della Macchina di Turing è straordinaria. Essa ha fornito una formalizzazione precisa e rigorosa del concetto intuitivo di algoritmo. L'idea chiave è che qualsiasi processo computazionale che può essere descritto da un insieme finito di regole non ambigue può essere simulato da una Macchina di Turing.

Questa nozione è formalizzata nella Tesi di Church-Turing, un principio fondamentale (non dimostrabile matematicamente ma ampiamente accettato) che afferma che qualsiasi funzione calcolabile da un essere umano che segue un insieme di regole meccaniche può essere calcolata da una Macchina di Turing.

La Macchina di Turing non solo ha fornito una definizione operativa di calcolabilità, ma ha anche permesso di esplorare i limiti intrinseci del calcolo. Ad esempio, Turing stesso utilizzò il suo modello per dimostrare l'esistenza di problemi indecidibili, ovvero problemi per i quali non esiste alcun algoritmo (e quindi nessuna Macchina di Turing) in grado di fornire una risposta definitiva (sì o no) per tutte le possibili istanze. Un esempio emblematico è il problema della fermata (Halting Problem): dato un programma (o una Macchina di Turing) e un suo input, è possibile determinare se il programma terminerà la sua esecuzione o continuerà a girare all'infinito? Turing dimostrò che non esiste un algoritmo generale per risolvere questo problema.

1.2 Il Modello di Von Neumann:
L'Architettura dei Computer Moderni

Mentre la Macchina di Turing rappresentava un modello teorico del calcolo, l'architettura proposta da John von Neumann, in collaborazione con altri pionieri come John Presper Eckert e John William Mauchly, ha fornito il progetto concettuale su cui si basa la stragrande maggioranza dei computer moderni. Questa architettura, descritta per la prima volta in un influente rapporto del 1945 intitolato "First Draft of a Report on the EDVAC", introduce alcuni principi fondamentali che ancora oggi definiscono la struttura dei nostri computer:

Unità di elaborazione centrale (CPU): Il "cervello" del computer, responsabile dell'esecuzione delle istruzioni. La CPU è ulteriormente suddivisa in: Unità di controllo (CU): Recupera le istruzioni dalla memoria, le decodifica e genera i segnali di controllo necessari per coordinare le altre componenti del sistema. Unità aritmetico-logica (ALU): Esegue le operazioni aritmetiche (addizione, sottrazione, moltiplicazione, divisione) e logiche (AND, OR, NOT) sui dati.
Unità di controllo (CU): Recupera le istruzioni dalla memoria, le decodifica e genera i segnali di controllo necessari per coordinare le altre componenti del sistema.
Unità aritmetico-logica (ALU): Esegue le operazioni aritmetiche (addizione, sottrazione, moltiplicazione, divisione) e logiche (AND, OR, NOT) sui dati.
Memoria: Utilizzata per memorizzare sia i dati da elaborare che le istruzioni del programma. Questa memoria è concettualmente organizzata come una sequenza di locazioni, ognuna identificata da un indirizzo univoco. La memoria consente l'accesso diretto a qualsiasi locazione in un tempo relativamente costante (memoria ad accesso casuale o RAM).
Dispositivi di input/output (I/O): Permettono al computer di interagire con il mondo esterno. I dispositivi di input consentono di inserire dati e comandi nel computer (ad esempio, tastiera, mouse), mentre i dispositivi di output permettono di visualizzare o trasmettere i risultati dell'elaborazione (ad esempio, monitor, stampante).
Bus: Un sistema di conduttori (fili o tracce su un circuito stampato) che funge da via di comunicazione tra le diverse componenti del sistema. Solitamente si distinguono tre tipi principali di bus: Bus dati: Trasporta i dati tra la CPU, la memoria e i dispositivi I/O. Bus indirizzi: Specifica l'indirizzo di memoria o del dispositivo I/O a cui si sta accedendo. Bus di controllo: Trasporta segnali di controllo che coordinano le operazioni tra le diverse componenti.
Bus dati: Trasporta i dati tra la CPU, la memoria e i dispositivi I/O.
Bus indirizzi: Specifica l'indirizzo di memoria o del dispositivo I/O a cui si sta accedendo.
Bus di controllo: Trasporta segnali di controllo che coordinano le operazioni tra le diverse componenti.

Un elemento concettuale fondamentale dell'architettura di von Neumann è il concetto di programma memorizzato. Ciò significa che sia le istruzioni del programma che i dati su cui operano sono memorizzati nella stessa memoria. Questa idea, apparentemente semplice, ha rappresentato una svolta cruciale rispetto ai primi calcolatori, dove le istruzioni erano spesso cablate direttamente nell'hardware o memorizzate su supporti separati.

Il programma memorizzato offre una flessibilità enorme, in quanto permette di cambiare il comportamento del computer semplicemente caricando un nuovo programma in memoria. Permette anche di trattare le istruzioni come dati, aprendo la strada a tecniche avanzate come la modifica di codice durante l'esecuzione.

Sebbene l'architettura di von Neumann sia stata incredibilmente influente e sia alla base della maggior parte dei computer che utilizziamo oggi, presenta anche alcune limitazioni intrinseche. La più nota è il collo di bottiglia di von Neumann. Poiché sia i dati che le istruzioni devono transitare attraverso lo stesso bus di memoria, la velocità di esecuzione del processore può essere limitata dalla velocità con cui i dati e le istruzioni possono essere recuperati dalla memoria. Per superare questa limitazione, sono state sviluppate diverse tecniche, come l'utilizzo di memorie cache e architetture alternative. Un'architettura alternativa significativa è l'architettura Harvard, utilizzata in alcuni sistemi specializzati come i processori di segnale digitale (DSP), che separa fisicamente la memoria per le istruzioni da quella per i dati, permettendo di accedere a entrambi contemporaneamente.

1.3 La Teoria dell'Informazione di Shannon:
Misurare l'Incertezza

Contemporaneamente allo sviluppo dei primi computer e alla formalizzazione dei modelli computazionali, il lavoro pionieristico di Claude Shannon sulla teoria dell'informazione, pubblicato nel suo fondamentale articolo del 1948 "A Mathematical Theory of Communication", ha fornito un quadro teorico rigoroso per quantificare e comprendere il concetto di informazione. Questo lavoro ha avuto un impatto profondo non solo sull'informatica, ma anche sull'ingegneria delle telecomunicazioni e su molti altri campi.

Shannon definì l'informazione in termini di riduzione dell'incertezza. In altre parole, l'informazione contenuta in un messaggio è proporzionale alla sorpresa che esso genera. Quanto più un evento o un messaggio è inaspettato, tanto più informazione esso veicola. Per quantificare questa idea, Shannon introdusse l'unità fondamentale di informazione: il bit (binary digit). Un bit rappresenta la quantità di informazione necessaria per risolvere un'incertezza tra due alternative equiprobabili (ad esempio, il risultato del lancio di una moneta).

Matematicamente, la quantità di informazione (H) di un evento con probabilità p di accadere è definita come:

H = -log₂(p)

Dove il logaritmo è in base 2, riflettendo la natura binaria del bit.

La teoria dell'informazione di Shannon ha fornito gli strumenti matematici fondamentali per:

Misurare la quantità di informazione contenuta in una sorgente di dati o in un messaggio. Questo ha permesso di definire la capacità massima di un canale di comunicazione (il cosiddetto teorema di Shannon-Hartley).
Comprendere i limiti teorici della compressione dei dati. La teoria di Shannon stabilisce un limite inferiore alla dimensione a cui un insieme di dati può essere compresso senza perdita di informazione (entropia).
Progettare sistemi di comunicazione affidabili anche in presenza di rumore o interferenze. La teoria dei codici correttori di errore, sviluppata a partire dal lavoro di Shannon, permette di aggiungere ridondanza ai dati trasmessi in modo da poter rilevare e correggere gli errori introdotti dal canale di comunicazione.

Il concetto di bit, derivato dalla teoria di Shannon, è diventato l'unità fondamentale per rappresentare e manipolare l'informazione all'interno dei sistemi informatici. Ogni dato, ogni istruzione, ogni immagine o suono all'interno di un computer è, in ultima analisi, codificato come una sequenza di bit.

I modelli computazionali di Turing e von Neumann, insieme alla teoria dell'informazione di Shannon, rappresentano i pilastri teorici su cui si è costruito e continua a evolversi il campo dell'informatica. La Macchina di Turing ha fornito una definizione formale di calcolabilità e ha permesso di esplorare i limiti del calcolo algoritmico. L'architettura di von Neumann ha offerto un progetto pratico e flessibile per la realizzazione dei computer elettronici, che ha dominato l'industria per decenni.

Infine, la teoria dell'informazione di Shannon ha fornito un quadro matematico per comprendere e gestire l'informazione, elemento centrale di qualsiasi sistema informatico. La comprensione di questi concetti fondamentali è non solo essenziale per gli studenti di informatica, ma offre anche una prospettiva profonda sulle radici intellettuali di questa disciplina che continua a trasformare il nostro mondo.