Θεώρημα απείρων πιθήκων

Θεώρημα των απείρων πιθήκων: Αν δοθεί αρκετός χρόνος, ένας υποθετικός χιμπαντζής πληκτρολογώντας στην τύχη, θα παράξει ανάμεσα στα άλλα, σχεδόν σίγουρα και ένα από τα έργα του Σαίξπηρ.

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

Σε αυτό το πλαίσιο το «σχεδόν βέβαια» είναι μαθηματικός όρος με συγκεκριμένη έννοια, και ως «πίθηκος» δεν νοείται ένας πραγματικός πίθηκος, αλλά χρησιμοποιείται μεταφορικά ως μία αφηρημένη συσκευή που παράγει μία τυχαία σειρά γραμμάτων επ’ άπειρον. Το θεώρημα καταδεικνύει τους κινδύνους στους συλλογισμούς για το άπειρο όταν υπεισέρχεται η υπόθεση τεράστιου αλλά πεπερασμένου αριθμού και αντίστροφα. Η πιθανότητα να παράξει ο πίθηκος ένα κείμενο με μέγεθος αντίστοιχο του Άμλετ, είναι τόσο μικρή ώστε αν το πείραμα εκτελούνταν, η πιθανότητα να συμβεί μέσα σε ένα χρονικό διάστημα της τάξης μεγέθους της ηλικίας του σύμπαντος είναι μηδαμινή αλλά όχι μηδενική.

Παραλλαγές του θεωρήματος περιλαμβάνουν περισσότερους ή και άπειρους δακτυλογράφους, ενώ το κείμενο στόχος ποικίλει μεταξύ ολόκληρης βιβλιοθήκης και μίας μόνο πρότασης. Η ιστορία αυτών των θεωρημάτων ανιχνεύεται στο έργο του Αριστοτέλη Περὶ γενέσεως καὶ φθορᾶς και στο έργο του Κικέρωνα De natura deorum, εν συνεχεία στους Μπλεζ Πασκάλ και Τζόναθαν Σουίφτ, και τελικώς στα σύγχρονα θεωρήματα με τους εικονικούς γραφείς.

Στις αρχές του 20ου αιώνα, ο Εμίλ Μπορέλ και ο Άρθουρ Έντιγκτον χρησιμοποίησαν το θεώρημα για να δείξουν τις χρονικές κλίμακες των θεμελίων της στατιστικής μηχανικής. Διάφοροι χριστιανοί απολογητές από την μία και ο Ρίτσαρντ Ντόκινς από την άλλη έχουν διαφωνήσει για την καταλληλότητα των πιθήκων ως μεταφορά για την εξέλιξη

Το ενδιαφέρον του κοινού για τους πιθήκους που δακτυλογραφούν συντηρείται από τις πολλές εμφανίσεις του στην λογοτεχνία, την τηλεόραση, το ραδιόφωνο, την μουσική και το ίντερνετ. Το 2003 έγινε ένα πραγματικό πείραμα με μακάκους του είδους Macaca nigra. Το αποτέλεσμα της εργασίας τους ήταν πέντε σελίδες που αποτελούνταν κυρίως από το γράμμα ‘S’.

Επίλυση

Άμεση απόδειξη: Υπάρχει μια ευθεία απόδειξη του θεωρήματος. Αν δύο ενδεχόμενα είναι στατιστικά ανεξάρτητα, τότε η πιθανότητα να συμβούν και τα δύο ισούται με το γινόμενο των πιθανοτήτων να συμβεί το καθένα ξεχωριστά. Για παράδειγμα αν η πιθανότητα να βρέξει στο Μόντρεαλ μια συγκεκριμένη μέρα είναι 0.3 και η πιθανότητα να συμβεί σεισμός την ίδια μέρα στο Σαν Φρανσίσκο είναι 0.008 τότε η πιθανότητα να συμβούν και τα δύο είναι 0.3 × 0.008 = 0.0024.

