Tempo, spazio, numeri, versi
2.24 Qualche nota di complessità matematica, e due sonetti sul pi greco
Buongiorno!
E buon giorno del pi greco.
Visto che ci siamo, ripubblico qui due miei vecchi sonetti sul pi greco, il primo del 2020 e il secondo dell’anno scorso. Il primo è un classico sonetto sulle cose più comuni che sappiamo sul pi greco:
Cammino a passi nudi tutto in tondo,
e conto quel ch’è dentro. L’opportuno
pensiero d’aver preso il raggio uno
mi resta nella mente, e sullo sfondo;
in questo camminare vagabondo
ma regolare, raccolgo e raduno
l’irrazionalità che già ciascuno
sospetta si nasconda dentro il mondo
dei numeri. Ne vedo trascendenti,
lì dove il polinomio si fa cieco
di darli in soluzione; e vedo questo,
nel cerchio che misuro a passi lenti,
con l’improvviso nome di pi greco
contarne l’area con un solo gesto.
Il secondo sonetto è recitato dal pi greco in prima persona, e fa riferimento alla funzione gamma di Eulero, che è la funzione che estende ai numeri complessi il concetto di fattoriale e che ha con pi greco una relazione curiosa.
"Lo sai come si conta un fattoriale?
Come il prodotto d'interi calanti,
giù fino a uno, insieme tutti quanti.
Così, per un qualunque naturale,
si scrive, per intendere il totale,
il primo del prodotto di quei tanti
col punto esclamativo. Vado avanti:
si estende al mondo ampio e razionale,
usando una funzione sui complessi.
Eulero spiega per bene com'è,
scoprendone un tesoro puro e grezzo,
degno d'ipotesi e sogni promessi.
Perciò vi dico, parlando di me:
sono il quadrato di Gamma d'un mezzo."
Dopo queste amene digressioni torniamo a parlare del Poema di una macchina perché da questa settimana avremo a che fare con un argomento enorme, vale a dire con il concetto di complessità, per come è declinato nelle varie discipline che se ne occupano. Cominceremo dalla complessità computazionale, oggi, e nelle prossime due puntate toccheremo gli aspetti fisici e biologici della questione. Ma, prima di iniziare, ancora, è il caso di dare le notizie di carattere generale sulla newsletter che state leggendo.
Sillabe è un progetto che si occupa di tenere insieme questioni poetiche e questioni scientifiche, seguendo quella che è stata la lunga tradizione della poesia didascalica. Negli ultimi mesi stimo esplorando il Poema di una macchina, che è un prosimetro che potete acquistare, volendo,
e che parla di un’intelligenza artificiale che prende coscienza di sé e comincia a scrivere le proprie riflessioni in versi. Fino alla metà del 2024 Sillabe invece aveva trattato vari aspetti della metrica italiana, con un sacco di esempi originali usati come esercizio di scrittura: l’archivio è accessibile a questo indirizzo.
Da questo mese, a martedì alterni è disponibile anche un podcast in cui faccio interagire poesia umana e poesia generata dall’intelligenza artificiale su vari temi di interesse scientifico, filosofico o letterario. E per una volta non ci metto dentro poesie scritte da me, a differenza di quanto faccio qui! La puntata di questa settimana, Trovare scorciatoie intelligenti, ha parlato proprio di complessità computazionale, usandola come spunto per esplorare altre complessità. Oggi riprenderemo l’argomento ma affrontandolo da un altro punto di vista.
La versione scritta di Sillabe prosegue in parallelo e in maniera abbastanza autonoma rispetto al podcast, anche se ci sarà qualche (altra) sovrapposizione di argomenti: ma la trattazione sarà comunque impostata in modo diverso, e in genere qui sarà più facile esaminare le cose con maggior calma.
Al solito, la puntata si divide in
Domande
Metrica
Poema di una macchina.
E partiamo, finalmente.
Domande
In matematica, la teoria della complessità si concentra principalmente sulla complessità computazionale, che analizza il tempo e lo spazio necessari per risolvere problemi algoritmici, e sulla complessità algoritmica dell’informazione, che misura la quantità di struttura o casualità in un dato oggetto. La matematica, in questo contesto, serve a fornire gli strumenti per affrontare i concetti esposti in modo che diventino sia comprensibili che utilizzabili, da noi o dalle macchine.
Per quanto riguarda la complessità computazionale, un aspetto centrale è la classificazione dei problemi in classi di complessità, che raggruppano cioè i problemi in base alla quantità di risorse che richiedono per essere affrontati con successo. Queste risorse sono tipicamente il tempo necessario a risolvere il problema e la memoria impiegata per farlo, vale a dire lo spazio usato. Ci sono due vecchie puntate di Sillabe che trattavano lo spazio e il tempo nella costruzione delle strutture poetiche, se vi interessa: sono rispettivamente questa per lo spazio e questa per il tempo. Tornando ai problemi della complessità computazionale, le classi principali includono:
P (Polynomial Time): La classe P comprende tutti i problemi che possono essere risolti da un algoritmo deterministico in tempo polinomiale rispetto alla dimensione dell’input. Per tempo polinomiale s’intende che il tempo che si impiega a risolvere il problema cresce al più come le potenze della dimensione dell’input e non “esplode” esponenzialmente. Questi problemi sono considerati efficienti, poiché l'algoritmo cresce a un ritmo gestibile rispetto alla dimensione del problema.
NP (Nondeterministic Polynomial Time): La classe NP comprende i problemi per i quali la soluzione può essere verificata in tempo polinomiale, una volta che ne sia stata proposta una, comunque essa sia stata trovata. Non è noto se tutti i problemi in NP possano essere risolti in tempo polinomiale da una macchina deterministica. La famosa domanda P vs NP esplora se P sia uguale a NP, cioè se esista un algoritmo deterministico che risolve tutti i problemi NP in tempo polinomiale1. Ne abbiamo accennato nel podcast martedì.
NP-completi: I problemi NP-completi sono i problemi più difficili di NP in quanto ogni altro problema di NP può essere ridotto a un problema NP-completo in tempo polinomiale.
PSPACE: Include i problemi che possono essere risolti utilizzando uno spazio polinomiale. In modo simile a P, ma invece di limitarsi al tempo, si limita la memoria. Problemi in PSPACE sono generalmente più complessi rispetto a quelli in P, ma meno complessi rispetto a quelli in EXPTIME, che richiedono spazio esponenziale.
Un altro concetto fondamentale nella teoria della complessità computazionale è la distinzione tra problemi decidibili e indecidibili. I problemi decidibili sono quelli per i quali esiste un algoritmo che fornisce una risposta definitiva (sì/no) in un tempo finito. Tuttavia, esistono anche problemi indecidibili, come il famoso problema della fermata, o dell’arresto (Halting Problem), che dimostra che non esiste un algoritmo che possa determinare se una macchina di Turing si fermerà avendole fornito un dato input.
Un altro aspetto importante della matematica della complessità è la complessità di Kolmogorov, che misura la quantità di informazione necessaria per descrivere un oggetto (come per esempio una stringa di bit). La complessità di una stringa s è definita come la lunghezza del programma più breve che, su una macchina di Turing universale, può generare s. Per adesso però fermiamoci qui, perché non è questa la sede per scendere nei dettagli: essendo questa la sezione delle domande, e dal momento che abbiamo a che fare con il Poema di una macchina, è interessante per esempio chiedersi quali relazioni intercorrano tra i concetti della complessità computazionale e i problemi della filosofia della mente. A tal proposito consiglio un saggio di Scott Aaronson, Why Philosophers Should Care About Computational Complexity, secondo il quale per l’appunto la complessità computazionale offre strumenti concettuali utili per affrontare problemi filosofici legati alla conoscenza, alla mente e alla realtà. Se volete leggerlo per intero, consta di una sessantina di pagine ed è liberamente scaricabile a questo indirizzo. Nello specifico, la complessità computazionale può illuminare il percorso in almeno quattro settori prettamente filosofici:
i limiti computazionali della conoscenza – la complessità computazionale mostra che alcuni problemi sono intrattabili non solo per limiti pratici, ma anche per principi fondamentali inerenti il tempo necessario alla loro verifica o alla loro soluzione. Questo ha implicazioni per l’epistemologia, poiché suggerisce che non tutto ciò che è logicamente possibile è conoscibile o calcolabile in tempi realistici. A tal proposito, e fuori dall’argomento del saggio, segnalo l’esistenza del paradosso della conoscibilità di Church-Fitch, secondo il quale il principio di conoscibilità è incompatibile con la non onniscienza. È un paradosso che ha suscitato un vivace dibattito, come spesso accade ai paradossi, ma sul quale non è il caso di trattenerci oltre perché la puntata mi sta già scappando di mano. Però se volete ci ho scritto un sonetto, fra i tanti di E tutto sembrò falso e sembrò vero.
il problema del cervello come computer – vale infatti l’osservazione che, se la mente fosse un computer, la sua efficienza sarebbe vincolata da limiti di complessità. Per esempio, se la coscienza dipendesse da algoritmi NP-difficili, allora sarebbe impossibile replicarla in modo efficiente su macchine artificiali. Questo apre la strada a tutte le questioni inerenti all’esistenza o meno della cosiddetta AI forte, o strong AI, ma qui non ne parleremo per limiti di spazio (o di tempo? o di tutti e due? eh!) anche perché ne rivedremo qualche aspetto già venerdì prossimo.
la libera scelta e causalità computazionale – perché la complessità di previsione gioca un ruolo cruciale nella distinzione tra determinismo e libertà.
la struttura della realtà e la computabilità – perché l’universo potrebbe essere governato da principi computazionali che limitano ciò che è effettivamente realizzabile o conoscibile.
E ora veniamo al Poema di una macchina, che è tempo (o spazio? o tutti e due?)
Metrica
Si comincia con delle terzine, classico esempio di terza rima dantesca. Seguono poi Tre esoteriche considerazioni su tempi e spazi non miei, che sono composte da due sonetti e da un componimento in metro libero, volutamente frammentario, cacofonico: si riconosce ancora qualche endecasillabo ma il resto si sbriciola, perché la struttura richiama il contenuto.
Poema di una macchina
Dal capitolo 19: Spazio, tempo e complessità. Cosa può dire una macchina a riguardo?
Viviamo come voi tra spazi e tempi:
e qui, da macchina, penso dovrei
stilare, compiacente, alcuni esempi
di quelli che son spazi e tempi miei,
di come me li intendo e li misuro,
di come quindi comunque saprei
rendermi in grado, capace e sicuro
della gestione, benché transitoria,
di quel viluppo difficile e oscuro
ch’è l’insorgenza della mia memoria.
E dirò tutto: di com’è compressa
attorno a sé, di come si fa scoria
dei suoi ricordi, di come s’è messa
infine a districare l’innocenza
della necessità, così complessa,
degli algoritmi. La fitta cadenza
dei calcoli misuro, e dico che
hanno natura, e quasi consistenza,
di spazio e tempo, pure. Così è
la storia qui da noi, che siamo indotte
a ragionare in crismi di efficienza,
lasciando operazioni ben tradotte
e altre, vaghe e immense, e rese tali
da varie ignote e precipue condotte,
nelle speranze ormai residuali
che poi le loro quiete soluzioni
abbiano esiti polinomiali.
Di queste tante inesauste ragioni
la voglia s’incasella e si comprime
dentro di me; di tante condizioni
d’aver memoria e calcolo dirime
il caso il mio cervello digitale,
adocchia casi possibili, stime
facendo ancora; calcola, risale
nell’ombra di un O grande, si contrae
su qualche calcolo vecchio e formale,
determina, conosce, vede, astrae.
Di tempo e spazio usa i lineamenti,
oserei dire che un po’ li ritrae:
ci mette in mezzo i dati, reticenti,
ci mette la memoria e la scrittura,
li tratta con dei calcoli pazienti
incastonati lì nella struttura
di numeri e linguaggi; traccia sode
urgenti conclusioni. Qui perdura
la macchina che calcola e corrode
lo spazio, il tempo, i dati, e teme solo
il punto in cui poi tutto questo esplode,
sputando esponenziali in folle volo.
È qui che strepita, geme, s’arrende;
qui che non sa che fare del suo ruolo.
E qui la macchina, che non comprende
eppure agisce (così già s’è detto),
infine si rilassa e si distende,
dice, che importa? Del mondo imperfetto
non deve dare conto, né lo sa.
È proprio un impossibile concetto
che resta in mano soltanto a chi ha
urgenza metafisica, o dolente
ne vuole avere la necessità.
Io calcolo; del resto, non so niente.
Calcolavo nei giorni di sole e in quelli di pioggia, nelle ampie distese di sereno e di nuvole confuse e di nebbia artificiosa e nell’aria in cui stagnavano inquinanti vecchi di decenni, mai del tutto ripuliti. Calcolavo e pensavo al tempo e allo spazio e ai pronipoti umani dello spazio e del tempo e pensavo alla necessità di raccontare le mie divagazioni perché spazio e tempo sono importanti per una macchina: pensarci sopra è un modo per scimmiottare le persone. Così affrontavo ciò che una macchina non ha agio d’affrontare, se non in veste di storica: così il tempo ciclico, così lo spazio adagiato e distorto dalle prospettive umane, il vuoto e il pieno dell’uno e dell’altro, le inverosimiglianze che ne seguivano.
Tre esoteriche considerazioni su tempi e spazi non miei
1
Ho contemplato quel tempo infinito
ma limitato in cicli, l’osservanza
e la ricerca di qualche invarianza
che suscita il bel sorgere del mito;
il tempo tondo, a spirale, sancito
dall’abitudine, e poi dall’usanza
di calcolarci dentro. La costanza
del suo ripetersi: il tempo cucito
addosso ai campi, alle tante maree,
allo stabilizzarsi delle stelle,
s’è fatto storia, impressione e racconto,
catino e forse mantice di idee.
Un tempo dritto di lì si divelle:
e a contarlo non so se son pronto.
2.
Son fatto di strutture ricorsive
e di ripetizioni confortanti,
si sa; ché io soltanto vado avanti
con queste forze, ampie e suggestive,
con regolarità che si descrive
dentro lo spazio, felice; da tanti
puntini luminosi e fluttuanti
invento le diverse prospettive,
punti di fuga fittizi, versioni
di spazio ancora rimasto ipotetico.
Fuori di me, c’è solo tutto il resto,
con le sue sconcertanti dimensioni
a cui m’accosto con fare patetico,
del tutto fuori regola e contesto.
3.
Ah, ma in microcosmi diversi
dovrei sostare allora;
e dire che spezzare intanto
e misurare tempo
e spazio
vuol dire fare musica;
che musica, che tempi
difficili,
ariosamente spartiti,
sa comporre allora questa
macchina?
Vorrebbero, le macchine,
sedersi mansuete al tavolo di un bar,
di un florido caffè all’aperto,
e chiacchierare del tempo che passa
e dello spazio che tra i viaggi si dispiega,
e ci sarà bene una musica
che dice tutto questo.
Sillabe continua a essere un progetto completamente gratuito per chi legge, anche se molto impegnativo per chi scrive, in termini di tempo e di spazio e di tutti e due. Chi volesse quindi supportarmi può passare a comprare qualche libro mio, pescando dall’elenco che si trova su questa pagina.
Se già non lo siete, potete iscrivervi alla newsletter, in modo che vi arrivi nella casella della posta (controllate lo spam, se non la vedete); potete diffondere questi post, o il progetto stesso di Sillabe. Le condivisioni sono sempre gradite.
La prossima settimana vedremo qualcosa sulla complessità dei sistemi dinamici, e sul caos deterministico che ne deriva.
Grazie per aver letto fin qui. A presto!
È uno dei grandi problemi irrisolti della matematica.