Minacce aliene — Parte 4

“Bene, quindi il problema diventa: se ciascuno dei numeri da 1 a n viene colorato di rosso o di blu, qual è il minimo valore di n per ottenere una progressione aritmetica monocromatica composta da 3, oppure 4, oppure k termini?”.

“Oh, due variabili?”.

“Eh, le cose si complicano”.

“Già mi pare un ottimo risultato affermare che un valore di n che risolve il problema esiste sempre”.

“E hai ragione, questo è il primo passo notevole. Dopo aver dimostrato l’esistenza di un tale n, van der Waerden ha provato anche a stabilirne un valore minimo. Il fatto è che questo valore minimo è enorme, così grande da non poter essere espresso nelle usuali notazioni a cui siamo abituati”.

“Eh? Come è possibile? La notazione scientifica permette di esprimere numeri enormi”.

“Che però sono ridicolmente piccoli se confrontati col numero trovato da van Der Waerden”.

“Incredibile”.

“Per definire il numero ha usato una successione di funzioni, che crescono sempre più velocemente”.

“Uhm, non capisco”.

“Aspetta, partiamo dal semplice. Non avrai difficoltà a immaginare la funzione DOPPIO(x), che raddoppia il suo ingresso”.

“Stai dicendo che DOPPIO(x) = 2x?”.

“Esatto”.

“E c’è bisogno di una funzione apposita?”.

“Per calcolare il doppio, certamente no. Per capire come è fatta la nostra successione di funzioni, invece, sì. Lasciami andare avanti”.

“Ok, vai”.

“Ora definisco la funzione ESPONENTE(x), che calcola il valore di 2 elevato a esponente x”.

“Una funzione esponenziale”.

“Sì, la cosa interessante è che questa funzione è definibile a partire da DOPPIO(x)”.

“In che modo?”.

“Cosa succede se calcoli per x volte il doppio di 1?”.

“Aspetta, allora… se calcolo 1 volta il doppio di 1, ottengo 2, e fin qua è facile. Se calcolo 2 volte il doppio di 1, ottengo 2 per 2, cioè 4. Se calcolo 3 volte il doppio di 1, ottengo 2 per 2 per 2… ah! Certo, se calcolo x volte il doppio di 1, ottengo 2 elevato a x, cioè ESPONENTE(x)”.

“Quindi possiamo dire che ESPONENTE(x) = DOPPIO(DOPPIO(...DOPPIO(1))), dove la funzione DOPPIO compare x volte”.

“Bello, comincio a capire”.

“Ora facciamo un altro passo, definiamo la funzione TORRE(x)”.

“Che immagino sia fatta dall'applicazione di x volte della funzione ESPONENTE”.

“Infatti.”.

“Da dove viene il nome TORRE?”.

“Prova a calcolare TORRE(3)”.

“Vediamo, TORRE(3) = ESPONENTE(ESPONENTE(ESPONENTE(1)))”.

“Ok, quindi partiamo da ESPONENTE(1)”.

“ESPONENTE(1) = DOPPIO(1), no?”.

“Certo”.

“E DOPPIO(1) = 2”.

“Giusto anche questo. Quindi TORRE(3) = ESPONENTE(ESPONENTE(2))”.

“Bene, allora adesso devo calcolare ESPONENTE(2), che è uguale a DOPPIO(DOPPIO(1)), cioè DOPPIO(2), cioè 4”.

“Infatti avevamo visto che ESPONENTE(2) calcola 2 elevato a 2, cioè 4”.

“Ah, ecco, vero. Quindi mi rimane da calcolare ESPONENTE(4)”.

“Si capisce meglio se calcoli ESPONENTE(2²), applicando direttamente l’esponenziale”.

“Applicando direttamente la definizione di ESPONENTE, verrebbe 2²²”.

“”Una torre di potenze. Ecco perché questa funzione si chiama TORRE: calcola torri di potenze.

“Non è come fare una potenza di una potenza?”.

“Eh, no, qui non ci sono parentesi: per calcolare una torre di potenze, si parte dall'alto. Per esempio, TORRE(4) è 2²²² = 2²⁴ = 2¹⁶, mentre ((2²)²)², che è la cosiddetta potenza di potenza, è uguale a 2⁸.

“Ok, ci sono”.

“Ora andiamo avanti, definiamo una nuova funzione, WOW(x). Ti anticipo che WOW non ha nessun significato se non quello di stupore, per quanto veloce cresce questa funzione”.

“Non ci posso credere”.

“Eh, in mancanza di nomi migliori… I numeri calcolati da WOW sono enormi. Naturalmente, WOW(x) è definita come TORRE(TORRE(…TORRE(1))), dove la funzione TORRE compare x volte”.

“Gulp. Chissà quanto vale WOW(4)”.

