Premio Turing 2023: Avi Wigderson e la casualità

Poiché non sto mai fermo un attimo e devo sempre sperimentare qualcosa di nuovo, da un po' di tempo a questa parte ho messo in piedi una specie di blocchetto degli appunti pubblico che uso per post rapidi, spesso come "ristampa" di post che dissemino per il fediverso. E originariamente anche questo sarebbe stato destinato ai pensierini, ma quando poi ho letto la motivazione del premio mi sono detto che sarebbe valsa la pena scriverne qui su DropSea (e no, non mi sono dimenticato di Peter Higgs: ho scritto ieri un breve post sull'Isola di Ula-Ula e non mi pare il caso, per ora, di scrivere altro).
Tutto inizia con il Premio Turing assegnato ogni anno dalla Association for Computing Machinery nel campo dell'informatica e intitolato ad Alan Turing (da non confondere con il Premio Loebner, ispirato quest'ultimo al test di Turing). In effetti il premio dell'anno \(n\) viene assegnato nell'anno \(n+1\), così in questo 2024 è stato assegnato il premio 2023, per la precisione ad Avi Wigderson (che aveva già vinto il Premio Abel nel 2021):

Per la ridefinizione del ruolo della casualità nella computazione e il suo decennale ruolo di leadership intellettuale nell'informatica teorica.

via commons

Inoltre nel comunicato ufficiale troviamo questo passaggio:

Fondamentalmente, i computer sono sistemi deterministici; l'insieme delle istruzioni di un algoritmo appliocate a ogni dato input determina univocamente il calcolo e, in particolare, l'output. In altre parole, l'algoritmo deterministico è seguito da uno schema prevedibile. La casualità, al contrario, manca di uno schema prevedibile, o di prevedibilità negli eventi o nei risultati.

E qui mi si accende la lampadina, visto che in quanto scritto riecheggiano le parole di Davide Palmigiani in Matematica #8: La probabilità.
In quell'agile libretto, infatti, viene sottolineato come i computer siano macchine deterministiche e quindi per far sì che siano in grado di simulare la casualità è necessario adottare una serie di accorgimenti, ricordandosi che simulare la casualità non vuol dire avere della vera casualità. E' interessante, quindi, riportare qui sotto il passo di Stanislaw Ulam, citato nel testo da Palmigiani, in cui ricorda l'inizio del lavoro con John von Neumann nello sviluppo del metodo Monte Carlo:

I primi tentativi che ho fatto per praticare il metodo Monte Carlo sono stati suggeriti da una domanda posta mentre giocavo a un solitario. La domanda era: quali sono le probabilità che un solitario con 52 carte venga completato con successo? Dopo aver speso molto tempo cercando di stimarle attraverso calcoli combinatori puri, mi schiesi se un metodo più pratico del "pensiero astratto" non sarebbe stato quello di simularlo, diciamo, cento volte e semplicemente osservare e contare il numero di partite vinte. Era una strategia realistica con l'avvento dell'era dei computer veloci, e subito pensai a problemi di diffusione dei neutroni e ad altre questioni di fisica matematica, e più in generale a come modificare problemi descritti da determinate equazioni differenziali in una forma equivalente interpretabile come una successione di operazioni casuali. In seguito ho descritto l'idea a John von Neumann e abbiamo iniziato a pianificare i calcoli effettivi.

La prima volta che ho incontrato i metodi Monte Carlo è stato al liceo, grazie al mio professore di matematica dell'epoca, Ottavio Serra, che è stato protagonista di altri quattro post. E a proposito di questi metodi di generazione di numeri casuali potete trovare in questa serie di lezioni sulla probabilità un pdf dedicato anche a tali metodi. All'interno vengono citati due metodi particolari, il sample mean, o media campionaria, e l'hit or miss, colpito o mancato, di cui il prof. inserisce anche alcune righe del listato. Il metodo, considerato il più semplice richiama all'interno la funzione random che

(...) genera numeri pseudo casuali compresi tra 0 incluso ed 1 escluso.

Per generare tali numeri si può utilizzare il lineare congruenziale descritto da Palmigiani e che fa uso della matematica modulare: \[x_{i+1} = a x_i \mod m\] \[u_{i+1} = x_{i+1} / m\] Ovviamente con la prima relazione si definisce una serie numerica che si blocca fino a che non ricorre nuovamente \(x_0\), il seme da cui la serie viene generata. \(a\) invece è detto moltiplicatore, mentre \(m\) è il modulo (ovviamente nome ispirato all'operazione di modulo). Praticamente si parte da un seme iniziale, lo si moltiplica per \(a\) e si calcola il risultato dell'operazione di modulo che restituirà un numero compreso tra 1 ed \(m\), escluso \(m\). Per avere un numero casuale compreso tra 0 e 1 bisogna dividere ciascun \(x_i\) per \(m\), ottenendo una sequenza, appunto, pseudo-casuale che appare tanto più casuale quanto più grande è \(m\).
Ritorniamo a questo punto all'esempio nella lezione del professor Serra. E' interessante osservare come il metodo hit or miss descritto dal prof. ha come utilità quella di determinare l'area di una figura (presumibilmente) irregolare posta all'interno di un rettangolo. La filosofia del metodo è quella di colpire \(n\) volte, con \(n\) sufficientemente grande, il rettangolo e contare le \(k\) volte che si è colpita la figura all'interno del rettangolo. In questo modo l'area della figura sarà presumibilmente data dalla formula \[A_F = \frac{k}{n} A_R\] Che poi è la stessa filosofia dietro l'esperimento di phyphox per il calcolo del pi greco.
E così, alla fine, arrivo sempre lì, al famoso \(\pi\), il tutto partendo da un premio dell'informatica assegnato a un matematico che si è interessato di casualità!