venerdì 5 marzo 2010

Numeri che fanno girare la testa

Oggi xkcd ha pubblicato una vignetta riguardante la congettura di Collatz. Si tratta di un giochino che funziona in questo modo: si prende un numero intero positivo qualunque, se è pari lo si divide per 2, se invece è dispari lo si moltiplica per 3 e si aggiunge 1. E si continua così, fino a che non si arriva a 1 (se si riesce ad arrivare a 1 e si vuole continuare col gioco, si entra in un ciclo: il numero successivo a 1 è 4, poi si ha 2, e di nuovo 1).

Qua a sinistra si può vedere un albero che rappresenta l'evoluzione di alcuni numeri. Come si vede, tutti finiscono a 1. La congettura di Collatz afferma che, comunque noi scegliamo un numero positivo, prima o poi arriviamo sempre a 1. È un giochino che si può fare con carta e penna, durante una riunione noiosa, per esempio. La vignetta suggerisce che se uno comincia a giocarci, poi non finisce più.

Ecco, una persona normale magari alla fine della riunione smette di calcolare e va a casa, ma un matematico forse no.

In effetti questo problema è stato studiato molto, e per molto tempo. È stato proposto nel 1937; nel 1972 Conway ha dimostrato che una generalizzazione della congettura è indecidibile (e qui potrebbero cominciare i guai: se fosse indecidibile anche la congettura, sarebbe inutile cercare una dimostrazione); in seguito ha dimostrato che non possono esistere cicli composti da meno di 400 termini (se esistesse anche solo un ciclo, di qualunque dimensione, la congettura sarebbe falsa, perché gli elementi del ciclo non arriverebbero mai a 1); nel 1985 Lagarias ha dimostrato che non possono esistere cicli di lunghezza minore di 275000, e a questo punto uno potrebbe anche dire “vabbè, dai, allora basta”.

Il fatto è che un matematico non si può accontentare di una serie di conferme alla sua teoria: un matematico vuole la dimostrazione.

La vuole trovare nonostante il parere autorevole di Paul Erdős, che nel 1985 ha affermato che la matematica non è ancora pronta per affrontare problemi così difficili.

Nel frattempo, mentre i matematici sviluppano nuove teorie per affrontare questo difficile problema, i calcolatori continuano a macinare numeri per analizzare sempre più in profondità l'albero di Collatz. Il primo grosso tentativo di studiare la congettura è partito nell'agosto del 1996, quando è stato lanciato un programma scritto in C su due workstation DEC Alpha a 133MHz e altre due a 266MHz. Il programma ha completato l'esame dell'evoluzione di tutti i numeri interi fino a 100·250 nell'aprile del 2000 (no, non ho sbagliato a scrivere).

L'algoritmo è stato migliorato e il programma è stato fatto ripartire nel giugno del 2004. Dopo 81.1 anni di cpu (suddivisi su più macchine, naturalmente), nel gennaio 2009 è stato fermato nuovamente: questa volta ha raggiunto il numero 20·258 (cioè 5764607523034234880), senza trovare alcun controesempio alla congettura — ah, dimenticavo: per maggior sicurezza ogni numero è stato controllato due volte. Un secondo gruppo di ricerca ha ottenuto, in maniera indipendente, lo stesso risultato.

Infine, nel 2001 è partito un progetto di calcolo distribuito che, ad oggi, ha superato la cifra 9·253.

Tutte queste prove non sono riuscite a trovare nessun controesempio alla congettura. Allora perché continuare? Sembra impossibile che la congettura, vera per così tanti numeri, possa dimostrarsi falsa per numeri ancora più grandi.

Eppure, questa non è una dimostrazione, e la storia della matematica ci insegna che già in altri casi sono stati trovati controesempi per numeri giganteschi. Ad esempio, la congettura di Pólya afferma che la maggior parte (cioè una parte superiore al 50%) dei numeri naturali minori di un dato numero ha un numero dispari di fattori primi. Nel 1958 si è dimostrato che la congettura è falsa, fornendo come controesempio un valore pari circa a 1.845·10361. In seguito questo valore è stato abbassato fino a 906150257.

