Numero di Graham

Il numero di Graham, così chiamato in onore di Ronald Graham, è considerato il primo numero di dimensioni inconcepibili ad essere usato in una seria dimostrazione matematica, il Problema di Graham, del quale rappresenta il limite superiore. Tale numero è estremamente più grande di altri famosi numeri grandi come il googol, il googolplex e persino il Megistone: in effetti è talmente grande che non è possibile dare un'idea delle sue dimensioni in termini non matematici senza sottostimarlo grandemente.

Come molti altri numeri di grandi dimensioni, una sua rappresentazione binaria completa è scientificamente impossibile, in quanto ipotizzando di essere in grado di immagazzinare un bit in un singolo volume di plank, lo spazio necessario ad 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 infintesima parte di questo numero. Tuttavia, nel caso del numero di Graham, lo stesso limite si ripresenta qualora volessimo rappresentare la quantità di cifre presenti nel numero, per qualsiasi notazione scientifica o addirittura per una rappresentazione tramite tetrazione del tipo $a ^{ b ^{ c ^{ \cdot ^{ \cdot ^{ \cdot}}}}}$, indipendentemente dai valori usati negli esponenti.

Il Numero di Graham è stato riportato nel Guinness dei Primati del 1980.

Problema di Graham

Esempio di colorazione di un cubo di 3 dimensioni (n=3) con riportato un sub-grafo 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 sub-grafi completi, piani e monocromi dimostrando empiricamente che, se esiste una soluzione al Problema di Graham, essa deve avere n>3.

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

La soluzione del problema non è conosciuta, il Numero di Graham è un limite massimo dell'intervallo in cui si possono trovare le soluzioni del problema, come dimostrato da Graham e da B.L. Rothschild nel 1971. Il maggiore limite inferiore conosciuto della soluzione è 13, come dimostrato da Jerome Barclay nel 2008.

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 ($\uparrow \uparrow$) rappresenta una tetrazione, ovvero una potenza ricorsiva, le tre frecce ($\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:
$3\uparrow \uparrow 3=3^{3^3}=3^{27}=7625597484987$
$3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow 3)= \begin{matrix} &3\underbrace{\uparrow \uparrow 3 \uparrow \uparrow 3 \uparrow \uparrow \dots \uparrow \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.$
e via dicendo.

In questa notazione, il numero di Graham ha valore:

$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 avrà ottenuto il numero di Graham. In altre parole, se scriviamo $3 \uparrow^{k} 3$ per indicare un 3 seguito da k frecce (con il senso che si è visto sopra), allora il numero di Graham può essere definito come:

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

Da notare che anche il numero espresso dal primo livello $g_{1}$, nonostante sia di semplice comprensione in termini matematici, è un numero impossibile da rappresentare per intero in questo universo, e tuttavia rimangono altri 63 passi per arrivare al Numero di Graham.

Il numero di Graham è esprimibile, nella nuova gerarchia di iperoperatori [1], tramite un valore decimale della base 1<n<2. Ovvero, per tutti i valori interi di n tali che n*n>n, l'iperoperatore di rango minimo della suddetta gerarchia genera comunque un numero maggiore di G.

Bibliografia

[1] Marco Ripà - http://www.scribd.com/doc/77714896/The-largest-number-ever-il-numero-dei-record

Voci correlate

• Megistone
• Googolplex

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica