Αριθμός του Γκράχαμ

Ο **αριθμός του Γκράχαμ** (αγγλικά: *Graham's number*) είναι ασύλληπτα μεγάλος ακέραιος αριθμός ο οποίος προκύπτει ως το άνω όριο στην απάντηση προβλήματος του μαθηματικού πεδίου της θεωρίας Ράμσεϋ. Ονομάστηκε βάσει του μαθηματικού Ρόναλντ Γκράχαμ ο οποίος χρησιμοποίησε τον αριθμό ως μια απλοποιημένη εξήγηση των άνω ορίων κάποιου προβλήματος στο οποίο εργαζόταν. Το σύνολο των ψηφίων από τα οποία απαρτίζεται ο αριθμός σε τόσο μεγάλη κλίμακα, δεν είναι δυνατό να εκφραστεί με μαθηματικές δυνάμεις ούτε καν υψωμένες διαδοχικά ως \scriptstyle a ^{ b ^{ c ^{ \cdot ^{ \cdot ^{ \cdot}}}}}ή τον παραγοντικό τελεστή !, και χρειάζεται ειδική σημειολογία, ενώ δεν είναι δυνατό ούτε να αποτυπωθούν γραπτά καθώς η καταγραφή του συνόλου των ψηφίων θα απαιτούσε μεγαλύτερο χώρο από αυτόν που είναι διαθέσιμος στο παρατηρήσιμο σύμπαν, υποθέτoντας πως το κάθε ψηφίο θα καταλάμβανε τον υπερμικροσκοπικό χώρο του 4.2217 × 10−105 m3 ο οποίος αντιστοιχεί σε μια μονάδα όγκου Πλανκ η οποία είναι η μικρότερη δυνατή μετρήσιμη ποσότητα όγκου. Επίσης, δεν είναι ούτε δυνατό να αναπαρασταθεί γραπτά απλά το σύνολο των ψηφίων του αριθμού αυτού αντί ο ίδιος ο αριθμός. Ωστόσο υπάρχουν τρόποι ώστε να βρεθούν το ποιά είναι τα τελευταία ψηφία του αριθμού, για παράδειγμα τα 12 τελευταία ψηφία του είναι τα ...262464195387.

Ο αριθμός αυτός αργότερα περιγράφθηκε στο επιστημονικό περιοδικό *[[Scientific American]]* το 1977, γνωστοποιώντας τον στο ευρύτερο αναγνωστικό κοινό. Κατά την εποχή όπου διατυπώθηκε, αποτέλεσε τον μεγαλύτερο θετικό ακέραιο ο οποίος χρησιμοποιήθηκε ποτέ σε δημοσιευμένη μαθηματική απόδειξη. Ακολούθως το 1980 ο αριθμός δημοσιεύτηκε στο βιβλίο των Ρεκόρ Γκίνες το 1980 κάνοντας τον ακόμη πιο γνωστό. Κατά τις επόμενες δεκαετίες εμφανίστηκαν ακόμη μεγαλύτεροι ακέραιοι όπως ο TREE(3) οι οποίοι είναι πολύ μεγαλύτεροι ακόμη και από τον αριθμό του Γκράχαμ και έχουν επίσης χρησιμοποιηθεί σε δημοσιευμένες μαθηματικές μελέτες, ή οι *[[αριθμοί busy beaver]]* οι οποίοι είναι τόσο μεγάλοι ώστε δεν μπορούν να παραχθούν βάσει μικρών αναδρομικών μεθόδων για να περιγράψουν κάποιο άνω όριο. Ωστόσο ο αριθμός του Γκράχαμ είναι κατά πολύ μεγαλύτερος από άλλους μεγάλους γνωστούς αριθμούς, όπως ο αριθμός του Σκιούς και ο αριθμός του Μόζερ, οι οποίοι με την σειρά τους είναι κατά πολύ μεγαλύτεροι από το γκούγκολ.

Ο αριθμός είναι δυνατό να αναπαρασταθεί μέσω της ειδικής μαθηματικής σημειολογίας του Ντόναλντ Κνουθ, γνωστής ως σημειολογίας Κνουθ άνω βέλους η οποία χρησιμοποιείται για εξαιρετικά μεγάλους αριθμούς και την οποία χρησιμοποίησε ο ίδιος ο Γκράχαμ κατά την διατύπωση του αριθμού του.

## Χρήση

Ο αριθμός του Γκράχαμ σχετίζεται με το παρακάτω πρόβλημα της θεωρίας Ράμσεΐ:

Το 1971, οι Γκράχαμ και Ρόθτσιλντ έλυσαν το πρόβλημα αυτό αποδεικνύοντας πως η λύση είναι *N**, όπου ισχύει η συνθήκη ορίου 6 ≤ *N** ≤ *N*, με το *N* να αποτελεί έναν μεγάλο αλλά ρητά καθορισμένο αριθμό \scriptstyle F^7(12) \;=\; F(F(F(F(F(F(F(12))))))), όπου \scriptstyle F(n) \;=\; 2\uparrow^n 3 στη σημειολογία Κνουθ άνω βέλους. Με την εναλλακτική μέθοδο της αλυσιδωτής σημειολογίας βέλους Κόνγουεϊ ο αριθμός είναι μεταξύ 4 → 2 → 8 → 2 και 2 → 3 → 9 → 2. Το 2004 σμικρύνθηκε μέσω των άνω ορίων στον αριθμό Χέιλς-Τζιούετ σε \scriptstyle N' \;=\; 2\;\uparrow\uparrow\uparrow\;6. Το 2003 το κάτω όριο διαμορφώθηκε από 6 σε 11, και το 2008 σε 13. Έτσι τα εκτιμώμενα όρια για το *N** είναι 13 ≤ *N** ≤ *N*'.

## Ορισμός

### Σημειολογία Κνουθ
Ο αριθμός ορίζεται ως:
:
\left.
 \begin{matrix}
  G &=&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots\cdots \uparrow}3 \\
    & &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots \uparrow}3 \\
    & &\underbrace{\qquad\;\; \vdots \qquad\;\;} \\
    & &3\underbrace{\uparrow \uparrow \cdots\cdot\cdot \uparrow}3 \\
    & &3\uparrow \uparrow \uparrow \uparrow3
 \end{matrix}
\right \} \text{64 επίπεδα}

:
όπου ο αριθμός βελών σε κάθε επίπεδο ορίζεται από την τιμή του επόμενου επιπέδου κάτω από αυτό, όπως:

:G = g_{64},\text{ όπου }g_1=3\uparrow\uparrow\uparrow\uparrow 3,\  g_n = 3\uparrow^{g_{n-1}}3,

και όπου η εκθετική γραφή περιγράφει το πόσα βέλη χρησιμοποιούνται. Εν τέλει, ο αριθμός Γκράχαμ περιγράφεται σε 64 τέτοια επίπεδα. Το πρώτο βήμα αφορά τον υπολογισμό του *g*1 με τέσσερα άνω βέλη μεταξύ των 3αριών, το δεύτερο βήμα είναι ο υπολογισμός του *g*2 με *g*1 άνω βέλη μεταξύ των 3αριών, και ακολουθείται η ίδια διαδικασία για όλα τα επόμενα επίπεδα μέχρι τον τελικό υπολογισμό του *G* = *g*64 με *g*63 άνω βέλη μεταξύ των 3αριών.

### Σημειολογία Κόνγουεϊ
Στην αλυσιδωτή σημειολογία βέλους Κόνγουεϊ ο αριθμός εκφράζεται με την μορφή \scriptstyle f(n) \;=\; 3 \rightarrow 3 \rightarrow n, και τα όρια του καθορίζονται ως:

: 3\rightarrow 3\rightarrow 64\rightarrow 2 

### Μέγεθος
Προσεγγιστικά, ο αριθμός των 3αριών σε κάθε επίπεδο, αν αναπαριστώνταν σε εκθετική μορφή θα περιείχε το παρακάτω αριθμούς σε κάθε εκθέτη (σύνολο ψηφίων έτσι ώστε να αναπαρασταθεί ο αριθμός του εκθέτη):
 ν=1  1ο επίπεδο εκθέτη:  3
      
 ν=2  2ο επίπεδο εκθέτη:  3↑3↑3 (το σύνολο 3αριών από το ν-1 επίπεδο είναι 3) = 7625597484987
      
 ν=3  3ο επίπεδο εκθέτη:  3↑3↑3↑3↑...↑3 (το σύνολο 3αριών από το ν-1 επίπεδο είναι 7625597484987) = …
      
       ⋮
      
 ν=ν *g*1 = *ν*ό επίπεδο:  3↑3↑3↑3↑3↑3↑3↑...↑3 (σύνολο 3αριών από το *ν-1*ό επίπεδο)

