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

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

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

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

 Χρήση 
μικρογραφία|
Παράδειγμα δίχρωμου τρισδιάστατου κύβου ο οποίος περιέχει ένα μονοχρωματισμένο ομοεπίπεδο υπογράφο τεσσάρων κορυφών. Ο υπογράφος αναπαριστάται ξεχωριστά κάτω από τον κύβο.
Ο αριθμός του Γκράχαμ σχετίζεται με το παρακάτω πρόβλημα της θεωρίας Ράμσεΐ:

Το 1971, οι Γκράχαμ και Ρόθτσιλντ έλυσαν το πρόβλημα αυτό αποδεικνύοντας πως η λύση είναι N*, όπου ισχύει η συνθήκη ορίου 6 ≤ N* ≤ N, με το N να αποτελεί έναν μεγάλο αλλά ρητά καθορισμένο αριθμό , όπου  στη σημειολογία Κνουθ άνω βέλους. Με την εναλλακτική μέθοδο της αλυσιδωτής σημειολογίας βέλους Κόνγουεϊ ο αριθμός είναι μεταξύ 4 → 2 → 8 → 2 και 2 → 3 → 9 → 2. Το 2004 σμικρύνθηκε μέσω των άνω ορίων στον αριθμό Χέιλς-Τζιούετ σε . Το 2003 το κάτω όριο διαμορφώθηκε από 6 σε 11, Exoo refers to the Graham & Rothschild upper bound N by the term "Graham's number". This is not the "Graham's number" G published by Martin Gardner. και το 2008 σε 13. Έτσι τα εκτιμώμενα όρια για το N* είναι 13 ≤ N* ≤ N'''.

 Ορισμός 

 Σημειολογία Κνουθ 
Ο αριθμός ορίζεται ως:

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

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

 Σημειολογία Κόνγουεϊ 
Στην αλυσιδωτή σημειολογία βέλους Κόνγουεϊ ο αριθμός εκφράζεται με την μορφή , και τα όρια του καθορίζονται ως:

 Μέγεθος 
Προσεγγιστικά, ο αριθμός των 3αριών σε κάθε επίπεδο, αν αναπαριστώνταν σε εκθετική μορφή θα περιείχε το παρακάτω αριθμούς σε κάθε εκθέτη (σύνολο ψηφίων έτσι ώστε να αναπαρασταθεί ο αριθμός του εκθέτη):
 ν=1  1ο επίπεδο εκθέτη:  3

 ν=2  2ο επίπεδο εκθέτη:  3↑3↑3 (το σύνολο 3αριών από το ν-1 επίπεδο είναι 3) = 7625597484987

 ν=3  3ο επίπεδο εκθέτη:  3↑3↑3↑3↑...↑3 (το σύνολο 3αριών από το ν-1 επίπεδο είναι 7625597484987) = …

       ⋮

 ν=ν g1 = νό επίπεδο:  3↑3↑3↑3↑3↑3↑3↑...↑3 (σύνολο 3αριών από το ν-1ό επίπεδο)

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

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

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

+ Αριθμός διαφορετικών πιθανών τιμών για το 3↑3↑…3↑x όταν όλα εκτός από τα d τελευταία ψηφία αγνοούνται Αριθμός ψηφίων (ψ)  3↑x  3↑3↑x  3↑3↑3↑x  3↑3↑3↑3↑x  3↑3↑3↑3↑3↑x 1 4  (1,3,9,7)  2  (3,7)  1  (7) 1  (7)  1  (7) 2 20   (01,03,…,87,…,67)  4  (03,27,83,87)  2  (27,87)  1  (87)  1  (87) 3 100  (001,003,…,387,…,667)  20  (003,027,…387,…,587)  4  (027,987,227,387) 2  (987,387)  1  (387)

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

Ένας απλός αλγόριθμος για τον υπολογισμό των ψηφίων αυτών είναι:
 για χ = 3,
 επανέλαβε, ψ φορές την ανάθεση χ = 3χ mod 10ψ.
 παρέλειψε τα όποια μηδενικά προκύπτουν στην αρχή του αριθμού,
 η τελική τιμή που προκύπτει για το χ αποτελείται από τα ψ πλέον δεξιά δεκαδικά ψηφία το 3↑↑ν, όπου ν > ψ. (αν η τελική τιμή του χ έχει λιγότερα από ψ ψηφία, τότε ο απαιτούμενος αριθμός 0 στην αρχή του αριθμού πρέπει να προστεθεί)
 όρισε το k ως την πληθικότητα των σταθερών αυτών στοιχείων, τα οποία ικανοποιούν την μαθηματική αναλογία G(mod 10k)≡[GG](mod 10k).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. 290. This is not the "Graham's number" G published by Martin Gardner.
  On p. 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


Γκραχαμ