Έστω ότι η γραφομηχανή έχει 50 πλήκτρα, και η λέξη που πρέπει να γραφτεί είναι ‘banana’. Δακτυλογραφώντας στην τύχη, η πιθανότητα το πρώτο γράμμα να είναι ‘b’ είναι 1/50, και η πιθανότητα το δεύτερο γράμμα να είναι ‘a’ είναι επίσης 1/50 κ.ο.κ, επειδή τα ενδεχόμενα είναι ανεξάρτητα. Έτσι, η πιθανότητα τα πρώτα έξι γράμματα να σχηματίσουν την λέξη ‘μπανάνα’ είναι

(1/50) × (1/50) × (1/50) × (1/50) × (1/50) × (1/50) = (1/50)⁶ 

μικρότερη από ένα στα 15 δισεκατομμύρια. Για τον ίδιο λόγο, η πιθανότητα και τα 6 επόμενα γράμματα να σχηματίσουν την λέξη ‘banana’ είναι επίσης (1/50))⁶, κ.ο.κ.

Από τα παραπάνω, η πιθανότητα να μην δακτυλογραφηθεί η λέξη banana σε ένα δεδομένο τμήμα 6 γραμμάτων είναι 1 − (1/50)⁶. Επειδή κάθε τμήμα δακτυλογραφείται ανεξάρτητα, η πιθανότητα X_n να μην δακτυλογραφηθεί μπανάνα σε κάθε ένα από τα πρώτα n τμήματα 6 γραμμάτων είναι

Καθώς το n αυξάνεται, το X_n γίνεται μικρότερο. Για n ένα εκατομμύριο, το X_n γίνεται περίπου 0.9999, αλλά για n 10 δισεκατομμύρια το X_n γίνεται περίπου 0.53 και για n 100 δισεκατομμύρια γίνεται περίπου 0.0017. Καθώς το n προσεγγίζει το άπειρο, η πιθανότητα X_n προσεγγίζει το μηδέν, που σημαίνει ότι για αρκετά μεγάλο n το X_n μπορεί να γίνει όσο μικρό είναι επιθυμητό.,^{[2] [σημ. 1]} και η πιθανότητα να δακτυλογραφηθεί μπανάνα προσεγγίζει το 100%.

Ο ίδιος συλλογισμός δείχνει γιατί τουλάχιστον ένας από τους άπειρους πιθήκους θα παράξει ένα κείμενο όσο γρήγορα θα παράγονταν από έναν τέλεια ακριβή δακτυλογράφο που θα το αντέγραφε από το πρωτότυπο. Σε αυτή την περίπτωση X_n = (1 − (1/50)⁶)ⁿ όπου το X_n αναπαριστά την πιθανότητα ένας από τους πρώτους n πιθήκους να δακτυλογραφήσει banana σωστά στην πρώτη προσπάθεια. Αν θεωρήσουμε 100 δισεκατομμύρια πιθήκους, η πιθανότητα πέφτει στο 0.17%, και καθώς ο αριθμός των πιθήκων n αυξάνεται, η τιμή του X_n – η πιθανότητα των πιθήκων που θα αποτύχουν να παράξουν το δεδομένο κείμενο – προσεγγίζει το μηδέν/ Το όριο για το n να τείνει στο άπειρο είναι μηδέν.

Ωστόσο, για οποιοδήποτε πλήθος πιθήκων με κάποιο τουλάχιστον φυσικό νόημα οι οποίοι να δακτυλογραφούν σε χρονικά διαστήματα με κάποιο τουλάχιστον φυσικό νόημα το αποτελέσματα είναι ανάποδο. Αν υπήρχαν τόσοι πίθηκοι όσα τα σωματίδια στο παρατηρήσιμο σύμπαν (10⁸⁰), και καθένας από αυτούς δακτυλογραφούσε με ρυθμό 1.000 πλήκτρα ανά δευτερόλεπτο για χρόνο πάνω από 100 φορές την ηλικία του σύμπαντος (10²⁰ seconds), η πιθανότητα να αναπαράγουν οι πίθηκοι ακόμα και ένα μικρό βιβλίο είναι σχεδόν μηδενική. Δείτε Πιθανότητες, παρακάτω.

