Numero di Graham

Da Wikipedia, l'enciclopedia libera.

In matematica, il numero di Graham, così chiamato in onore di Ronald Graham, è considerato il primo numero di grandezza inconcepibile ad essere usato in una seria dimostrazione matematica riguardo ad un problema della teoria di Ramsey, soprannominato 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.[1]

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 Planck, 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 minuscola 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, o la quantità di cifre della quantità di cifre presenti nel numero, ma anche per la lunghezza della frase "quantità di cifre della quantità di cifre della quantità di cifre..." necessaria, o per una rappresentazione tramite tetrazione \underbrace{a^{a^{a^{\cdot^{\cdot}}}}}_{x\ volte}, indipendentemente dai valori usati per a e x.

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

Problema di Graham[modifica | modifica wikitesto]

Esempio di colorazione di un cubo di tre 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 la soluzione al Problema di Graham 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?[3]

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 Bruce Lee Rothschild nel 1971. Il maggiore limite inferiore conosciuto della soluzione è 13, come dimostrato da Jerome Barclay nel 2008[4]

Rappresentazione del Numero di Graham[modifica | modifica wikitesto]

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 3=3^3=27
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  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. 
volte
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}

Primo livello[modifica | modifica wikitesto]

Per avere un'idea della sconfinata grandezza del numero di Graham si possono seguire i passi necessari a sviluppare il primo livello g_{1}.

Si parte calcolando 3 tetratto 3:

3\uparrow\uparrow3=3^{3^3}=3^{27}=7625597484987.

Chiameremo questo numero a. Il successivo passo è calcolare la tetrazione ricorsiva di 3 per se stesso, ovvero:

3\uparrow\uparrow\uparrow3=3\uparrow\uparrow(3\uparrow\uparrow3)=3\uparrow\uparrow{a}= 
\left.
    \begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}\end{matrix}
  \right \}
  \left. 
    \begin{matrix}7625597484987\end{matrix}
  \right.

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 g_{1}, tuttavia, è necessario un altro passo di iterazione:


 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:


 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, ovvero talmente tante da non essere possibile scriverle tutte per mancanza di spazio nell'universo conosciuto.

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

Ultime cifre del numero di Graham[modifica | modifica wikitesto]

È idealmente semplice pervenire alle ultime 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 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[6] e tale numero (gigantesco) è ben maggiore di g_{63}, ma (al contempo) molto minore di G := g_{64}.

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

…02425950695064738395657479136519351798334535362521
 43003540126026771622672160419810652263169355188780
 38814483140652526168785095552646051071172000997092
 91249544378887496062882911725063001303622934916080
 25459461494578871427832350829242102091825896753560
 43086993801689249889268099510169055919951195027887
 17830837018340236474548882222161573228010132974509
 27344594504343300901096928025352751833289884461508
 94042482650181938515625357963996189939679054966380
 03222348723967018485186439059104575627262464195387

vale a dire le ultime 500 cifre di G.

Notes[modifica | modifica wikitesto]

  1. ^ Mauro Fiorentini, Graham (numero di). 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). URL consultato il 21 maggio 2014.
  4. ^ Jerome Barclay, Improved lower bound on an Euclidean Ramsey problem, 6 novembre 2008. URL consultato il 21 maggio 2014.
  5. ^ Susan Stepney, Graham's number. URL consultato il 21 maggio 2014.
  6. ^ Ripà, Marco (2011). La strana coda della serie n^n^…^n, Trento, UNI Service. ISBN 978-88-6178-789-6

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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