Numero di Graham

Il 'numero di Graham', così chiamato in onore del matematico Ronald Graham, è un numero naturale di grandezza inconcepibile, il più alto numero finito utilizzato in una seria dimostrazione matematica. Tale numero è estremamente più grande di altri famosi numeri grandi come il googol, il googolplex e perfino il megistone.

Come molti altri numeri di grandi dimensioni, una sua rappresentazione completa in notazione decimale è scientificamente impossibile in quanto, anche ipotizzando di essere in grado di immagazzinare un bit in un singolo volume di Planck, lo spazio necessario a immagazzinare tale numero sarebbe enormemente superiore a quello dell'intero universo conosciuto. In altre parole, un ipotetico calcolatore grande quanto l'intero universo e sofisticato sino agli attuali limiti fisici potrebbe calcolare solo una minuscola parte di questo numero. Tuttavia, nel caso del numero di Graham, lo stesso limite si ripresenta qualora volessimo esprimere la quantità di cifre presenti nel numero, o la quantità di cifre della quantità di cifre, ma anche per la lunghezza della frase "quantità di cifre della quantità di cifre della quantità di cifre..." necessaria. In altre parole, la sua dimensione è tale che non è possibile dare un'idea delle sue effettive dimensioni in termini non matematici.^[1]

Il numero di Graham è stato riportato nel Guinness dei primati del 1980.^[2]

Problema di Graham

Esempio di colorazione di un cubo di tre dimensioni (${\displaystyle n=3}$) con riportato un sottografo soddisfacente il problema di Graham. Da notare che se, ad esempio, il lato inferiore destro del cubo fosse colorato di blu, nel cubo in esame non esisterebbero sottografi completi, piani e monocromi dimostrando empiricamente che la soluzione al problema di Graham deve avere ${\displaystyle n>3}$.

Il problema matematico che ha portato alla definizione del numero di Graham è un particolare caso della teoria di Ramsey, soprannominato "problema di Graham":

Si consideri un ipercubo di ${\displaystyle n}$ dimensioni. Si uniscano tutti i vertici, ottenendo un grafo completo con ${\displaystyle 2^{n}}$ vertici. Si colorino quindi tutti gli spigoli con i colori rosso o blu, a piacere. Qual è il valore più basso di ${\displaystyle n}$ per cui ogni possibile colorazione deve necessariamente contenere almeno un sottografo monocromo completo con ${\displaystyle 4}$ vertici giacenti su un piano?^[3]

La soluzione del problema non è conosciuta; il numero di Graham è un limite massimo dell'intervallo di ${\displaystyle n}$ in cui si possono trovare le soluzioni del problema, come dimostrato da Graham e da Bruce Lee Rothschild nel 1971.^[3]

Nel 2008 Jerome Barclay dimostrò che il limite inferiore dell'intervallo di ${\displaystyle n}$ in cui potrebbe esistere la soluzione è ${\displaystyle 13}$, mentre, allora, i teorici dei grafi erano già riusciti ad abbassare il limite superiore ad un valore inferiore al numero di Graham.^[3][4]

Rappresentazione del numero di Graham

Il numero di Graham può essere rappresentato e calcolato tramite la notazione a frecce di Knuth. In questa notazione, una singola freccia verso l'alto rappresenta un elevamento a potenza, la doppia freccia verso l'alto (${\displaystyle \uparrow \uparrow }$) rappresenta una tetrazione, ossia una potenza ricorsiva, le tre frecce (${\displaystyle \uparrow \uparrow \uparrow }$) rappresentano una tetrazione ricorsiva, e ogni successiva freccia incrementa la profondità di iterazione, con un aumento numerico estremamente elevato per ogni freccia aggiunta. In termini numerici:

${\displaystyle 3\uparrow 3=3^{3}=27}$

${\displaystyle 3\uparrow \uparrow 3=3\uparrow (3\uparrow 3)=3^{3^{3}}=3^{27}=7625597484987}$

${\displaystyle 3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow 3)={\begin{matrix}&3\underbrace {\uparrow 3\uparrow 3\uparrow \dots \uparrow 3} \\&3\uparrow \uparrow 3{\text{ volte }}\end{matrix}}=3\uparrow \uparrow 3^{27}=\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}7625597484987\end{matrix}}\right.{\text{ volte}}}$

e così via.

In questa notazione, il numero di Graham ha valore:

${\displaystyle G=\left.{\begin{matrix}3\underbrace {\uparrow \ldots \uparrow } 3\\\underbrace {\vdots } \\3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 piani}}}$

Nell'espressione riportata sopra, il numero di frecce di ogni livello successivo al primo è definito dal numero espresso nel livello inferiore. Arrivando al 64º livello e calcolandolo, si sarà ottenuto il numero di Graham. In altre parole, scrivendo ${\displaystyle 3\uparrow ^{k}3}$ per indicare un ${\displaystyle 3}$ seguito da ${\displaystyle k}$ frecce (con il senso che si è visto sopra), allora il numero di Graham può essere definito come:

${\displaystyle G=g_{64},\quad {\text{con}}\quad {\begin{cases}g_{1}=3\uparrow \uparrow \uparrow \uparrow 3\\g_{n}=3\uparrow ^{g_{n-1}}3\end{cases}}}$

Primo livello

Per rendersi conto dell'inconcepibile grandezza del numero di Graham, si possono seguire i passi necessari a sviluppare il primo livello ${\displaystyle g_{1}.}$

Si parte calcolando ${\displaystyle 3}$ tetratto ${\displaystyle 3}$:

${\displaystyle a=3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7.625.597.484.987}$

Il successivo passo è calcolare la tetrazione ricorsiva di ${\displaystyle 3}$ per sé stesso, ossia:

${\displaystyle 3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow 3)=\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}7625597484987\end{matrix}}\right.{\text{ volte }}}$

Si tratta quindi di calcolare una torre di elevazioni alta 7625597484987 livelli. Già l'enorme numero risultante da questo relativamente semplice conto è impossibile da scrivere per intero in questo universo. Per arrivare a calcolare il primo livello ${\displaystyle g_{1}}$, tuttavia, è necessario un altro passo di iterazione:

${\displaystyle g_{1}=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))\quad {\text{dove il numero di parentesi è}}\quad 3\uparrow \uparrow (3\uparrow \uparrow 3)}$

In termini di potenze, questo equivale a scrivere:

${\displaystyle g_{1}=\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\dots \left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3}$

Dove l'altezza di ogni torre, e quindi il numero di elevazioni al cubo, si calcola dal numero espresso dalla torre alla sua destra, con un numero di torri pari al numero enorme calcolato nel passo precedente, cioè talmente tante da non essere possibile scriverne il numero per mancanza di spazio nell'universo conosciuto.

Come è intuitivo comprendere, l'aggiunta di ogni singola freccia comporta un enorme aumento sia delle operazioni da effettuare sia della dimensione del risultato finale. Il numero ${\displaystyle g_{1}}$ così calcolato, già di dimensioni difficili da comprendere in termini non matematici, rappresenta però una parte praticamente infinitesima del solo livello ${\displaystyle g_{2}}$, in quanto rappresenta il numero di "frecce" presenti nel calcolo di tale numero, che è a sua volta il numero di "frecce" presenti nel calcolo del terzo livello ${\displaystyle g_{3}}$, e così via fino a ${\displaystyle g_{64}}$.^[5]

Ultime cifre del numero di Graham

È idealmente semplice pervenire alle ultime ${\displaystyle k}$ cifre del numero di Graham. Sfruttando la convergenza p-adica che caratterizza gli iperoperatori (dalla tetrazione in poi), è sufficiente calcolare le successive tetrazioni del ${\displaystyle 3}$ in modulo ${\displaystyle 10^{k}}$ (o sostituire a ${\displaystyle k}$ un qualsiasi intero compreso tra ${\displaystyle 1}$ e ${\displaystyle k}$ stesso). Le tetrazioni da eseguire, per ottenere tutte le "cifre stabili" (quelle che restano immutate tra la tetrazione di altezza ${\displaystyle h}$ e quelle di altezza ${\displaystyle h'>h}$) del numero di Graham, sono esattamente ${\displaystyle k+1}$^[6] e tale numero (gigantesco) è ben maggiore di ${\displaystyle g_{63}}$, ma molto minore di ${\displaystyle G:=g_{64}}$.

Ad esempio, calcolando (almeno) la tetrazione di base ${\displaystyle 3}$ e di altezza ${\displaystyle 501}$ (computando ${\displaystyle 3\uparrow \uparrow 501\mod 10^{500}}$), si ottiene:

 ...02425950695064738395657479136519351798334535362521
    43003540126026771622672160419810652263169355188780
    38814483140652526168785095552646051071172000997092
    91249544378887496062882911725063001303622934916080
    25459461494578871427832350829242102091825896753560
    43086993801689249889268099510169055919951195027887
    17830837018340236474548882222161573228010132974509
    27344594504343300901096928025352751833289884461508
    94042482650181938515625357963996189939679054966380
    03222348723967018485186439059104575627262464195387

che sono le ultime ${\displaystyle 500}$ cifre di ${\displaystyle G.}$

Note

1. Mauro Fiorentini, Graham (numero di), su bitman.name. URL consultato il 21 maggio 2014.
2. Guinness Book of World Records 1980, Guinness World Records, 1979, p. 193.
3. Michael Albanese, Graham's Problem (and Number) (PDF), su maths.adelaide.edu.au. URL consultato il 21 maggio 2014 (archiviato dall'url originale il 26 maggio 2013).
4. Jerome Barclay, Improved lower bound on an Euclidean Ramsey problem, su arxiv.org, 6 novembre 2008. URL consultato il 21 maggio 2014.
5. Susan Stepney, Graham's number, su www-users.cs.york.ac.uk. URL consultato il 21 maggio 2014.
6. Ripà, Marco (2011). La strana coda della serie n^n^…^n, Trento, UNI Service. Archiviato il 31 gennaio 2018 in Internet Archive. ISBN 978-88-6178-789-6

Voci correlate

• Teoria di Ramsey
• Googol
• Googolplex
• Megistone

Collegamenti esterni

• (EN) Eric W. Weisstein, Numero di Graham, su MathWorld, Wolfram Research.