Άπειρες συμβολοσειρές: Οι δύο προτάσεις παραπάνω μπορούν αν εκφραστούν πιο γενικά και πιο συνεπτυγμένα με όρους συμβολοσειρών, οι οποίες είναι ακολουθίες χαρακτήρων επιλεγμένες από ένα πεπερασμένο αλφάβητο:

*Δεδομένης μία άπειρης συμβολοσειράς όπου κάθε χαρακτήρας επιλέγεται τυχαία με κανονική κατανομή, οποιαδήποτε δεδομένη πεπερασμένη συμβολοσειρά θα εμφανιστεί σχεδόν βέβαια ώς υποσυμβολοσειρά σε κάποια θέση.

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

Και τα δύο απορρέουν εύκολα από το δεύτερο λήμμα Μπορέλ-Καντέλι. Για το δεύτερο θεώρημα, έστω E_k το ενδεχόμενο ότι η kστή συμβολοσειρά ξεκινάει με δεδομένο κείμενο. Εξαιτίας αυτού έχει μία σταθερή μη μηδενική πιθανότητα p να εμφανιστεί, τα E_k είναι ανεξάρτητα, και το παρακάτω άθροισμα αποκλίνει,

η πιθανότητα ότι άπειρα από τα E_k θα εφανιστούν είναι 1. Το πρώτο θεώρημα αποδεικνύεται αναλόγως. Μπορεί κανείς να χωρίσει την τυχαία συμβολοσειρά σε μη αλληλεπικαλυπτόμενα τμήματα που να ταιριάζουν στο μέγεθος του επιθυμητού κειμένου, και να κάνει E_k το ενδεχόμενο όπου το kστο τμήμα ισούται με την επιθυμητή συμβολοσειρά.^{[σημ. 2]}

Πιθανότητες: Αγνοώντας την στίξη, τα διαστήματα και τα κεφαλαία, ένας πίθηκος που δακτυλογραφεί τυχαία με κανονική κατανομή έχει πιθανότητα μία στις 26 να δακτυλογραφήσει σωστά το πρώτο γράμμα από τον Άμλετ. Έχει πιθανότητα μία στις 676 (26 × 26) να δακτυλογραφήσει τα πρώτα δύο γράμματα. Επειδή η πιθανότητα μειώνεται εκθετικά, στα είκοσι γράμματα είναι ήδη ένα στα 26²⁰ = 19,928,148,895,209,409,152,340,197,376 (σχεδόν 2 × 10²⁸). Για την περίπτωση ολόκληρου του κειμένου του Άμλετ, η πιθανότητα είναι υπερβολικά μικρή ώστε να γίνει αντιληπτή σε ανθρώπινους όρους. Το κείμενο του Άμλετ περιέχει περίπου 130.000 γράμματα.^{[σημ. 3]}

Έτσι η πιθανότητα είναι ένα στα 3.4 × 10^183,946 ώστε να δακτυλογραφηθεί σωστά το κείμενο στην πρώτη προσπάθεια. Ο μέσος αριθμός γραμμάτων που χρειάζεται να δακτυλογραφηθεί μέχρι να εμφανιστεί το κείμενο είναι επίσης 3.4 × 10^183,946,^{[σημ. 4]} ή συμπεριλαμβάνοντας και την στίξη, 4.4 × 10^360,783.^{[σημ. 5]}

Ακόμα και αν το παρατηρήσιμο σύμπαν ήταν γεμάτο πιθήκους που δακτυλογραφούσαν όλη την ώρα, η συνολική πιθανότητα να παράξουν ένα αντίγραφο του Άμλετ θα ήταν 1 / 10^183,800. Όπως το έθεσαν ο Τσαρλς Κάιτελ και ο Χέρμπερτ Κρέμερ, «η πιθανότητα για τον Άμλετ είναι έτσι μηδέν υπό οποιαδήποτε επιχειρησιακή έννοια…», και η πρόταση ότι οι πίθηκοι πρέπει τελικώς να πετύχουν «δίνει παραπλανητικό συμπέρασμα για τους πολύ μεγάλους αριθμούς.» Αυτό προέρχεται από το εγχειρίδιο τους στην θερμοδυναμική, το πεδίο του οποίου το στατιστικό υπόβαθρο έδωσε το κίνητρο για τις πρώτες γνωστές εμφανίσεις της υπόθεσης των πιθήκων που δακτυλογραφούν.^[3]

Ιστορία

Στατιστική μηχανική: Μία από τις μορφές που είναι γνωστό σήμερα το θεώρημα, με τους πίθηκους που δακτυλογραφούν, εμφανίστηκε στο άρθρο του Εμίλ Μπορέλ Mécanique Statistique et Irréversibilité (1913, Στατιστική μηχανική κα μη αναστρεψιμότητα),),^[4] και στο βιβλίο του, Le Hasard (1914). Οι πίθηκοί του δεν είναι πραγματικοί, αλλά μία μεταφορά για ένα φανταστικό τρόπο να παραχθεί μία μεγάλη, τυχαία ακολουθία γραμμάτων.

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

Ο φυσικός Άρθουρ Έντιγκτον προχώρησε την σκέψη του Μπορέλ παραπέρα στο έργο του Nature of the Physical World (Η Φύση του Φυσικού Κόσμου, 1928), γράφοντας:

Αν αφήσω τα δάκτυλά μου να περιπλανηθούν άσκοπα στα πλήκτρα μιας γραφομηχανής μπορεί να συμβεί το κείμενό μου να είναι μία πρόταση με νόημα. Αν μία στρατιά πιθήκων χτυπούσαν πλήκτρα σε γραφομηχανές μπορεί να έγραφαν όλα τα βιβλία του Βρετανικού Μουσείου. Η πιθανότητα να το πετύχουν αυτό είναι σαφώς μεγαλύτερη από αυτήν των μορίων να επιστρέψουν στο ένα μισό του δοχείου.^[5]

Με αυτά τα παραδείγματα ο αναγνώστης καλούνταν να αναλογιστεί την τεράστια απιθανότητα η εργασία μεγάλου αλλά πεπερασμένου αριθμού πιθήκων για μεγάλο αλλά πεπερασμένο χρονικό διάστημα να έχει αποτέλεσμα ένα σημαντικό έργο με την ακόμη μεγαλύτερη απιθανότητα συγκεκριμένων φυσικών φαινομένων. Κάθε φυσική διεργασία που είναι πιο απίθανο να συμβεί από την επιτυχία τέτοιων πιθήκων θεωρείται πρακτικώς απίθανη, και μπορεί να ειπωθεί με ασφάλεια ότι δεν πρόκειται να συμβεί ποτέ.^[3]

Προέλευση και «Η Ολική Βιβλιοθήκη»

Σε ένα δοκίμιο του 1939 με τίτλο «Η Ολική Βιβλιοθήκη» (The Total Library), ο Αργεντίνος συγγραφέας Χόρχε Λουίς Μπόρχες, εντόπισε την προέλευση της έννοιας των άπειρων πιθήκων στα Μεταφυσικά του Αριστοτέλη. Εξηγώντας τις αντιλήψεις του Λεύκιππου, κατά τον οποίο ο κόσμος προήλθε από τυχαίους συνδυασμούς ατόμων, ο Αριστοτέλης σημείωσε ότι τα άτομα αυτά καθεαυτά είναι ομογενή και ότι οι πιθανές διατάξεις τους διαφέρουν μόνο στο σχήμα, την θέση και την διάταξη. Στο έργο του, Περί γενέσεως και φθοράς, συγκρίνει με αυτό τον τρόπο με τον οποίο μια τραγωδία και μια κωμωδία αποτελείται από τα ίδια «άτομα», δηλαδή αλφαβητικούς χαρακτήρες.^[6]

Τρεις αιώνες αργότερα, ο Κικέρωνας στο έργο του De natura deorum (Περί της φύσεως των θεών) διαφώνησε με την ατομική κοσμοθεώρηση:

Αυτός ο οποίος το πιστεύει αυτό μπορεί επίσης να πιστεύει ότι αν μία μεγάλη ποσότητα από τα εικοσιένα γράμματα, φτιαγμένα είτε από χρυσό είτε από άλλη ύλη, πετιόνταν στο έδαφος, θα έπεφταν με τέτοιο τρόπο ώστε να σχηματίσουν τα Χρονικά του Έννιου. Αμφιβάλω αν η τύχη θα μπορούσε να φτιάξει έστω ένα στίχο από αυτά.^[7]

Ο Μπόρχες ακολουθεί την ιστορία αυτού του επιχειρήματος εν συνεχεία στον Μπλεζ Πασκάλ και τον Τζόναθαν Σουίφτ, και παρατηρεί ότι στον καιρό του το λεξιλόγιο είχε αλλάξει. Το 1939, ο ιδιωματισμός ήταν «ότι μισή ντουζίνα πίθηκοι με γραφομηχανές θα μπορούσαν, σε μερικές αιωνιότητες να παράξουν όλα τα βιβλία του Βρετανικού Μουσείου» Στο ο οποίο ο Μπόρχες προσέθεσε, «ένας αθάνατος πίθηκος θα αρκούσε» Ο Μπόρχες κατόπιν φαντάζεται τα περιεχόμενα της Ολικής Βιβλιοθήκης τα οποία θα παράγονταν από αυτή την επιχείρηση στην πλήρη έκτασή της:

Τα πάντα: η αναλυτική ιστορία του μέλλοντος, οι Αιγύπτιοι του Αισχύλου, ο ακριβής αριθμός των φορών που τα νερά του Γάγγη αντικατόπτρισαν την πτήση ενός γερακιού, η μυστική και αληθινή φύση της Ρώμης, η εγκυκλοπαίδεια Novalis θα είχε κατασκευάσει τα όνειρά και ημι-όνειρα μου της αυγής της 14ης Αυγούστου 1934, την απόδειξη του θεωρήματος του Φερμά, τα άγραφα κεφάλαια του Edwin Drood, τα ίδια κεφάλαια μεταφρασμένα στην γλώσσα που μιλούν οι Γαράμαντες, τα παράδοξα που εφηύρε ο Μπέρκλεϊ για τον Χρόνο αλλά δεν δημοσίευσε, τα βιβλία του σιδήρου του Urizen, τις πρόωρες εμπνεύσεις του Stephen Dedalus, οι οποίες θα ήταν χωρίς νόημα πριν από ένα κύκλο χιλίων χρόνων, το γνωστικό Ευαγγέλιο του Βασιλίδη, το τραγούδι που τραγούδησαν οι Σειρήνες, ο πλήρης κατάλογος της Βιβλιοθήκης, η απόδειξη ανακρίβειας αυτού του καταλόγου.

Τα πάντα: αλλά για κάθε γραμμή με νόημα ή ακριβούς δεδομένου θα υπήρχαν εκατομμύρια κακοφωνίες χωρίς νόημα, φραστικά συνονθυλεύματα και ανοησίες. Τα πάντα: αλλά όλες οι γενιές της ανθρωπότητας θα μπορούσαν να περάσουν από τα ιλιγγιώδη ράφια, ράφια που εξαλείφουν την μέρα και στα οποία βρίσκεται το χάος, για να ανταμειφθούν με μία ανεκτή σελίδα.^[8]

Η έννοια της ολικής βιβλιοθήκης του Μπόρχες ήταν το κύριο θέμα του δημοφιλούς βιβλίου του «Η Βιβλιοθήκη της Βαβέλ» (1941), στο οποίο περιγράφεται μία αφάνταστα τεράστια βιβλιοθήκη η οποία αποτελείται από συμπλεγμένες εξαγωνικές αίθουσες, που μαζί περιέχουν όλους τους πιθανούς τόμους που θα μπορούσαν να συντεθούν από τα γράμματα του αλφαβήτου και μερικούς χαρακτήρες στίξης.

Σημειώσεις

