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 ${\displaystyle 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

File:CuboDiGraham.svg

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 ${\displaystyle 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 (${\displaystyle \uparrow \uparrow }$ ) rappresenta una tetrazione, ovvero 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 \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 \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:

${\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 avrà ottenuto il numero di Graham. In altre parole, se scriviamo ${\displaystyle 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:

${\displaystyle 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 ${\displaystyle 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.

Ultime cifre del Numero di Graham

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

Ad esempio, calcolando (almeno) la tetrazione di base 3 e di altezza 501 (computando [3^^501 (mod 10^500)]), otteniamo:

…02425950695064738395657479136519351798334535362521
 43003540126026771622672160419810652263169355188780
 38814483140652526168785095552646051071172000997092
 91249544378887496062882911725063001303622934916080
 25459461494578871427832350829242102091825896753560
 43086993801689249889268099510169055919951195027887
 17830837018340236474548882222161573228010132974509
 27344594504343300901096928025352751833289884461508
 94042482650181938515625357963996189939679054966380
 03222348723967018485186439059104575627262464195387,

vale a dire le ultime 500 cifre di G.

Notes

1. ^ Ripà, Marco (2011). La strana coda della serie n^n^…^n, Trento, UNI Service. ISBN 978-88-6178-789-6

Voci correlate

• Megistone
• Googolplex

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