Oh no! More maths

Pare che dietro ad ogni potenziale matematico si nasconda un potenziale nerd, quasi come se nel tratto di DNA che codifica l'attitudine per le scienze esatte fosse codificata pure l'attrazione per SF, fumetti e videogames (sto certamente parlando anche di me stesso). Le cose si fanno però stimolanti quando al ricercatore riesce di coniugare nerditudine e interesse professionale. È il caso, ad esempio, del buffo saggio The Hardness of the Lemmings Game, or Oh no, more NP-Completeness Proofs (scaricatelo qui), in cui Graham Cormode, professore a Warwick con un resumé lungo così, si dedica seriamente all'analisi di Lemmings, che per chi non lo sapesse è uno dei capisaldi del divertimento videoludico degli anni '90, dove lo scopo del gioco è di prevenire l'estinzione di una torma di creaturine antropomorfe e stupidissime, ispirate idealmente ai simpatici roditori che, almeno a livello di leggende metropolitane, sembrerebbero pericolosamente inclini al suicidio di massa (ci si può giocare qui).

Il punto di vista di Cormode è quello della teoria della complessità computazionale: il problema dell'esistenza di una strategia vincente viene interpretato come problema decisionale, e classificato come tale. L'autore dimostra innanzitutto che si tratta di un problema di classe NP (Nondeterministic Polynomial, cioè tale che una soluzione può essere verificata in tempo polinomiale). Successivamente, per mezzo di una riduzione polinomiale al cosiddetto 3SAT (uno dei problemi NP-hard per antonomasia) si dimostra che l'esistenza di una strategia vincente è a sua volta NP-hard, e di conseguenza NP-completo (classificato cioè tra i più interessanti problemi decisionali, equivalente ad uno dei Millennium Problems della Fondazione Clay).

La geometria del TARDIS

Dopo averci eruditi sulle proprietà spazio-temporali dell'isola di R'lyeh (vedi anche qui), quel burlone di Benjamin Tippett si trasferisce da Arkham a Gallifrey, per studiare il bizzarro dispositivo che permette a the doctor di spostarsi nello spazio e nel tempo. Ci propone quindi due brevi saggi, Traversable Achronal Retrograde Domains In Spacetime (vedi qui, nota le iniziali...), dove introduce una geometria che rende possibile il viaggio a ritroso nel tempo, e The Blue Box White Paper (vedi qui), di carattere divulgativo, dove include anche una breve introduzione alla relatività generale.

Francamente non ho letto con attenzione i due lavori, non avendone né il tempo, né la voglia. Forse ci ritornerò sopra (o forse no). Forse investirò altrimenti il sabato sera, magari dando un'occhiata all'episodio speciale proposto dalla BBC in occasione del cinquantenario di the doctor.

Cthulhu sull'ArXiv

[A dire il vero questo post era soltanto un abbozzo. Avevo iniziato a scriverlo mesi fa, ma evidentemente mi ero dimenticato di terminarlo. Lo pubblico comunque.]

Ho già parlato dell'ossessione (una fra le tante...) di Howard Phillips Lovecraft per le geometrie non euclidee. Esse fanno la loro comparsa anche in uno dei racconti più famosi del Solitario di Providence, The Call of Cthulhu (leggibile per intero qui), dove HPL introduce il più noto tra i componenti del suo inquietante pantheon. In particolare, nella terza parte del racconto, The Madness from the Sea, l'immaginario narratore fa esplicitamente uso dell'aggettivo non-Euclideo, parlando ad esempio di "un angolo acuto che si comporta come se fosse ottuso".

Gli aspetti matematici del racconto di Lovecraft hanno evidentemente stimolato la curiosità del fisico Benjamin Tippett, che nel breve saggio Possible Bubbles of Spacetime Curvature in the South Pacific finge di prendere sul serio la questione, esaminando le affermazioni del marinaio Gustaf Johansen con la lente del matematico. Il paper in questione è disponibile qui, archiviato tra i preprints dell'ArXiv.

1, 11, 21,1211,111221,...

... cioè: "uno", "una volta uno", "due volte uno", "una volta due una volta uno"e così via. Probabilmente un po' tutti noi insegnanti di matematica ci siamo visti sottoporre questa bizzarra sequenza di numeri (nota come look-and-say,  numero A005150 dell'OEIS) da qualche intraprendente alunno e probabilmente un po' tutti, dopo aver capito il meccanismo che la genera, l'abbiamo archiviata come una mera curiosità poco matematica. Ma non (come ho appreso leggendo The Irrationals) quel mattacchione di John Horton Conway, che nel saggio The Weird and Wonderful Chemistry of Audioactive Decay prende tale successione terribilmente sul serio, associandole addirittura un enunciato che battezza con il nome altisonante di Teorema Cosmologico. Si tratta in effetti di un risultato piuttosto imprevedibile, che solo una mente non convenzionale come quella del grande matematico inglese avrebbe potuto partorire: essenzialmente, qualunque sia la scelta iniziale delle cifra (non soltanto "1", quindi, ma anche ad esempio "123", che si trasforma in "111213", "31121113" ecc.), a un certo punto (dopo meno di 30 passaggi) il procedimento "look-and-say" (che Conway chiama decadimento audioattivo) finisce per produrre immancabilmente ed esclusivamente allineamenti di sequenze "atomiche" che non interagiscono più con le sequenze vicine, classificate in 92 "elementi comuni" e due "transuranici".

Ma c'è di più: Conway si occupa anche del tasso di crescita delle sue successioni, mostrando che il limite $$ \lim_{n\to\infty}\frac{L_{n+1}}{L_n} $$ del rapporto tra la lunghezza di due termini consecutivi è pari ad una costante algebrica $\lambda \cong 1.303577269$ di grado 71, di cui è in grado di fornire esplicitamente il polinomio minimo:

Weird, nevvero?

L'articolo originale di Conway, piuttosto stringato, fu pubblicato inizialmente su Eureka, magazine dell'Università di Cambridge, e non è di facile reperibilità in rete (anche se da qualche parte lo si trova...). Pare che la dimostrazione originale del Teorema Cosmologico sia andata persa, ma ne esistono di più recenti, ad esempio quella annunciata qui sull'ArXiv. A questo indirizzo è inoltre visionabile una lezione sul decadimento audioattivo.
Il decadimento audioattivo non è l'unica stramberia architettata da quel geniaccio di Conway. A lui si devono anche, in ordine sparso, il gioco della vita, l'algoritmo Doomsday, il FRACTRAN e i numeri surreali. E vale certamente la pena di dare un'occhiata al Book of Numbers, da lui scritto a quattro mani con un altro celebre matematico, Richard K. Guy.