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.

La rovina del giocatore

O del perché non conviene giocare d'azzardo.
Partiamo dalla roulette: questa è una ruota suddivisa in 37 settori numerati, da 0 a 36, di cui 18 neri, 18 rossi e lo 0 neutro. Quest'ultimo va a favore del banco, che ha quindi una probabilità di 1/37 in più rispetto allo sprovveduto giocatore di vincere. La percentuale è decisamente irrisoria, almeno rispetto ad altri giochi d'azzardo, ma è sufficiente per permettere a chi detiene il banco di trovarsi in una posizione di vantaggio.
Vediamo cosa succede con il Lotto:

Al Lotto la probabilità di un estratto su una data ruota, poniamo la ruota di Napoli, cioè che tra i 5 numeri estratti sul totale di 90 ci sia quello giocato, è di 5/90 uguale a 1/18; ma nel caso in cui esca il tuo numero lo stato non ti dà 18 volte la posta, bensì poco più di 10 euro per ogni euro giocato. Questo è da aspettarsi e in un certo senso è anche giusto: lo stato non tiene il banco del lotto per far divertire e arricchire la gente, ma per far cassa. L'ambo ha una probabilità di 2/801, all'incirca un caso a favore contro 400; però se vinci il Lotto non ti dà 400 volte la posta, bensì 250 volte (al lordo della tassa governativa, è ovvio!). Ma anche in caso di gioco equo, cioè nel caso in cui giocatore e banco abbiano la stessa probabilità di vincere ad ogni giocata, se il giocatore si intestardisce nel gioco finirà per rovinarsi.

(via Ottavio Serra)

Sette messaggeri cosmici

Supponiamo di metterci in viaggio dalla Terra verso il punto dell'universo osservabile più lontano. Sulla nostra navicella abbiamo sette sonde che ci servono per tenere i collegamenti tra noi e la Terra. Supponiamo che la velocità delle sonde coincide con quella della luce, o comunque pari a una velocità la cui differenza con $c$ sia trascurabile, mentre la velocità della navicella è $v = 2/3 \, c$. La sonda, una volta giunta in orbita alla Terra, trasmette le informazioni che abbiamo caricato nella sua memoria, quindi si dirige nuovamente verso di noi per raccogliere le nuove informazioni. Nel frattempo, a 24 ore di distanza una dall'altra, lanciamo tutte le navicelle.
Il tempo che impiega ciascuna sonda sarà dato dalla formula

Tullio Regge e la rottura di simmetria

Capire come avvenga la rottura della simmetria non è facile; può servire la seguente similitudine creata dal fisico italiano Tullio Regge:
Si immagini una scodella circolare allargata verso l'alto, il cui fondo non sia piatto, ma con un rialzo centrale circondato da un solco il cui bordo esterno poggi su un tavolo orizzontale. Delle palline lanciate internamente alla scodella con velocità sufficientemente alta (energia elevata) ruotano premute dalla forza centrifuga contro la superficie interna della scodella. Esse presentano simmetria circolare. Quando l'energia diminuisce, le palline cadono verso il basso e si vanno a fermare nel solco del fondo in punti diversi e non presentano più simmetria circolare: la simmetria circolare si è rotta spontaneamente. Nella similitudine la scodella è l'universo, il campo di gravità che rompe la simmetria è il campo di Higgs.

- via Ottavio Serra (pdf)

Quei matematici dei contadini russi: moltiplicazioni

Contadini russi di Filipp Andreevic Maljavin (1902)

Non è né una prosecuzione ideale e apocrifa, né un prequel dell'interessantissimo Problemi matematici per gli ebrei sovietici di Popinga, ma l'idea di fondo è quella di omaggiare il professore di matematica del liceo, Ottavio Serra, che all'epoca per la prima volta mi introdusse al magico mondo della matematica dei contadini russi. Visto però che questo metodo serviva ai nostri bravi contadini per calcolare più semplicemente e rapidamente le moltiplicazioni ha senso, prima di tutto, parlare dell'operazione prodotto tra numeri naturali.
Innanzitutto è necessario, a partire da due numeri $m$, $n$, definire il prodotto $m \cdot n$ tra i due. Questa operazione può essere definita come la somma di tanti $m$ uno dietro l'altro per $n$ volte o d'altra parte come la somma di tanti $n$ uno dietro l'altro per $m$ volte, e questo ci fa capire come la moltiplicazione sia commutativa (in un certo senso si potrebbe dire che la commutatività della moltiplicazione discende da quella dell'addizione). Questo modo può anche andar bene quando abbiamo numeri di una cifra, ma quando entrambi i numeri hanno due cifre, operare in questo modo diventa piuttosto lungo. Così il metodo classico, o canonico utilizzato a scuola è quello che si fonda sulle tavole pitagoriche e quindi sulle tabelline, e certamente è molto più semplice e veloce delle somme ripetute, ma implica il ricordare una decina di tabelline e l'uso successivo delle somme. Qualcosa del tipo⁽¹⁾:

Non è però l'unico metodo per eseguire il prodotto tra due numeri e nel corso della storia ne sono stati sviluppati cinque⁽²⁾: la moltiplicazione in colonna (quella classica, per intenderci), la moltiplicazione medievale, la moltiplicazione a crocetta, la moltiplicazione cinese, la moltiplicazione per raddoppio, la moltiplicazione dei contadini russi.
La seconda di queste moltiplicazioni, quella araba, anche detta a graticola o gelosia, è stata probabilmente sviluppata in India e nel mondo arabo, e probabilmente era nota anche in Cina. La prima traccia documentata in Europa risale al 1478 quando viene diffuso il primo libro di matematica stampato con il nuovo metodo sviluppato nel 1456 da Gutenberg, Larte de labbacho, testo anonimo anche noto come l'Aritmetica di Treviso⁽³⁾.