La congettura di Mertens, il cui enunciato riguardante le proprietà di un certo numero n è un po' troppo complicato per stare su questo margine, è stata confutata utilizzando un valore pari a e3.21·1064. Nel 2006 questo limite è stato un po' abbassato, ed ora è pari a e1.59·1040.

Esiste poi una proprietà riguardante i numeri primi, che afferma che a un certo punto il numero di numeri primi minori di un certo numero x supera il valore del logaritmo integrale di x. Nel 1914 è stato dimostrato che questo numero esiste. Nel 1933 è stato dimostrato che, se l'ipotesi di Riemann è vera, allora questo numero è maggiore di eee79. Nel 1955 è stato dimostrato che, senza la necessità di utilizzare l'ipotesi di Riemann, questo numero è minore di 101010963. In seguito questi valori sono stati abbassati, ma rimangono comunque enormi.

Enormi, ma anche piccoli, se confrontati con il numero di Graham: un numero talmente grande che non potrebbe essere contenuto all'interno dell'universo conosciuto, supponendo di poter memorizzare ogni sua cifra in uno spazio pari a un volume di Planck, pari a 4.22419·10−105 metri cubi. Un numero usato in un dimostrazione, eh.

Uh, dimenticavo: come per tutti i grandi teoremi che si rispettino, esiste un premio di mille sterline destinato al primo che riesce a dimostrare, o confutare, la congettura di Collatz.

E, come succede per tutti i grandi teoremi che si rispettino, anche la congettura di Collatz non serve a niente.

12 commenti:

Annarita ha detto...

Beh, se si rimedia un premio di mille sterline (eventualmente, molto eventualmente) a qualcosina potrebbe servire, no?

topor ha detto...

mi fermo al giochino da farsi alle riunioni noiose...

zar ha detto...

@annarita, se la vediamo da questo punto di vista, allora certamente serve :-)

Ronkas ha detto...

Quanto dispreco di energie per nulla.
Io adesso quasi quasi mi rinstallo Folding@home almeno è più carino...

e vedi qualcosa.

ed è utile (dovrebbe).

zar ha detto...

Ronkas, sei un brontolone :-)

E' chiaro che la congettura di Collatz non serve a niente, ma da quando hanno cominciato a studiarla hanno sviluppato molta matematica, e già questo è un risultato. Poi, lo sai che i matematici non si preoccupano della meta, a loro interessa la strada.

Anche folding@home in sé è un giochino - magari ha applicazioni pratiche nell'immediato, ma non puntiamo solo a quelle.

Ronkas ha detto...

Ma nooo dai, provoco, ci metto un po' di pepe... così vi mettete in gioco.

Foldit è anche più carino, ma è veramente da nerds. L'hai visto? Ora che faccio biochimica è troppo goloso.

zar ha detto...

Foldit l'avevo guardato tempo fa, l'idea di analizzare le proteine (proteine?) per ottenere risultati in medicina è bella. Non l'ho mai installato: ti fa vedere le proteine sullo schermo?

Ronkas ha detto...

E' bellissimo, si che ti fa vedere le proteine sullo schermo!
Praticamente è una specie di Folding@home, che però al posto di utilizzare la forza bruta utilizza il cervello della gente.

Ti fanno vedere la proteina denaturata (tutta tutta, foglietti beta, alfa eliche, glicosilazioni) e tu devi ricostruirla o maneggiarla secondo una forma più stabile. Io lo provai tanto tempo fa, ma non c'era gusto perché non sapevo cosa stavo facendo... ora invece è molto divertente!
Ci sono punteggi, community, tutorial, ha una bella grafica... da provare dai, almeno per vedere quelle proteinozze sullo schermo!

nazgul17 ha detto...

Ho letto di questa congettura non più di 5 giorni fa sulle mie dispense di fondamenti dell'informatica! Quando si dice "che coincidenza!"

zar ha detto...

Bello, vi fanno fare esercizi sulla congettura di Collatz?

jenga ha detto...

prooof, ho copiato:
http://jenga.wordpress.com/2010/03/29/la-congettura-di-collatz/

zar ha detto...

Copia, copia.