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

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

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

הוכחת הטענה

הטענה נובעת מן הלמה של בורל-קנטלי.

ניתן גם להראות את קיום הטענה באופן ישיר: ההסתברות שיתרחשו שני מאורעות בלתי־תלויים שווה למכפלת ההסתברויות שלהם; לדוגמה, אם ההסתברות שפרוסת לחם תיפול על הצד המרוח בחמאה היא $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$. היות ש־1 > $P$, כאשר 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".

ראו גם

• הלמה של בורל-קנטלי
• The Monkey's Finger (באנגלית)

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

• Terry R. McConnell, The Expected Time to Find a String in a Random Binary Sequence, על התוחלת של זמן ההמתנה לסדרה נתונה.