Off-line del 20 maggio 1998

Introduzione ai nuovi media 2/a.
Il computer

di Gino Roncaglia

Nella prima lezione, abbiamo visto come tipi diversi di informazione - dal testo scritto ai suoni e alle immagini - possano essere convertiti in formato digitale, e cioè in lunghe catene di 0 e 1. Ma perché questa conversione si rivela tanto vantaggiosa? Perché disponiamo di strumenti capaci di immagazzinare, manipolare e trasmettere con grande rapidità ed efficienza proprio queste catene di 0 e 1. Si tratta degli strumenti che ci vengono forniti dall'informatica e dalla telematica.

L'informatica è la scienza che si occupa del trattamento automatico dell'informazione. E' all'informatica che dobbiamo i computer. Senza la rivoluzione informatica, la possibilità di convertire informazione analogica in informazione digitale rappresenterebbe poco più che una curiosità teorica.

La telematica, a sua volta, permette di usare gli strumenti informatici, oltre che per elaborare l'informazione, anche come veri e propri mezzi di comunicazione.

Il computer, come si è detto, è alla base di tutto questo. E' importante quindi capire, almeno a grandi linee, cos'è un computer, e come funziona. E' il compito che cercheremo di affrontare in questa lezione.

La parola inglese computer deriva da computation, ovvero computazione, calcolo; il termine italiano calcolatore rimanda anch'esso direttamente all'idea di calcolo. E il computer è in effetti una macchina nata per eseguire computazioni, calcoli.

Attenzione, però: noi abbiamo spesso l'idea - sbagliata - che un calcoilo o una computazione siano operazioni che possano riguardare escludivamente numeri. E abbiamo di conseguenza l'idea - anch'essa sbagliata - che il computer sia unicamente una macchina per maneggiare numeri.

In realtà, l'idea di computazione è più generale. Ogni processo di manipolazione di simboli che parta da una serie di dati iniziali, li modifichi - e cioè li elabori - in base a regole prefissate, e ci fornisca il risultato di queste modifiche, può essere considerato, in senso astratto, come una computazione.

Così, ad esempio, la somma di due numeri è una computazione: i dati iniziali sono i numeri che sommiamo, le regole da seguire sono quelle, familiari, dell'aritmetica, e il risultato sarà il numero che corrisponde alla somma dei due numeri di partenza.

Ma anche l'ordinamento alfabetico di un elenco di parole, e cioè l'operazione che si fa ad esempio per realizzare l'indice di un libro, è una computazione. In questo caso, i dati di partenza saranno costituiti da una serie di parole disordinate, le regole ci forniranno un procedimento dettagliato per ordinarle, e il risultato sarà il nostro bell'indice in ordine alfabetico.

In sostanza, dunque, la computazione ha a che fare con una modificazione di stato: si parte da uno stato iniziale, rappresentato dai nostri dati di partenza, si passa in genere attraverso stati intermedi corrispondenti alla progressiva applicazione delle regole di manipolazione dei simboli, e si arriva allo stato finale che ci fornisce il rislutato del processo.

I tentativi di costruire macchine capaci di svolgere computazioni in modo automatico o quasi automatico non sono una novità del nostro secolo. In fondo, rientra in questa categoria già il pallottoliere, una invenzione araba.

Questa che vedete alle mie spalle è invece una macchina calcolatrice costruita alla fine del '600 da Leibniz, il grande filosofo e matematico tedesco al quale dobbiamo anche le prime riflessioni sul calcolo binario.

Ecco un'altra delle macchine di Leibniz - questa poteva eseguire anche semplici moltiplicazioni.

Ma alla radice dei computer contemporanei non sono solo solo macchine da calcolo 'fisiche' come quelle di Leibniz o, prima di lui, di Pascal: sono anche macchine 'ideali', progetti puramente teorici, come la macchina analitica di Babbage, di cui potete leggere nelle dispense, o la macchina di Turing, di cui parleremo adesso.

