משפט הקוף המקליד

אם נמתין די הצורך, גם שימפנזה המקליד באקראי יקליד לבסוף את כל יצירות שייקספיר

משפט הקוף המקליד הוא טענה מתמטית פשוטה, לפיה אם נבחר טקסט באורך סופי, אז הוא יופיע ברצף אינסופי של תווים אקראיים המוגרלים מהתפלגות אחידה (אך לאו דווקא מהתפלגות זו) בהסתברות $1$. בניסוח פופולרי, ברוח מאמרו של המתמטיקאי הצרפתי אמיל בורל, בו הופיע המשפט לראשונה, אפשר לומר שאם קוף מקליד תווים אקראיים במכונת כתיבה במשך זמן הולך וגדל ללא מגבלה - לבסוף יעבור מספיק זמן כך שיופיעו בטקסט כל כתבי ויליאם שייקספיר.

הוכחת הטענה

ההסתברות שיתרחשו שני מאורעות בלתי-תלויים שווה למכפלת ההסתברויות שלהם; לדוגמה, אם ההסתברות שפרוסת לחם תיפול על הצד המרוח בחמאה היא $0.5$, וההסתברות ש"נמר עם גדי ירבץ" היא $0.7$, הרי שההסתברות ששני המאורעות יתרחשו היא $0.35$, זאת בהנחה שאין תלות בין המאורעות.

נניח כעת שברשותנו מקלדת בעלת חמישים תווים, ונאמר שעל הקוף להקליד את המילה "אנציקלופדיה". ההסתברות שהאות הראשונה שיקליד תהיה אל"ף היא אחת לחמישים, דהיינו, $0.02$. ההסתברות שיקליד את האות אל"ף ואחריה את האות נו"ן היא אחת לחמישים כפול אחת לחמישים, לשון אחר, $0.0004$. הסיכוי שאחת־עשרה אותיות רצופות שיקליד יאייתו את המילה "אנציקלופדיה" הוא נמוך מאוד: אחת לחמישים בחזקת $11$, שהן $0.0000000000000000002048$.

ההסתברות, $p$, לכך שאחת-עשרה האותיות הראשונות לא ייצרו את המילה "אנציקלופדיה" היא כמעט ודאית:

$$p=1-0.0000000000000000002048=99.99999999999999997952\,\%$$

ניתן לקוף להדפיס עוד $11$ אותיות. אם עדיין לא מופיעה המילה "אנציקלופדיה", הרי שהיא אינה מופיעה במקטע בן אחת-עשרה האותיות הראשונות, וגם לא באחת-עשרה האותיות האחרונות. מכיוון שאלו מקטעים זרים, האותיות נבחרות באופן בלתי-תלוי בכל אחד מהם בנפרד, ולכן גם המאורעות "המילה אינה מופיעה במקטע הראשון" ו"המילה אינה מופיעה במקטע השני" בלתי-תלויים. לכן ההסתברות שהמילה לא תופיע בשני המקטעים שווה ל- $p^{2}$. מכאן נובע שההסתברות לכך שהמילה אינה מופיעה בשום מקום ברצף בן עשרים ושתיים האותיות, קטנה מ-$p^{2}$.

באופן דומה, עבור $n$ מקטעים של $11$ אותיות למקטע, ההסתברות שהמילה לא תופיע היא לכל היותר $p^{n}$. היות ש־$p<1$, כאשר $n$ גדל לאינסוף, ההסתברות שהמילה לא תופיע בכלל שואפת לאפס, וההסתברות שההפך הוא הנכון שואפת לאחת, כלומר, המילה תופיע כמעט בוודאות.

אותו טיעון אפשר להחיל על טקסט בכל אורך סופי - כמו כל כתביו של שייקספיר לדוגמה.

תוחלת הזמן להופעת קטע מסוים

אפשר להראות שעבור קטע נתון (כגון המילה "אנציקלופדיה"), לא רק שההסתברות להופעתה בסופו של דבר בסדרת התווים שהקוף מדפיס שווה ל-$1$, אלא אף תוחלת זמן ההמתנה למאורע זה היא סופית. תוחלת הזמן עד להופעת קטע בן $n$ אותיות המורכב מ-$M$ סוגי תווים, בהנחה שכל תו נבחר בהסתברות אחידה, אינה עולה על $nM^{n}$.

סדרות ארוכות במתמטיקה

על-פי המשפט שהוצג לעיל, טקסט סופי נתון וקבוע יופיע בהסתברות אחד בסדרה אקראית אינסופית. אפשר להוכיח יותר מזה: בהינתן סדרה אקראית אינסופית (שבה האותיות מוגרלות מאלפבית סופי, באופן אחיד ובלתי תלוי), כל טקסט סופי יופיע (שוב, בהסתברות $1$). יתרה מזו, כל טקסט מקרי מופיע בשכיחות השווה להסתברות שלו להופיע בכל מקום בסדרה. להרחבה בנושא זה, ראו מספר נורמלי.

התוצאה האינטואיטיבית שלפיה אפשר לצפות לתופעות מוזרות בסדרה, בתנאי שהיא ארוכה מספיק, מופיעה פעמים רבות בקומבינטוריקה. הלמה של בורל-קנטלי היא דוגמה לא פשוטה לכך, שהיא בעלת השלכות חשובות בתורת החוגים.