“Un numero enorme. WOW(4) = TORRE(TORRE(TORRE(TORRE(1))))”.

“Uhm, TORRE(1) è uguale a 2, fin qua è facile. Quindi mi rimane da calcolare TORRE(TORRE(TORRE(2)))”.

“Anche TORRE(2) è facile, no?”.

“Certo, è uguale a 2², cioè 4”.

“Ok, quindi ora devi calcolare TORRE(TORRE(4))”.

“TORRE(4) è una torre di 2 composta da 4 elementi, cioè 2²²², che è uguale a 65536”.

“Bene, ultimo passo, devi calcolare TORRE(65536)”.

“Argh”.

“O anche wow!”.

“Una torre di potenze composta da 65536 esponenti, una cosa impossibile da immaginare”.

“Esattamente”.

“E questo numero è quello trovato da van der Waerden?”.

“Oh, no, questo è ancora piccolo se confrontato con quello”.

“Cosa?”.

“Eh, sì. Per arrivare al numero trovato da van der Waerden, occorre immaginare questa successione di funzioni:”.

DOPPIO(1)
ESPONENTE(2)
TORRE(3)
WOW(4)
eccetera

“Ogni volta applichiamo tante volte la funzione precedente?”.

“Esattamente”.

“E dopo WOW che funzioni ci sono?”.

“Non sono stati definiti nomi per le funzioni successive. Sai come si fa, si definisce una regola e poi si va avanti così. Per scrivere i termini successivi si usa un nome generico, che è ACKERMANN”.

“Questo è un nome proprio, suppongo?”.

“Esatto, dal nome di chi l’ha definita. Una volta capito che a ogni passo si deve applicare la funzione precedente un certo numero di volte, possiamo definire la funzione ACKERMANN in questo modo:”.

ACKERMANN(1) = DOPPIO(1)
ACKERMANN(2) = ESPONENTE(2)
ACKERMANN(3) = TORRE(3)
ACKERMANN(4) = WOW(4)
eccetera

“Quell'eccetera fa paura”.

“Ed eccoci arrivati alla soluzione del problema proposto da van der Waerden”.

“Se ciascuno dei numeri da 1 a n viene colorato di rosso o di blu, qual è il minimo valore di n per ottenere una progressione aritmetica monocromatica composta da k termini?”.

“E la risposta è: ACKERMANN(k)”.

“Quindi, tornando al quesito iniziale, quello delle progressioni aritmetiche composte da 3 numeri dello stesso colore, siamo sicuri di trovarne se prendiamo i numeri che vanno da 1 a ACKERMANN(3), giusto?”.

“Giusto”.

“E ACKERMANN(3) è uguale a TORRE(3), cioè 16. Uhm, non avevo dimostrato che anche solo prendendo i numeri da 1 a 9 troverò sempre una progressione aritmetica monocolore?”.

“Sì, certo. La stima ACKERMANN(k) è una condizione sufficiente per essere sicuri di trovare la progressione monocolore. Non è detto che, con ulteriori studi, non si possa migliorare la stima. Anzi, un miglioramento è già stato fatto: nella dimostrazione originale di van der Waerden compare il numero ACKERMANN(k), ma successivamente, nel 1987, il matematico israeliano Sharon Shelah ha dimostrato che ci si può fermare a WOW(k)”.

“Ah, ecco. Rimane comunque un numero colossale”.

“E, per quanto riguarda il quesito iniziale, ancora più inutile: WOW(3) è uguale a 65536”.

“Se k aumenta, però, WOW(k) rimane a un livello inferiore rispetto a ACKERMANN(k), vero?”.

“Esatto. Sappi che Graham, un altro matematico che ha lavorato alla teoria di Ramsey, ha offerto un premio di 1000 dollari per chiunque sia in grado di dimostrare che, al posto di WOW(k), si può usare TORRE(k). O a chi sia in grado di dimostrare il contrario, cioè che TORRE(k) è un numero troppo basso”.

“Anche in questo campo, quindi, ci sono molti problemi aperti”.

“Già. Quella di Ramsey è una teoria affascinante, proprio perché si occupa di trovare strutture ordinate all'interno di strutture apparentemente casuali. Un articolo divulgativo di Graham e Spencer, comparso su Le Scienze nel 1990, si concludeva con questa domanda: oggi, grazie alla teoria di Ramsey, siamo in grado di riconoscere con facilità le costellazioni del cielo notturno. Quali configurazioni potremmo mai trovare in insiemi che sono ACKERMANN(9) volte più grandi?”.

“Speriamo di non trovare alieni cattivi, però”.

---

Questa è l'ultima parte di un articolo uscito sulla rivista Archimede, numero 4, del 2017. La prima parte è qua, la seconda qua, la terza qua.