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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

תוכן עניינים

[עריכה] הוכחת הטענה

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

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

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

P = 1-0.0000000000000000002048 = 99.99999999999999997952\, \%.

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

באופן דומה, עבור n מקטעים של 11 אותיות למקטע, ההסתברות שהמלה לא תופיע היא לכל היותר Pn. היות ש־1 > P, כאשר n גדל לאינסוף, ההסתברות שהמלה לא תופיע בכלל שואפת לאפס, וההסתברות שההיפך הוא הנכון שואפת לאחת, כלומר, המלה תופיע כמעט בוודאות.


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

[עריכה] תוחלת הזמן עד שיופיע קטע מסוים

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

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

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

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

[עריכה] ניסויים מעשיים

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

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


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

[עריכה] איזכורים בתרבות

[עריכה] קישורים חיצוניים