1. Αυτό δείχνει ότι η πιθανότητα δακτυλογράφησης banana σε ένα από τα προκαθορισμένα τμήματα επτά γραμμάτων τείνει στο 1. Επιπροσθέτως, η λέξη μπορεί να εμφανιστεί ανάμεσα σε δύο τμήματα, έτσι η εκτίμηση που δίνεται είναι συντηριτική.
2. Το πρώτο θεώρημα αποδεικνύεται με παρόμοιο αν και πιο έμεσο τρόπο στο Gut, Allan (2005). Probability: A Graduate Course. Springer. σελ. 97–100. ISBN 0387228330.
3. Χρησιμοποιώντας το κείμενο από το εγχείρημα Gutenberg, υπάρχουν 132680 γράμματα του αλφαβήτου και 199749 χαρακτήρες συνολικά
4. Για οποιαδήποτε επιθυμητή συμβολοσειρά 130.000 γραμμάτων από το σύνολο a-z, ο μέσος όρος γραμμάτων που χρειάζεται να δακτυλογραφηθεί μέχρι να εμφανιστεί η συμβολοσειρά είναι (στρογγυλοποιημένος)3.4 × 10^183,946, εκτός από την περίπτωση που όλα τα γράμματα της επιθυμητής συμβολοσειράς είναι ίσα, στην οποία περίπτωση η τιμή είναι περίπου 4% μεγαλύτερη, 3.6 × 10^183,946. Σε αυτή την περίπτωση, αποτυχία να εμφανιστεί η σωστή συμβολοσειρά σε μία συγκεκριμένη θέση μειώνεται περίπου 4% In that case failure to have the correct string starting from a particular position reduces with about 4% the probability of a correct string starting from the next position (i.e., για αλληλεπικαλυπτόμενες θέσεις τα ενδεχόμενα να υπάρχουν σωστές συμβολοσειρές δεν είναι ανεξάρτητα, σε αυτή την περίπτωση υπάρχει θετική συσχέτιση μεταξύ των δύο επιτυχιών, έτσι η πιθανότητα μετά από αποτυχία είναι μικρότερη από την πιθανότητα επιτυχίας εν γένει). Η τιμή 3.4 × 10^183,946 προκύπτει από το n = 26¹³⁰⁰⁰⁰ λαμβάνοντας τον λογάριθμο των δύο πλευρών: log₁₀(n) = 1300000×log₁₀(26) = 183946.5352, άρα n = 10^0.5352 × 10¹⁸³⁹⁴⁶ = 3.429 × 10¹⁸³⁹⁴⁶.
5. 26 γράμματα ×2 για κεφαλαία, 12 για χαρακτήρες στίξης = 64, 199749×log₁₀(64) = 4.4 × 10^360,783.

Παραπομπές

1. «No words to describe monkeys’ play». BBC News. 2003-05-09. Ανακτήθηκε στις 2009-07-25.
2. Isaac, Richard E. (1995). The Pleasures of Probability. Springer. σελ. 48–50. ISBN 038794415X. Isaac generalizes this argument immediately to variable text and alphabet size; the common main conclusion is on p.50.
3. Kittel, Charles and Herbert Kroemer (1980). Thermal Physics (2nd ed.). W. H. Freeman Company. σελ. 53. ISBN 0-7167-1088-9.
4. Émile Borel (1913). «Mécanique Statistique et Irréversibilité». J. Phys. 5e série 3: 189–196.
5. Arthur Eddington (1928). The Nature of the Physical World: The Gifford Lectures. New York: Macmillan. σελ. 72. ISBN 0-8414-3885-4.
6. Aristotle, De Generatione et Corruptione, 315b14.
7. Marcus Tullius Cicero, De natura deorum, 2.37. Translation from Cicero’s Tusculan Disputations; Also, Treatises On The Nature Of The Gods, And On The Commonwealth, C. D. Yonge, principal translator, New York, Harper & Brothers Publishers, Franklin Square. (1877). Downloadable text.
8. Borges, Jorge Luis. «La biblioteca total» (The Total Library), Sur No. 59, August 1939. Trans. by Eliot Weinberger. In Selected Non-Fictions (Penguin: 1999), ISBN 0-670-84947-2.