|
||||||
DOCUMENTS
elab.immagini
galileo
realtà virtuale
vrml
biomeccanica
esapodi
formula1
intelligenza
Papers
meccanica
sistemi
robotica
IL SOGNO DI LEIBNIZ
Con questa espressione ("il sogno di Leibniz"), Giuseppe Peano, "il maestro del pensiero formale", battezzò, nel 1898 (Formulario, II, 2, Cremonese, Roma, 1960), la prima formulazione, in Leibniz, di "uno dei più meraviglioso programmi di ricerca progressivi nella storia della conoscenza umana, la logica matematica".
(I. Lakatos, Scritti, II, Il Saggiatore, Milano, 1985, p. 304 n)
Lasciamolo raccontare
a Leibniz stesso:
"Studiando questo problema [di logica], arrivai come spinto da una necessità
interna a questa idea straordinaria: che doveva essere possibile costruire
una caratteristica universale della ragione, mediante la quale, in qualsiasi
dominio, tutte le verità si presenterebbero alla ragione in virtù di un
metodo di calcolo, come nell'aritmetica o nell'algebra.
Di conseguenza, quando sorgeranno controversie tra due filosofi, non sarà
più necessaria una discussione; sarà sufficiente infatti che prendano
in mano le penne, si siedano di fronte agli abachi e si dicano l'un l'altro:
calculemus!".
(in I.M. Bochenski, A History of FonnalLogic, University of Notre Dame Press, Notre Dame, 1961, 38.07, 38.10)
Comprendendo tuttavia
che vaste zone della nostra conoscenza non si trovano, nelle parole di
Locke, "nella chiara luce del giorno", ma "nel crepuscolo della probabilità",
Leibniz comprese anche che per costruire una caratteristica universale
della ragione, non sarebbe stato sufficiente lo sviluppo di una macchina
deduttiva. Notava Leibniz nei Nuovi Saggi sull'Intelletto Umano:
"Merita forse anche il titolo di conoscenza l'opinione fondata sulla plausibilità;
altrimenti, verrebbe meno tutta la conoscenza storica, e non solo quella.
Per questo credo che la ricerca sui gradi di probabilità sia estremamente
importante; purtroppo ci manca ancora ed è questo un grave difetto delle
nostre logiche. Così, quando non si potesse decidere con assoluta certezza
una questione, si potrebbe almeno determinare il grado di probabilità
[delle varie soluzioni] alla luce dell'evidenza".
(Scritti Filosofici, UTET, Torino, 1967, pp. 502-3)
Era questa la prima formulazione
esplicita di un altro straordinario programma di ricerca progressivo,
la teoria classica della probabilità, o come diremo anche, il programma
di ricerca di Bayes-Laplace, in onore dei due matematici che più contribuirono
al suo sviluppo.
Implicita nel sogno di Leibniz era una generalizzazione di quello che
David Hilbert, forse il più geniale matematico a cavallo tra ’800 e ’900,
chiamò "assioma di risolubilità di ogni problema", e cioè, nelle parole
dello stesso Hilbert, la convinzione che "ogni problema matematico determinato
debba necessariamente essere passibile di una rigorosa sistemazione o
riuscendo a dare una risposta alla questione posta oppure dimostrando
l'impossibilità di una sua soluzione e quindi la necessità dell'insuccesso
di ogni tentativo".
(Ricerche sui Fondamenti della Matematica, Bibliopolis, Napoli, 1978, p. 153)
Molte sono state le conferme
di questa convinzione "metafisica" dopo il 1900; ma forse la più clamorosa
(ha avuto l'onore della prima pagina del "New York Times") e, ai nostri
effetti istruttiva, è venuta di recente con la soluzione positiva di un
durissimo problema: il problema dei quattro colori. Semplicissimo nella
sua formulazione, che risale al 1852, ogni carta geografica può essere
colorata in modo tale che ogni coppia di paesi confinanti ottenga colori
diversi, senza usare più di quattro colori, ha resistito fino al 1976
ad ogni tentativo di soluzione.
Oggi, la carta da lettere dell’Università dell'Illinois, a Urbana, porta
orgogliosamente il motto: quattro colori bastano, per celebrare i due
ricercatori di questa Università che l’hanno risolto: Kenneth Appel e
Wolfgang Haken.
(si veda ad esempio l'esposizione divulgativa dei due autori in L.A. Steen, a cura di, Mathematics Today, Springer, New York, 1978, pp. 153-190)
La conferma è istruttiva
per almeno due ragioni. In primo luogo, si tratta di un problema apparentemente
insignificante, nella pratica della cartografia era ben noto che quattro
colori bastano. La sua soluzione ha però richiesto parecchie migliaia
di ore di lavoro-uomo, ed esattamente mille ore di lavoro-calcolatore
su un calcolatore ultraveloce, un IBM 370/168; dunque, un costo relativamente
alto per la collettività. In secondo luogo, tale soluzione è basata in
modo ESSENZIALE sull'uso del calcolatore. Allora, è nell'interesse della
collettività dirottare risorse significative su questo tipo di problemi?
e che differenza fa alla pratica scientifica l'uso essenziale del calcolatore
nella soluzione dei problemi?
Alla prima questione diede implicitamente una risposta paradossale, ma
corretta, proprio Hilbert. Alla richiesta su quali risultati tecnologici
considerasse più urgenti, rispose: "Colpire una mosca sulla luna". Perché?
"Perché per ottenere un risultato del genere dovrebbero essere risolti
problemi tecnologici ausiliari che implicano una soluzione a quasi tutte
le difficoltà materiali dell'umanità".
(in C. Reid, Hilbert, Springer, New York, 1970, p. 92)
Il punto di Hilbert dovrebbe
essere chiaro, I. Lakatos, il grande allievo-rívale di Karl Popper, lo
ha riespresso più prosaicamente con la sua tesi dell'autonomia della scienza
pura: pretendere dalla scienza pura un impegno pianificato nella soluzione
diretta di problemi socialmente urgenti significa al tempo stesso bloccarne
lo sviluppo e lasciare quei problemi irrisolti; l'affare Lysenko esemplifica
bene questo punto.
La loro soluzione è invece (spesso)
una conseguenza collaterale imprevista dei sogni teorici più selvaggi.
Il sogno di Leibniz esemplifica bene questo secondo punto.
Abbiamo sottolineato che esso costituiva in nucleo di due programmi di
ricerca unificati dall'idea portante di una caratteristica universale
della ragione.
Il primo, la logica matematica, era volto alla meccanizzazione del ragionamento
deduttivo, mirava cioè alla costruzione di una macchina "deduttiva", capace
di rispondere ad ogni domanda della forma: è la proposizione A vera in
ogni situazione in cui sono vere le proposizioni B, C, D, ecc.?
Il secondo, la teoria classica della probabilità, era invece volto alla
meccanizzazione del ragionamento plausibile, mirava cioè alla costruzione
di una macchina "induttiva", capace di rispondere ad ogni domanda della
forma: qual è la probabilità della proposizione A alla luce delle proposizioni
B, C, D, ecc.
I due programmi di ricerca ebbero tempi di sviluppo assai diversi.
Il primo, la logica matematica, non decollò effettivamente che circa duecento
anni dopo, quando nel 1879 un altro ricercatore tedesco, largamente incompreso
dalla comunità scientifica del suo tempo, Gottlob Frege pubblicò il suo
Begriffßclgrift, o scrittura concettuale. Dal suo calcolo, dalla sua grande
logica, Frege si aspettava che fosse capace di generare la totalità delle
verità matematiche a partire da pochi principi elementari "ovvii", dando
così ad esse un fondamento ultimo indubitabile.
Come è noto, nel 1902 un giovane matematico inglese, Bertrand Russell
gli dimostrò in una breve lettera che tale fondamento era semplicemente
incoerente. Non era certo questo un buon inizio per il sogno "deduttivistico"
di Leibniz. Bertrand Russell, tuttavia, non disperò proseguendo nell'impresa.
Dopo dieci anni di duro lavoro con Whitehead, pubblicò nei Principia Mathematica
una revisione della Grande Logica di Frege apparentemente libera da antinomie.
Questa volta il ruolo del guastafeste lo svolse un giovane matematico
tedesco, Kurt Goedel, che nel 1931 dimostrò che il sistema dei Principia,
se è effettivamente libero da antinomie, se cioè è davvero coerente, allora
è essenzialmente incompleto; vi sono cioè problemi della forma: è la proposizione
A (del sistema) una conseguenza degli assiomi di Russell? cui è impossibile
rispondere SIA entro il sistema stesso sia entro ogni sua estensione coerente.
Si tratta del famoso teorema di incompletezza di Goedel reso ormai popolare
da Hofstadter nel suo Goedel, Escher, Bach.
Ma lasciamo per un momento in questo stato precario il sogno "deduttivistico"
di Leibniz e torniamo al suo sogno "probabilistico", e cioè al programma
di ricerca di Bayes-Laplace, alla teoria classica della probabilità. In
questo caso, i risultati vennero subito, e abbondanti. I Bernoulli, Bayes,
Gauss, Laplace sopra tutti, e molti altri, praticamente completarono tra
il 1700 e il 1820 una teoria del ragionamento plausibile, basata sulla
teoria classica della probabilità, che si applicava con grande successo
alla maggior parte dei problemi di inferenza scientifica, dalle scienze
fisiche fino alle scienze morali.
Ma a questo punto accade un fatto sorprendente, o per lo meno inconsueto
nella storia della scienza: nonostante il programma fosse manifestamente
progressivo, esso venne quasi del tutto abbandonato verso la fine dell"800,
non perché fosse disponibile un programma migliore, ma sulla base di pregiudizi
filosofici contro il suo principio portante, formulato dallo stesso Leibniz,
il principio di ragion insufficiente, o principio di indifferenza nella
formulazione di Laplace.
In breve, esso affermava che dobbiamo assegnare la stessa probabilità
a due eventi se non esistono ragioni per pensare altrimenti. Nonostante
la sua apparente innocenza, esso era certo particolarmente fertile di
paradossi nella sua applicazione a quantità casuali continue. Ma vuoti
slogan ideologici, a cominciare da j. Venn (1866), prevalsero su uno sforzo
più pacato di comprenderne le condizioni di applicabilità.
Così, se il sogno "deduttivistico" di Leibniz si trovava nel 1931 bloccato
da difficoltà "tecniche", intorno al 1900 quello "probabilistico" si trovò
bloccato da difficoltà "ideologiche".
A parte i geniali, ma isolati contributi negli anni ’30, di eretici come
gli inglesi Frank Plumpton Ramsey e Harold Jeffrey, e del nostro Bruno
de Finetti, il programma di ricerca di Bayes-Laplace riprese slancio solo
alla fine degli anni ’40, grazie, tra l'altro, a un teorema dimostrato
da uno statistico, Abraham Wald.
Come ha notato E.T. Jaynes, un altro grande protagonista di questi nuovi
sviluppi, "t una di quelle ironie che rendono interessante la storia della
scienza che la dimostrazione mancante di ottimalità per le regole di Bayes-Laplace,
che non era riuscita né a Laplace né a Jeffrey, venne alla fine trovata
inavvertitamente, nel tentativo di dimostrare l'opposto, da un ricercatore
[Wald, appunto] che in gioventù era stato un acceso seguace della teoria
[rivale] di von Mises".
"<Where Do We Stand on Maximum Entropy", in Papers in Probability, Statistics and Statistical Physics, a cura di R.D. Rosenkrantz, Reidel, Dordrecht, 1983, p. 222)
Da quel momento le applicazioni,
anche tecnologiche, interessanti, della costruzione di Bayes-Laplace si
sono moltiplicate ed è stato un vero trionfo per il principio di ragion
sufficiente di Leibniz, o più esattamente per il suo erede, il principio
di massima entropia.
Su di esso si basa ad esempio l'analisi spettrale delle serie temporali
in geofísica, di Burg e Shore, e il metodo di ricostruzione di immagini,
in ottica e radioastronomia, di Skillíng-Gull-Frieden.
In questo secondo caso i risultati sembrano addirittura magici: prendete
ad esempio una fotografia sfocata a cui l'occhio umano più addestrato
non riesce a dare alcuna interpretazione; datela a un calcolatore ultraveloce
programmato con il metodo di Skilling-Gull-Frieden, che elabora cioè i
dati forniti dalla fotografia sulla base dei metodi di Bayes-Laplace di
massima entropia e otterrete in breve tempo una fotografia intelligibile
dello scenario originale.
Un tempo, non lontano, i detrattori del principio, tra cui lo stesso Karl
Popper, usavano affermare sprezzantemente che si trattava di un metodo
per produrre conoscenza dall'ignoranza e concludevano che non poteva che
trattarsi di una ciarlataneria. Paradossalmente, avevano ragione: si tratta
proprio di un metodo per produrre conoscenza dall'ignoranza ma non si
tratta di ciarlataneria: non solo il metodo funziona ma siamo anche in
grado di spiegare perché.
Semplicemente, gli scenari selezionati dalle distribuzioni di massima
entropia hanno nella maggior parte dei problemi una probabilità di realizzarsi
incredibilmente superiore a quella di tutti gli scenari alternativi messi
insieme: nel caso di Skilling-Gull tale superiorità è dell'ordine di 1011.
Infine, più in generale, i metodi di Bayes-Laplace risultano oggi assai
promettenti per la meccanizzazione del ragionamento plausibile in vari
campi particolari, dalla chimica alla medicina alla geologia all'ingegneria,
e cioè per la costruzione dei così detti sistemi esperti, programmi capaci
di simulare con successo le competenze professionali degli esperti dei
campi corrispondenti. Qui, l'esempio migliore è in geologia con il programma
PROSPECTOR capace di determinare, sulla base di dati di varia natura,
le zone più favorevoli per le trivellazioni petrolifere, e molto altro
ancora.
Altri importanti sviluppi recenti del programma di Bayes-Laplace sono
venuti dalla sua estensione dal campo delle situazioni non competitive
a quello delle situazioni competitive, quelle cioè in cui l'esito finale
è determinato anche dalle valutazioni e decisioni di altri agenti intelligenti.
I modelli più semplici delle situazioni di questo secondo tipo sono naturalmente
i giochi da salotto come ad esempio la dama e gli scacchi. Di fatto, essi
costituirono il punto di partenza della prima teoria articolata per questa
classe di situazioni, quella di von Neumann e Morgenstern, nel loro monumentale
La teoria dei giochi e il comportamento economico, del 1944.
Tuttavia, era già chiaro ad entrambi che una vasta classe di reali situazioni
economiche e sociali di conflitto poteva essere modellizzata lungo queste
linee. La reinterpretazione e generalizzazione dei loro risultati sui
giochi a somma zero entro il programma di Bayes-Laplace è ancora in corso,
ma vedrà presto la luce in un volume da tempo annunciato, di John Harsanyi
dell'Università di California, a Berkeley e di Reinhard Selten dell'Università
di Bonn.
Già nel 1981 un ricercatore dell'Università di Stoccarda, Berndt Lutz
aveva costruito un programma per implementare su calcolatore parte della
teoria di Harsanyi-Selten. Questo implica la possibilità di simulare su
calcolatore una classe significativa di situazioni di conflitto economico
e sociale in modo da trovarne una soluzione ottimale, o almeno soddisfacente
in caso di eccessiva complessità computazionale, senza i costi connessi
alla soluzione "sul campo" di tali conflitti.
Infine, almeno in linea di principio, una analoga possibilità esiste anche
per le situazioni di tipo morale da quando a partire dagli anni ’50 lo
stesso Harsanyi ha dato rispettabilità scientifica al calcolo della felicità
di Jeremy Bentham. Non sto naturalmente sostenendo che non vi siano più
problemi aperti, sia di carattere filosofico che di carattere più strettamente
matematico che, infine, di carattere empirico. Al contrario.
Ma il sintomo certo che un programma è progressivo è proprio che la soluzione
di ogni problema dia luogo a nuovi innumerevoli problemi interessanti.
Qual è allora il bilancio del sogno "probabilistico" di Leibniz? Benché
anche in questo caso vi siano risultati analoghi al teorema di incompletezza
di Goedel precedentemente discusso, che stabiliscono l'impossibilità di
una "macchina induttiva" universale del tipo di quella prospettata da
Leibniz, le macchine induttive "speciali" stanno proliferando e, come
abbiamo sottolineato, con notevoli successi nei campi più diversi.
Abbiamo lasciato il sogno "deduttivistico" di Leibniz fermo al 1931 nella
situazione apparentemente fallimentare determinata dal teorema di incompletezza
di Goedel. Tuttavia, il linguaggio sottostante al sistema dei Principia
di Russell era molto ricco, quasi tanto ricco quanto un linguaggio naturale.
Forse, allora, il sogno "deduttivistico" di Leibniz avrebbe potuto essere
realizzato rispetto a un linguaggio meno ricco ma che ci consentisse ugualmente
di formulare una classe di problemi praticamente e teoricamente interessanti.
Di fatto, già nel 1928 era stato isolato un "frammento" dei linguaggi
naturali che pareva assai promettente da questo punto di vista. Senza
soffermarci qui sulla sua definizione tecnica, diciamo solo che linguaggi
di questo tipo vengono oggi detti del primo ordine.
Il sogno "deduttivistico" di Leibniz subiva così uno slittamento creativo:
il nuovo problema era quello della meccanizzazione dei ragionamenti esprimibili
in linguaggi del primo ordine, o in altri termini: è possibile costruire
una macchina "deduttiva" capace di risolvere ogni problema formulabile
in un linguaggio del 1 ordine? capace cioè di rispondere si o no ad ogni
domanda della forma: è la proposizione A vera in ogni situazione in cui
lo sono le proposizioni B, C, D, ecc., dove A, B, C, D, ecc. sono proposizioni
del 1 ordine.
Il primo risultato parziale, ma finalmente positivo, arrivò quasi subito,
nel 1930. Nella sua dissertazione di dottorato, il solito Kurt Goedel
dimostrò un teorema che avrebbe estasiato Leibniz.
In esso infatti erano contenute le istruzioni per costruire una "macchina
deduttiva" capace di generare ad una ad una tutte le proposizioni del
I ordine che sono vere in ogni situazione in cui lo è un qualsivoglia
insieme finito P di proposizioni del I ordine, in breve tutte le conseguenze
di P. Chiamiamo una macchina di questo tipo KURT, in onore di Kurt Goedel.
Ma la disponibilità di KURT non implicava ancora una piena realizzazione,
nemmeno al livello dei linguaggi del I ordine, del sogno "deduttivistico"
di Leibniz. Supponiamo infatti di avere sotto mano KURT e di porgli il
quesito se una data proporzione A è o meno una conseguenza di un dato
insieme finito P di proposizioni. Quel che farà allora KURT sarà di stampare
ad una ad una ciascuna delle conseguenze di P. Se A è davvero una conseguenza
di P, essa verrà stampata dopo un tempo finito cosicché noi potremo sapere
che lo è. Invece, se non lo è, essa non verrà naturalmente mai stampata.
Ma come potremo saperlo visto che, essendo infinita la lista delle conseguenze
di ogni P, il processo di stampa non terminerà mai? In altri termini,
il fatto che A non sia stata stampata dopo, diciamo, mille anni non ci
autorizzerà a concludere che non lo sarà nei successivi mille anni.
Così, KURT darà una risposta al nostro quesito se e solo se la risposta
è positiva, se e solo se cioè A è davvero una conseguenza di P. Se invece
A non è una conseguenza di P, KURT non ci risponderà né si né no: ci lascerà
in una perenne incertezza.
Supponiamo però di disporre di una seconda macchina capace di generare
ad una ad una tutte le proposizioni che NON conseguono da P. Chiamiamola
ADA in onore della contessa Ada Lovelace, che a metà ottocento contribuì
significativamente, insieme a Charles Babbage, allo sviluppo dei moderni
calcolatori. Poniamo allora ad entrambe simultaneamente il nostro quesito:
è A una conseguenza di P? Entrambe cominceranno a stampare e questa volta
se A non sarà stampata da KURT in un tempo finito dovrà esserlo da ADA,
per cui in ogni caso sapremo se A è o meno una conseguenza di P. Sfortunatamente,
solo sei anni dopo il risultato positivo di Goedel, Alan Turing, proprio
il logico e matematico che con von Neumann più contribuì negli anni '40
allo sviluppo dei moderni calcolatori, dimostrò che nemmeno Dio potrebbe
creare ADA, e cioè che l'esistenza di ADA è in linea di principio impossibile.
Era questo teorema una ragione conclusiva per disperare che il sogno "deduttivistico"
di Leibniz potesse essere realizzato persino sul terreno apparentemente
più dominabile dei linguaggi del I ordine? In un certo senso lo era, poiché
esso implicava che nemmeno per questa classe di linguaggi poteva essere
costruita una caratteristica universale.
Tuttavia, esso non vietava affatto la possibilità di costruire macchine
capaci di decidere classi anche molto ricche di proposizioni del 1 ordine.
Come notò il matematico russo Trachtenbrot: "teoremi sull’impossibilità
di risolvere meccanicamente una data classe di problemi non dovrebbero
essere fonte di disperazione. Un teorema di questo tipo stabilisce solo
che non esiste una macchina capace di risolvere l'intera classe di problemi.
Ma questo non implica che problemi particolari della classe non ammettano
un metodo meccanico di soluzione... In tali soluzioni, bisogna perciò
cercare di costruire macchine capaci di risolvere sottoclassi di problemi
sempre più ricche".
(Algorithms and Automatic Computing Machines, D.C. Heath and Company, Boston, 1963, p. 100)
E’ precisamente in questa direzione che si è sviluppata, e continua, con notevole successo, la ricerca su questo problema. Una impressionante rassegna di risultati positivi è stata pubblicata nel 1979 in un volume di Dreben e Goldfarb.
(Tbe Decision Problem, Addison-Wesley, Reading, Mass., 1979)
Si
tratta di teoremi che stabiliscono l'esistenza di macchine che, pur non
essendo capaci di determinare per ogni insieme P di proposizioni, se una
data proposizione A consegue o meno da P, sono tuttavia capaci di risolvere
ogni problema relativamente a specifici P. I due casi forse più interessanti
sono le due macchine di Alfred Taski (1949) in grado di risolvere qualunque
problema di algebra e geometria euclidea elementare (P in questo caso
sono gli assiomi dell'algebra e della geometria euclidea elementare).
Potremmo allora dire: non esiste una unica coppia, ADA e KURT, capace
di fare tutto; esistono invece molte coppie di ADA e KURT ciascuna in
grado di fare qualcosa di interessante.
Ma intorno alla metà degli anni ’60 lo sviluppo della tecnologia dei calcolatori
ha reso attuale un nuovo problema. E’ vero che se esiste una coppia ADA-KURT
per risolvere una data classe di problemi, saremo in grado di ottenere
una soluzione per ciascuno di essi in un tempo finito. Ma in quanto tempo?
Le sorprese non sono mancate. Sia allora data una classe C di problemi
(ad esempio la classe di problemi della forma: è A una conseguenza degli
assiomi della geometria euclidea elementare?) e prendiamo come complessità
di un problema il numero di simboli necessario a formularlo. Supponiamo
che vi siano problemi in C di complessità k per la cui soluzione una data
macchina M richiede 2^k (due elevato alla k) operazioni.
Si dice allora che la macchina M lavora in tempo esponenziale. Supponiamo
infine che la velocità di M sia di 10^6, e cioè di un milione di operazioni
al secondo.
Allora, nonostante questa mostruosa velocità, se M lavora in tempo esponenziale,
vi saranno problemi in C di complessità relativamente bassa per la cui
soluzione dovremo aspettare alcune migliaia di anni (per una complessità
non certo alta pari a 60 l'attesa è già 36600 anni!).
Certo, non dobbiamo farci spaventare eccessivamente: già nel 1960 un calcolatore
relativamente poco veloce come l'IBM 704 ci mise meno di nove minuti a
dimostrare tutte (oltre 340) le proposizioni del I ordine dei Principia
Mathematica, di Russell e Whitehead. Sembra che Russell abbia esclamato:
"Sarei stato felice di poter disporre di questa possibilità; avrei evitare
di sprecare dieci anni della mia vita su quelle maledette 340 proposizioni!
"
Comunque, il gap tra macchine teoriche, e cioè semplicemente capaci di
risolvere un problema in un tempo finito e macchine praticabili, e cioè
capaci di risolvere lo stesso problema in tempo reale, e cioè non troppo
lungo per i nostri scopi pratici, è profondo per il fenomeno dell'esplosione
esponenziale sopra illustrato.
E’ ancora un problema aperto che cosa debba essere considerata una macchina
praticabile per una data classe di problemi. Buone candidate sono però
le macchine che riescono a risolvere problemi di complessità k con al
massimo k- di operazioni, dove n è un intero fissato.
Si dice di una macchina M di questo tipo che M lavora in tempo polinomiale.
Il caso particolare con n = 2 è noto come tempo quadratico.
La differenza di efficienza rispetto alle macchine che lavorano in tempo
esponenziale è schiacciante già per valori di k relativamente piccoli.
Già con un k = 10, se rispetto ad una data classe di problemi il Cray-3
lavorasse in tempo polinomiale, ci metterebbe al massimo 41 anni per risolvere
problemi di complessità 80 contro i 4.7 milioni di anni del tempo esponenziale;
con un k = 5, ci metterebbe solo mezzo secondo; infine con il k migliore,
pari a due, solo un milionesimo di secondo.
Ma nel 1974/5 sono di nuovo arrivati alcuni sorprendenti risultati limitativi
che stabiliscono che alcune classi importanti di problemi pur solubili
meccanicamente non sono solubili in tempo polinomiale: l'esplosione esponenziale
è per essi inevitabile! Tra questi vi sono proprio i problemi relativi
alla geometria euclidea elementare.
Questo significa: benché sia possibile costruire macchine capaci di rispondere
si o no, in un tempo finito, ad ogni domanda della forma: "è la proposizione
A una conseguenza degli assiomi della geometria euclidea elementare?"
, quale che sia la complessità della domanda, nessuna di queste macchine
può rispondere in tempo polinomiale; ovvero non esistono macchine che
lavorino in tempo polinomiale capaci di rispondere ad ogni domanda del
tipo appena menzionato.
E’ attorno a problemi di questo genere (e a molti altri ancora di carattere
più strettamente tecnologico) che ruota uno dei più arditi progetti nella
storia della tecnologia, il progetto giapponese della V generazione di
calcolatori.
La posta in gioco è la costruzione di calcolatori intelligenti: capaci
di apprendere, ragionare, prendere decisioni, riconoscere immagini, tradurre
automaticamente da un linguaggio naturale all'altro e di interagire con
noi nel linguaggio naturale preferito (incidentalmente, il loro linguaggio
di base sarà essenzialmente quello inventato da Frege!) Certo, è probabile
che solo una minima parte del progetto V generazione sarà realizzata nei
tempi previsti.
Ma, come notava l'autore del Libro delle Macchine, nell’Erehwon di Samuel
Butler alla fine dell’Ottocento (1871): "Pensate alla straordinaria evoluzione
delle macchine in questi ultimi secoli e osservate invece con quale lentezza
progrediscono il regno vegetale e quello animale. Le macchine più altamente
organizzate sono creature non di ieri, ma addirittura degli ultimi cinque
secondi, oserei dire, di fronte alla storia dell'universo.
Supponiamo che gli esseri coscienti esistano da venti, venticinque milioni
di anni: guardate quali passi hanno fatto le macchine negli ultimi trecento
anni! Il mondo non può forse durate altri venti milioni di anni? Ma se
dura altri venti milioni di anni, che cosa finiranno per diventare le
macchine?".
La mia risposta non è quella dell'autore del Libro delle Macchine: lui
predicava la loro distruzione prima che la loro evoluzione finisse per
produrre effetti da noi non più controllabili; io, non trovando alcuna
buona ragione per questa opinione, credo che esse diventeranno, con la
mosca sulla luna di Hilbert, i nostri migliori alleati nella soluzione
della maggior parte delle nostre difficoltà materiali.