όπου το σύνολο τριαριών για κάθε επίπεδο εκθέτη δίνεται από το αμέσως προηγούμενο επίπεδο. Ακόμη και το ίδιο το *ν* το οποίο είναι απλώς το σύνολο των επιπέδων εκθέτη, είναι αφάνταστα μεγάλο και δεν μπορεί να αναπαρασταθεί.

## Υπολογισμός των τελευταίων ψηφίων
Ο *πύργος εκθετών* του αριθμού Γκράχαμ είναι της μορφής 3↑↑ν (όπου το ν είναι ένας πάρα πολύ μεγάλος αριθμός), έτσι τα πλέον *δεξιά* ψηφία του ικανοποιούν ορισμένα χαρακτηριστικά τα οποία είναι κοινά σε όλα τα επίπεδα του εκθετικού πύργου. Μια από αυτές τις ιδιότητες είναι ότι *όλα τα επίπεδα τα οποία έχουν ύψος μεγαλύτερο από ψ, διαθέτουν την ίδια ακολουθία ψ των πλέον δεξιών ψηφίων*. Αυτή είναι ειδική περίπτωση μιας πιο γενικής ιδιότητας, πως *τα ψ πλέον δεξιά στοιχεία όλων αυτών των επιπέδων με ύψος μεγαλύτερο από ψ*+2, *είναι* *ανεξάρτητα από τα κορυφαία 3 στον πύργο*, δηλαδή τα κορυφαία 3 μπορούν να αλλαχτούν σε οποιονδήποτε μη αρνητικό ακέραιο χωρίς να επηρεαστούν τα δ πλέον δεξιά ψηφία.

Για ένα ορισμένο ύψος εκθετικού πύργου και σύνολο ψηφίων *ψ*, το πλήρες εύρος των αριθμών με *ψ*-ψηφία (10*ψ* από αυτά) δεν διαδραματίζεται, ωστόσο μια ορισμένη μικρότερη υποομάδα των τιμών αυτών επαναλαμβάνεται κυκλικά. Το μήκος του κύκλου αυτού και κάποιες από τις τιμές (σε παρένθεση) είναι όπως παρακάτω:

Τα συγκεκριμένα πλέον δεξιά *ψ* ψηφία είναι τα ίδια με όλα τα επίπεδα του εκθετικού πύργου, και αναπτύσσονται περαιτέρω καθώς το ύψος αυξάνει.

Ένας απλός αλγόριθμος για τον υπολογισμό των ψηφίων αυτών είναι:
* για χ = 3,
* επανέλαβε, *ψ* φορές την ανάθεση *χ* = 3*χ* mod 10ψ.
* παρέλειψε τα όποια μηδενικά προκύπτουν στην αρχή του αριθμού,
* η τελική τιμή που προκύπτει για το χ αποτελείται από τα *ψ* πλέον δεξιά δεκαδικά ψηφία το 3↑↑*ν*, όπου *ν* > *ψ*. (αν η τελική τιμή του χ έχει λιγότερα από ψ ψηφία, τότε ο απαιτούμενος αριθμός 0 στην αρχή του αριθμού πρέπει να προστεθεί)
* όρισε το *k* ως την πληθικότητα των σταθερών αυτών στοιχείων, τα οποία ικανοποιούν την μαθηματική αναλογία G(mod 10*k*)≡[GG](mod 10*k*).
*k*=*t*-1, όπου G(*t*):=3↑↑*t*. Συνεπάγεται πως .

Ο παραπάνω αλγόριθμος παράγει τα 500 πλέον δεξιά (*τελευταία*) ψηφία του αριθμού του Γκράχαμ:

   …02425950695064738395657479136519351798334535362521
    43003540126026771622672160419810652263169355188780
    38814483140652526168785095552646051071172000997092
    91249544378887496062882911725063001303622934916080
    25459461494578871427832350829242102091825896753560
    43086993801689249889268099510169055919951195027887
    17830837018340236474548882222161573228010132974509
    27344594504343300901096928025352751833289884461508
    94042482650181938515625357963996189939679054966380
    03222348723967018485186439059104575627262464195387

## Παραπομπές


## Σχετική βιβλιογραφία
* ; reprinted (revised) in Gardner (2001), cited below.
* 
* 
*  The explicit formula for *N* appears on p.&nbsp;290. This is not the "Graham's number" *G* published by Martin Gardner.
*  On p.&nbsp;90, in stating "the best available estimate" for the solution, the explicit formula for *N* is repeated from the 1971 paper.

## Εξωτερικοί σύνδεσμοι
* Graham's number- Mathworld
* 

Γκραχαμ