E' possibile dare una definizione matematica adeguata per il concetto generale di computer, una definizione capace di catturare tutti gli esempi di computer possibili, che siano realizzabili oggi e domani con qualunque tipo di tecnologia? Le macchine di Turing sono proprio questo. Sono un modello matematico ideale che vuole catturare tutti gli esempi di computer possibili. Gli ingredienti che intervengono in una macchina di Turing sono molto semplici. Prima di tutto abbiamo un nastro, potenzialmente infinito. Questo nastro è diviso in maniera discreta in caselle e calcolare attraverso una macchina di Turing significa spostarsi su questo nastro, avendo la possibilità di leggere quello che sta scritto nelle caselle e di stampare, cancellare simboli, passando successivamente in stati di memoria diversi. Quando la macchina di Turing esegue un calcolo per un'operazione o per una funzione matematica, dopo un certo numero finito di passi si ferma, esattamente come fanno i nostri personal computer. Ora un problema teorico molto importante che nasce a questo proposito è il seguente: tutte le volte che noi sottoponiamo un calcolo alla nostra macchina di Turing, la macchina si fermerà? Bene, questa domanda ha una risposta negativa. Come hanno dimostrato Turing e il logico Kurt Gödel, vi sono delle funzioni matematiche che non sono computabili in un numero finito di passi da una macchina di Turing. Questo significa che in certi casi particolari la nostra macchina di Turing può non fermarsi, può andare avanti all'infinito.

Ecco una macchina di Turing, con la quale potete fare esperimenti voi stessi, dato che si tratta di un programma che troverete sia sul nostro CD-ROM, sia su Internet.

Come abbiamo detto, la macchina di Turing è innanzitutto una costruzione concettuale, una macchina teorica. La immaginiamo costituita da tre elementi.

Il primo è un nastro di lunghezza infinita, questo, suddiviso in tante piccole cellette. Ogni celletta può contenere un simbolo, ad esempio uno 0 o un 1.

Il secondo elemento che costituisce la macchina di Turing è una testina di lettura/scrittura, questa. La testina è capace di muoversi avanti e indietro lungo il nastro, una cella alla volta. Può inoltre leggere il contenuto della cella su cui si trova, e, volendo, modificarlo.

Il terzo elemento è un insieme di regole che definiscono le situazioni - ovvero gli stati - in cui la testina si può trovare, e le azioni che deve compiere. Ad esempio, una regola potrebbe dire alla testina che se si trova su una casella 0 deve trasformare lo 0 in 1, spostarsi di un passo a destra, e passare ad eseguire la regola successiva.

Ebbene, sembra impossibile ma una macchina di questo tipo, dalle componenti apparentemente così semplici, è in grado di eseguire TUTTE le computazioni che può compiere il migliore dei nostri computer - almeno, dei computer che conosciamo fino ad oggi. Tanto che una definizione di 'computabilità' potrebbe essere proprio questa: è computabile tutto quello che una macchina di Turing può computare.

Ma vediamo cosa succede quando avviamo la macchina. In questo momento, questa particolare macchina sta sommando due numeri e scrivendo il risultato. Come vedete la testina legge, scrive e si muove lungo il nastro. Lo fa seguendo un insieme di regole, queste.

E' un esempio che, assieme a diversi altri, potete sperimentare voi stessi, con l'aiuto delle dispense e del programma contenuto nel CD-ROM.

Naturalmente una somma è una operazione molto semplice - ma come si è detto la macchina di Turing può compiere computazioni anche molto più complicate. Solo che più è complicata l'operazione, più complicato sarà l'insieme di regole che la macchina deve seguire, e più passi saranno necessari per eseguirla.

I computer che conosciamo funzionano in maniera abbastanza simile a una macchina di Turing, anche se al posto del nastro infinito - evidentemente non realizzabile in realtà - ci sono i cosiddetti registri, ovvero un certo numero di gruppi di celle che, al solito, possono contenete i nostri '0' e '1'.

Un problema importante è il seguente: saremo un giorno in grado di costruire un computer, un robot intelligente, capace di andare oltre i limiti delle macchine di Turing? Ora, le macchine di Turing possono essere equivalentemente sostituite da una macchina a registri, non c'è una differenza in linea di principio tra macchina di Turing e macchina a registri, quindi parlare dei limiti delle macchine di Turing significa parlare dei limiti delle macchine a registri. Ora c'è una tesi molto importante, la tesi di Church-Turing, che dice questo: non andremo mai oltre i limiti delle macchine di Turing, perché calcolare significa calcolare attraverso una macchina di Turing. Naturalmente una tesi come questa è difficilmente dimostrabile, perché non si tratta di un teorema matematico. La tesi di Church-Turing paragona un concetto intuitivo un po' ambiguo con un concetto matematico preciso, il concetto di macchina di Turing.

vai alla seconda parte