Valentini Carlo

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.