Non molto successivamente a Gödel, appare sulla scena Alan M. Turing, il quale contempla la questione della decisione in termini ancora più basilari ed estremi. L’idea fondamentale alla base della rivoluzione inaugurata da Turing è che se le operazioni logico-matematiche sono di per sé meccaniche, non ci sarebbe dovuto essere nessun problema, almeno a livello teorico, per sostituire la mente umana con un dispositivo meccanico. Il lavoro di Turing rappresenta quindi la prima descrizione concettuale astratta di un computer digitale come lo intendiamo ad oggi, nel suo articolo del 193680 definisce
quello che lui chiama un ‘a’ computer per automatico, che ha preso poi il nome di macchina di Turing.
Cercando di capire e definire quali sono i passaggi che si compiono du- rante lo svolgimento delle operazioni, Turing si è immaginato un potenziale operatore umano che applica una serie di istruzioni sui dati iniziali e che si appunta su un foglio i risultati intermedi dei calcoli. Turing argomenta sul fatto che la mente dell’operatore si può trovare solo in un numero finito di stati, ovvero può distinguere solo un numero finito di simboli e può scrivere solo finiti simboli. Da ciò possiamo concludere che l’operatore, interpretato in questo senso, è una specie di automata con un numero finito di stati possi- bili, almeno finché si considera lo svolgimento di algoritmi. Il foglio di carta su cui segnare i risultati intermedi delle operazioni può essere pensato come un nastro di carta lineare e illimitato, diviso in caselle, ognuna delle quali contiene un simbolo di un alfabeto finito. L’operatore a questo punto è in
grado di leggere o scrivere i simboli su una cella del nastro e traslare il nastro una cella a destra o a sinistra, mentre i dati iniziali vengono quindi scritti sul nastro in un numero finito di celle. Il calcolo è finito quando l’operatore entra nella modalità ‘la computazione è finita’, che verrà chiamata lo stato di halt o di fermo.
Abbiamo visto quindi come un operatore umano che esegue un algoritmo può essere modellato da una macchina di Turing con un singolo nastro di memoria. Per un problema di decisione possiamo supporre che lo stato ‘men- tale’ corrispondente allo stato di halt della macchina, contenga la risposta al problema posto. Risulta importante sottolineare che una computazione eseguita su una macchina di Turing può avere solo tre risultati: ‘Si’, ‘No’ o ‘nessuna risposta’ (ovvero la macchina non raggiunge lo stato di halt). Quella che si è andata definendo negli anni trenta è stata la nozione di ‘funzione com- putabile’; una funzione f si dice computabile se esiste una macchina M81tale
che:
i) f(x) è definita ⇒ M termina, con input x, con l’output f(x); ii) f(x) è indefinita ⇒ M non termina mai con input x.
Credo valga la pena a questo punto rimarcare la relazione che intercorre tra i sistemi formali, di cui abbiamo parlato sopra, e le macchine di Turing. Iniziano entrambi dalle stesse condizioni iniziali (assiomi da una parte e input data dall’altra), portano entrambi a compimento una serie finita di operazioni meccaniche (regole logico-matematiche e istruzioni algoritmiche), producono
81Si dovrebbe specificare anche la classe di macchine che sono qui intese, ed ovviamente
entrambi risultati (teoremi e output), e conducono entrambi a espressioni che sono indecidibili (espressioni non dimostrabili che sono vere e numeri incomputabili). Questa analogia è rispecchiata da un’equivalenza formale tra computazione e logica formale82, conseguentemente nel resto della trattazione
useremo indimostrabile e incomputabile intercambiabilmente.
Turing conferma la sensatezza della sua definizione, dimostrando come anche dei modelli leggermente diversi, ad esempio macchine con due nastri di memoria, hanno le stesse capacità delle classiche macchine di Turing. A partire da questa considerazione è però venuta alla luce una delle idee più proficue della storia, ovvero la dimostrazione che esiste una ‘a’ macchina la quale è capace di leggere altre ‘a’ macchine e comportarsi come farebbero loro rispetto ad un determinato input s. Questa macchina di Turing univer- sale, Mu, permette di convertire in modo effettivo ogni coppia (macchina di
Turing e input), 〈M, s〉, in un nuovo input su per la macchina universale, che
preserva il risultato, ‘si’, ‘no’ o ‘non si arresta’, della macchina M. In questo modo si era dimostrato, almeno teoricamente, che non era necessario costru- ire una nuova macchina per ogni nuovo compito da assegnarli ma che era semplicemente sufficiente una macchina che potesse essere riprogrammata.83
Questo in un certo senso ha cancellato la differenza tra hardware e software, come quella tra programmi e dati, in quanto si può facilmente codificare dei dati in un programma da far eseguire ad un’altra macchina di Turing, allo stesso identico modo di come si può sempre costruire una macchina univer-
82Come descritta da Penrose [Pen94], pp. 64-66.
83Nel suo articolo del 1936, Turing, non solo ha definito le basi di quello che conosciamo
ad oggi come personal computer ma anche del software e della programmazione, perciò credo si possa affermare con sicurezza che, ancora ad oggi, il suo contributo rappresenta la migliore risposta alla domanda: che cos’è un algoritmo?
sale che esegua un programma. Da questo risultato Turing inoltre riuscì ad intuire che ci sarebbero state macchine di Turing che non avrebbero potuto dare una risposta certa, ovvero il programma non si sarebbe arrestato mai. Se una macchina di Turing è universale e quindi capace di simulare qualsiasi altra macchina, era previsto che non si sarebbe mai arrestata per un deter- minato tipo di input e che invece si sarebbe arrestata per altri. Questo era esattamente cosa Turing si aspettava, dati i risultati di Gödel e quello che egli aveva voluto dimostrare: che la assiomatizzazione di Hilbert era impossibile. Questo risultato è quello che ha preso il nome di indecidibilità del problema dell’arresto o anche l’Halting Theorem. Informalmente possiamo riformulare il teorema dicendo che, dato un input iniziale s e un programma P per una determinata macchina di Turing M1, non può esistere una macchina M2,
tale che ci dica se il programma P eseguito sulla macchina M1 si arresta,
producendo un output, o no.
Dobbiamo tenere anche presente che, al contrario delle presenti inno- vazioni che spesso derivano da una scoperta tecnologica già acquisita, la nascita del computer ha avuto prima una lunga gestazione puramente teor- ica. In particolare infatti, basti pensare al fatto che una macchina universale, che può compiere qualsiasi tipo di computazione, è risultata essere tecnologi- camente realizzabile. In maniera molto approssimativa, questo risultato è stato ottenuto proprio grazie al fatto che la fisica del nostro mondo sup- porta la computazione: possiamo costruire congegni il cui comportamento è definito dalle leggi della fisica, ma che implementano una macchina di Tur- ing in senso molto ovvio. Ciò significa che per ogni area della matematica in cui il problema dell’Entscheidungs ha soluzione, possiamo costruire un
apparecchio fisico che risponde a tutte le domande possibili.
Vorrei concludere questa sezione con un citazione di D. Deutsch, che riassume, in maniera molto provocativa, la svolta determinata dall’avvento della computazione:
contrariamente a ciò che Hilbert ha pensato, e contrariamente a ciò che la maggior parte dei matematici fin dall’antichità hanno creduto e credono an- cora ad oggi, la teoria della dimostrazione non potrà mai essere resa una branca della matematica. La teoria della dimostrazione è scienza: specifi- catamente, è computer science.84 (...)
La possibilità di gestire gradi quantità di dati e manipolarli attraverso dei calcolatori è stato ciò che ha reso possibile all’uomo di espandere la sua capacità di previsione e di accuratezza della scienza. La rivoluzione iniziata dall’informatica ha portato all’avvento di quella branca della scienza che ad oggi si è rivelata essere una delle più promettenti: la teoria della complessità.
5
Teorie della complessità
Il termine ‘complessità’ ha un’origine etimologica latina rintracciabile nella parola plexus, che significa intrecciato. Ciò rende già l’idea intuitiva che sta alla base del concetto di complesso, ovvero qualcosa composto da ele- menti che sono difficili da separare, e questa difficoltà sorge proprio dalle interazioni che ci sono tra i suddetti componenti. Si può già cogliere, an- che se ancora in maniera superficiale, come questa difficoltà o impossibilità di separare gli elementi costitutivi è in contrasto con il metodo scientifico
classico, quello che abbiamo discusso nella sezione precedente. Tuttavia, è proprio grazie a questa tensione che i limiti del riduzionismo sono venuti a galla: nel momento in cui le interazioni tra i componenti diventano rilevanti, un modello riduzionista non è più adatto per studiare i fenomeni cosiddetti complessi. Negli ultimi decenni, lo studio accademico della complessità e dei sistemi complessi ha proposto, a mia opinione, un cambio di paradigma per la scienza e la filosofia proponendo nuovi metodi di simulare e pensare ai modelli della natura stessa.
Intorno agli anni ottanta del ventesimo secolo venne proposto un nuovo approccio tipicamente chiamato, scienza della complessità.85 Le radici dell’
approccio alla complessità sono svariate, ne riportiamo solo alcune a scopo esplicativo:
• dinamiche non lineari e meccanica statistica, due diramazioni della mec- canica newtoniana che hanno dimostrato come per modellare sistemi più complessi erano richiesti nuovi strumenti matematici che potessero fare i conti con il random e il caos;
• informatica, che ha reso possibile la simulazione di sistemi che erano o troppo grandi o troppo complessi per crearci un modello matematico; • evoluzione biologica, che spiega l’apparizione di forme complesse at-
traverso quei meccanismi intrinsecamente imprevedibili come la vari- azione casuale e la selezione naturale;
• infine anche l’applicazione di tutti questi metodi per descrivere i sistemi sociali in un senso ampio, come i mercati azionari, internet o colonie
di insetti, dove non c’è un ordine prestabilito, eppure emergono delle strutture ordinate.
In un’ampia e comprensiva presentazione del ruolo che il concetto di com- plessità assume nello sviluppo delle scienze moderne, leggiamo: "La comp- lessità determina lo spirito della scienza del ventunesimo secolo. L’espansione dell’universo, l’evoluzione della vita, e la globalizzazione delle economie e so- cietà umane comportano tutti transizioni di fase di sistemi dinamici comp- lessi."86 L’autore si spinge anche oltre dicendo che:
La teoria dei sistemi complessi non-lineari è divenuta un approccio vincente per la risoluzione dei problemi delle scienze naturali - dalla fisica dei laser, caos quantistico e meteorologia, ai modelli delle molecole in chimica e simu- lazioni di crescita cellulare assistite dal computer. Dall’altra parte, le scienze sociali hanno riconosciuto che i problemi fondamentali dell’umanità sono globali, complessi, non-lineari, e spesso, anche randomici. Cambiamenti lo- cali nel sistema ecologico, economico, o politico possono causare crisi globali. Il pensiero lineare e la convinzione che il tutto sia solo la somma delle parti sono evidentemente obsoleti.87
In effetti la complessità è diventata non solo un argomento importante per la ricerca, ma anche una chiave di spiegazione scientifica per tutte le aree della scienza. Questo non implica assolutamente che si sia raggiunta una sorta di chiarezza concettuale per la questione della complessità. Anzi, dato il nostro passato scientifico dominato dalla visione riduzionista, la maggior parte dei ricercatori sulla complessità non hanno ancora riflettuto sui fonda- menti filosofici del loro nuovo approccio. Si potrebbe dire, a buon ragione, che siamo di fronte ad una scienza ancora nelle sue fasce.
86[Mai07], p. VII. Traduzione mia. 87[Mai07], p. 1. Traduzione mia.
Ciò che però contraddistingue lo studio della complessità è il suo inter- esse per quei fenomeni che non sono caratterizzati né dall’ordine, come quelli studiati dalla meccanica newtoniana, ma nemmeno dal disordine, come quei fenomeni analizzati dalla meccanica statistica, ma sono situati a metà strada, in quella zona che viene spesso definita l’orlo del caos.88 I sistemi ordinati,
come quelli dei cristalli, sono caratterizzati dal fatto che i componenti obbe- discono a regole rigide che specificano come ognuno dei componenti dipende dagli altri. I sistemi disordinati, come i gas, consistono di componenti che sono totalmente indipendenti, agendo senza vincoli. In questo senso l’ordine è facile da modellare, dato che possiamo predire tutto, una volta conosciute le condizioni iniziali e i vincoli. Il disordine però è anch’esso semplice, anzi troppo, perché nonostante non possiamo predire il comportamento del singolo componente, l’indipendenza statistica implica che possiamo accuratamente predire il loro comportamento medio.
Ma cosa sono i sistemi complessi? Anche se una definizione formale è dif- ficile da raggiungere e non può non ricorrere all’utilizzo di tecnicismi matem- atici, possiamo comunque vedere esempi di sistemi complessi praticamente ovunque in natura; dalla turbolenza dei fluidi, ai modelli globali di meteorolo- gia, fino alle intricate strutture galattiche e alla complessità degli organismi viventi. Tutti questi sistemi condividono almeno questa proprietà: sono tutti composti da un vasto assemblamento di parti interconnesse e che interagis- cono, tipicamente non-linearmente, tra di loro. Come se non bastasse, il loro comportamento complessivo risultante è emergente, in quanto le proprietà del sistema non sono possedute da, ma nemmeno derivabili da, nessuna delle
sue parti prese separatamente: molto banalmente, una molecola d’acqua non è un vortice tanto quanto un neurone non è cosciente. Un sistema complesso dovrà quindi essere compreso non solo in termini dell’insieme di componenti da cui è costituito, ma anche dalla topologia delle interconnessioni e inter- azioni tra questi componenti.
Questa nuova scienza della complessità emergente esplora la questione importante di in che misura il comportamento dei più disparati sistemi com- plessi che ritrovano in natura, da quelli in scala molto piccola a quelli in scala macroscopica, scaturisce dallo stesso fondamentale insieme di principi universali.
Vorrei concludere questa breve introduzione con un’osservazione che ritengo rilevante rispetto alla presente argomentazione. C’è una sorta di discorso au- toreferenziale nel nostro tentativo di capire come ‘fare’ scienza dei sistemi complessi che è tanto interessante quanto estremamente pericoloso. Anche se usare le strutture e i linguaggi della scienza della complessità è probabil- mente inevitabile, farlo da adito ad un elemento autoreferenziale che sembra quanto meno sospetto in quanto analogo all’approccio della meta-matematica alla matematica. Questo tipo di approccio aprirebbe le porte ad una specie di gödelizazzione delle scienze dei sistemi complessi, che si potrebbe nascondere dietro anche a qualsiasi nostro tentativo di comprendere e classificare questi sistemi. Prima di segnalare una falla nel nostro ragionamento, questo fatto potrebbe costituire il marchio di riconoscimento dei sistemi complessi.89
5.1
Complessità computazionale
Uno dei primi scienziati a sviluppare più pragmaticamente le intuizioni di Alan Turing è stato sicuramente John Von Neumann, un matematico, fisico e informatico Ungaro-Americano della prima metà del ventesimo secolo. Von Neumann si interessò al lavoro di Turing sulle macchine automatiche, in cui le operazioni della macchina potevano essere scritte sotto forma di un programma, e fu lui il primo, all’interno della sua vasta area di ricerca, a dare vita al progetto di Turing creando il primo concreto calcolatore universale chiamato EDSAC, Electronic Delay Storage Automatic Calculator.90 Una
delle prime considerazioni fu che la macchina sarebbe dovuta essere integrata con della memoria vuota, per poter contenere le informazioni del programma, inoltre avrebbe dovuto essere provvisto di una unità logica e aritmetica per eseguire le istruzioni contenute nel programma. Il computer a quel punto non farà altro che eseguire un insieme di operazioni, con dei dati come input, e rispondere a domande complesse.
Per cogliere meglio questa totale rivoluzione ci basta pensare che prima dell’avvento dei calcolatori universali, i computer venivano progettati speci- ficatamente per un determinato compito, il che significava che ogni volta che si voleva modificare il programma, erano necessarie delle modifiche nel cablaggio interno delle porte logiche. Poter eseguire qualsiasi programma con lo stesso hardware di base, con lo stesso cablaggio interno è stato sicuramente il proto-progetto della nostra era digitale.
Nonostante tutti promettenti successi tecnologici, ci si rese subito conto
che si sarebbe andati incontro ai soliti limiti che hanno ancora ad oggi le nostre macchine da computazione, il tempo e lo spazio, o meglio, la memoria; quest’ultima però non era di grande preoccupazione per gli scienziati, almeno non quanto lo fosse la questione del tempo richiesto per eseguire tutte la serie di operazioni richieste per rispondere a domande sempre più complesse. Una delle persone che ha meglio articolato la questione molto precocemente è stato il matematico John Nash, il quale, in una lettera declassificata alla National Security Agency americana del 1955, si era preoccupato dei requisiti computazionali per certi tipi di problemi, nel suo caso particolare riguardava gli algoritmi di decodifica, ma la sua intuizione fu molto più generale e di profondo impatto. Nash propose di pensare non al tempo richiesto a calcolare un qualsiasi esempio particolare di un problema, come ad esempio il tempo richiesto a sommare due numeri da 4 cifre ciascuno, ma piuttosto di vedere come le richieste computazionali si relazionino all’aumento della grandezza dell’input. Inoltre, invece di misurare il tempo in base ai secondi richiesti si deve tenere di conto del numero di operazioni, o passaggi richiesti dalla macchina per risolvere il problema.
Ovvero, riprendendo il nostro esempio della somma, per capire la comp- lessità di un problema dovremo guardare a quante operazioni o passaggi sono richiesti per sommare due numeri da due cifre, rispetto che a due numeri da tre cifre, che da quattro, da cinque e così via.. Inserendo questi dati in un grafico otteniamo una curva che ci descrive il numero di operazioni che una qualsiasi macchina deve eseguire, rispetto alla dimensione dell’input della domanda che aumenta. È stata proprio la forma di questa curva a diventare un modo significativo di parlare della complessità di un problema. Intuiti-
vamente possiamo pensare che se paragoniamo le operazioni di addizione e moltiplicazione, la curva relativa alla moltiplicazione sarà più ripida e quindi richiederà più operazioni o passaggi per arrivare alla soluzione, a parità di grandezza dell’input.91
Perché la curva che descrive alcuni tipi di problemi risulta essere più ripida di altre? Questa domanda ha certamente guidato lo studio della com- plessità computazionale e cercheremo qui di rendere un’idea della ragione, o se vogliamo dell’origine, della complessità dei problemi. Per capire il mo- tivo di questo aumento asimmetrico della complessità dei problemi dobbiamo tenere presente la possibilità che siano presenti dei loop, o cicli, nell’algoritmo addetto alla risoluzione, qualcosa della forma generale: ‘fai X, n volte’.92
Figure 2: Un esempio di ciclo lineare.
In questo caso vediamo come il numero di passaggi in un loop di questo genere dipenderà dalla dimensione dell’input n; se inseriamo questi dati in un grafico del numero di passaggi rispetto alla grandezza dell’input vediamo
91Vedi fig. 3. 92Vedi fig.2.
come c’è una corrispondenza o una crescita lineare.93
Figure 3: Complessità computazionale di addizione e moltiplicazione.
La questione però si complica subito, in quanto alcuni problemi più com- plessi richiedono algoritmi che, per trovare la soluzione, contengono al loro interno dei loop all’interno di altri loop, anche definiti cicli annidati. Non importa andare a pensare a cose molto complesse in realtà, se ci pensiamo bene compiamo un ciclo annidato ogni volta che andiamo a fare la spesa con la lista scritta sul biglietto: nel primo loop andiamo a controllare tutti gli elementi della nostra lista, ma successivamente, per ogni elemento nel primo loop compiamo un secondo loop, ovvero controlliamo il nostro carrello finché non troviamo quell’oggetto. Ciò implica che se la nostra lista della spesa contiene n elementi, potrebbe richiedere n × n o n2 passaggi. Se andiamo
ad inserire questa formula in un grafico otteniamo una curva, che nel nostro caso particolare potrebbe essere descritta dall’equazione n2, ma se il loop
fosse annidato più di due volte allora l’esponente crescerebbe di uno per ogni