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

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

משפט הקוף המקליד הוא טענה מתמטית, לפיה אם נבחר טקסט באורך סופי, אז הוא יופיע ברצף אינסופי של תווים אקראיים המוגרלים מהתפלגות אחידה (אך לאו דווקא מהתפלגות זו) בהסתברות $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, המדמה הקלדות אקראיות של קופים רבים. עד היום נתקבלו בסימולציה זו תוצאות המכילות עשרים וארבעה תווים רצופים מתוך מחזהו של שייקספיר, הנרי הרביעי, חלק שני.

משפט הסמור, אבולוציה וסדר

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

לא סביר להגיע לסדר באמצעות מקריות בלבד

דוקינס מתחיל בתאור ניסוי דמיוני דומה, שבו מגיעים לכך שהסיכוי לקבל סדר, ואפילו פשוט, עקב תהליך מקרי לגמרי, לוקח זמן רב מאד. דוקינס שואל מה הסיכוי לקבל את המשפט, "נדמה לי שהוא כמו סמוּר" (METHINKS IT IS LIKE A WEASEL)- מתוך המחזה המלט, על ידי הגרלה מקרית מתוך $26$ אותיות באנגלית ומקש רווח. לדוגמה על ידי קוף שמקליד בצורה מקרית על מקלדת מחשב.

במשפט האנגלי יש $28$ תווים (כולל רווחים) הסיכוי לנחש נכון את האות הראשונה הוא $1/27$. הסיכוי לנחש שתי אותיות נכונות באופן מקרי הוא $1/{27}^{2}$, וכך הלאה – כך שניחוש כל המשפט באנגלית הוא ${27}^{28}$ שהם בקירוב ${10}^{40}$. גם אם במקום קוף נכניס תוכנת מחשב שתבחר במהירות אותיות באופן מקרי, הזמן הממוצע הנדרש להגיע לתוצאה נכונה צפוי להיות מאות מיליארדי שנים – ארוך יותר מגיל היקום. הנכונות של "משפט הקוף המקליד" נבעה מכך שמניחים באופן משתמע את קיומו של זמן ארוך ככל שנרצה לסיום התהליך – דבר זה נכון במקרה של משפט מתמטי תאורטי אבל לא מתקיים בהכרח בשאלות מעשית.

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

הוספת בחירה לא מקרית גורמת להופעה מהירה של סדר

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

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

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

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

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

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

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

• בסרט על החוף (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
• משפט הקוף המקליד - מה הקשר בין קופים לגאונות?, באתר אנציקלופדיה אאוריקה