בתרבות פופולרית

קוף מקוק - חזרות על האות האנגלית "S"

בשנת 2003 נערך "ניסוי" בגן החיות של פייתון, שבמהלכו ניתנו שש מכונות כתיבה לקופי מקוק. במשך חודש הפיקו הקופים חמישה עמודים בלבד, ואלה הורכבו בעיקר מחזרות על האות האנגלית "S". יתרה מכך, הקופים השחיתו את המקלדות במגוון אופנים. משך זמן הניסוי זניח לחלוטין ביחס לפרק הזמן הדרוש בתוחלת כדי להפיק יצירה בעלת משמעות, וכן תנאי הניסוי הושפעו ממשתנים מפריעים נוספים, וכך למשל הקופים הרסו חלק ממכונות הכתיבה במקום להקיש בהן אותיות.

דרך מלאכותית לעריכת הניסוי מספק האתר "סימולטור הקופים של שייקספיר", המכיל תוכנית Java, המדמה הקלדות אקראיות של קופים רבים. עד היום נתקבלו בסימולציה זו תוצאות המכילות עשרים וארבעה תווים רצופים מתוך מחזהו של שייקספיר, הנרי הרביעי, חלק שני.

הניסוי מוזכר ביצירות תרבות שונות, בספרות ובטלוויזיה והקולנוע:

• בספרו של דאגלס אדמס, "מדריך הטרמפיסט לגלקסיה", לאחר שמופעל מנוע אי-ההסתברות, ארתור דנט אומר שישנם אינסוף קופים מחוץ לספינה שרוצים לדבר על התסריט שהם כתבו להמלט.
• בספרו של ריצ'רד דוקינס, "השען העיוור", משמש המשפט כהנגדה לדרך בה פועלת ברירה הצטברותית.
• בספרו של מיכאל אנדה "הסיפור שאינו נגמר" מוזכרת עיר דמיונית המכונה "עיר הקיסרים שעבר זמנם" שתושביה עוסקים יומם וליל בכתיבה רנדומלית של צירופי אותיות שונים, וחזקה עליהם שיכתבו כל חיבור שייכתב אי פעם.
• הסיפור הקצר "הספרייה בבבל", באוסף הסיפורים "בדיונות" מאת חורחה לואיס בורחס, רומז גם הוא לניסוי, ומתאר היכל דמיוני המכיל אינסוף ספרים שבהם מופיעים כל צירופי האותיות האפשריים.
• אאוגוסטו מונטרוסו מתאר את ההתנשאות האירופית והאמריקנית כלפי היוצרים של אמריקה הלטינית בדימוי של קוף מקליד:

  ”ליצר החקרנות אין גבול. בארצות הברית ובאירופה התגלה לאחרונה קיומו של זן קופים לטינו-אמריקנים המסוגלים להתבטא בכתב, מן הסתם ממשיכיו של הקוף החרוץ, אשר משהצליח להדפיס במכונת כתיבה, סופו שכתב מחדש, לגמרי במקרה, את הסונטות של שייקספיר. מובן מאליו שהתגלית מעוררת השתוממות גדולה.” (הסימפוניה הגמורה, מתוך: "תנועה מתמדת", תרגום טל ניצן קרן, הוצאת הקיבוץ המאוחד)

• בסיפור המדע הבדיוני "אצבעות הקוף" מאת אייזק אסימוב מתואר קוף שמוחו הפך במסגרת ניסוי מדעי למחשב, והוא מקליד ו"מתקן" את מילותיו של שייקספיר.
• בסרט "על החוף" (1959 ,On the Beach), רב חובל מזכיר "הסיפור הישן אודות מספר אינסופי של קופים ומספר אינסופי של מכונות כתיבה".
• בסדרת הטלוויזיה "ורוניקה מארס " (עונה 2, פרק 3), ורוניקה אומרת "איפשהו, מיליון השימפנזים האלו, עם מיליון מכונות כתיבה שלהם מוכרחים לכתוב את 'המלך ליר'".
• בסדרת הטלוויזיה "משפחת סימפסון ", בפרק "יציאה אחרונה לספרינגפילד", מר ברנז מציג להומר חדר שבו אלף קופים מקלידים על אלף מכונות כתיבה. מר ברנז קורא את הטקסט שכתב אחד הקופים - "זה היה הטוב שבזמנים, זה היה הרע שבזמנים" (שורת הפתיחה של הספר בין שתי ערים מאת צ'ארלס דיקנס) ומתעצבן כאשר הוא מוצא בו שגיאת כתיב.
• בסדרת הטלוויזיה איש משפחה (עונה 2, פרק 7), ישנה סצנה שבה קופים מנסים לכתוב את השורה מהמחזה רומיאו ויוליה של שייקספיר, "A rose by any other name would smell as sweet".

ראו גם

• הלמה של בורל-קנטלי
• מיון אקראי

קישורים חיצוניים

• Terry R. McConnell, The Expected Time to Find a String in a Random Binary Sequence, על התוחלת של זמן ההמתנה לסדרה נתונה.
• פזיה מילר, תיאורמת הקוף האינסופי, במדור "מאגר המדע" באתר של מכון דוידסון לחינוך מדעי, 9 ביולי 2012
• משפט הקוף המקליד - מה הקשר בין קופים לגאונות?, באתר אנציקלופדיה אאוריקה