ראסל, גדל, טיורינג - כיצד ההכרה בגבולות הידיעה מהווה את הבסיס לעולם המידע

פרדוקס הסַפָּר

על אי יווני מבודד וקטן חי סַפָּר אחד ויחיד. על דלת מספרתו תלוי שלט: "אני מספר את כל הגברים באי שאינם מספרים את עצמם, ורק אותם".

השאלה פשוטה: מי מספר את הסַפָּר?

• אם הסַפָּר מספר את עצמו, הוא מפר את הכלל שלו, שאומר שהוא מספר רק את אלה שאינם מספרים את עצמם. זו סתירה.
• אך אם הוא אינו מספר את עצמו, הרי שהוא שייך לקבוצת הגברים שאינם מספרים את עצמם, ולפי השלט, עליו לספר אותם. כלומר, עליו לספר את עצמו. שוב סתירה.

מסקנה: לא ייתכן ספר כזה כי עצם הגדרתו סותרת את עצמה.

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

חלום המכונה

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

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

השאיפה לשלמות: הילברט וארמון הלוגיקה

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

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

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

גֶדֵל ומשפטי אי-השלמות

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

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

בזה טמונה הגאוניות:

• אם המערכת יכולה להוכיח את הטענה, אז הטענה נכונה, ומה שהיא אומרת ("שלא ניתן להוכיחה") הוא אמת. אבל אם המערכת הוכיחה אותה, היא הוכיחה שקר. כלומר, המערכת אינה עקבית (מכילה סתירה).
• אם המערכת אינה יכולה להוכיח את הטענה, אז הטענה אכן נכונה (כי זה בדיוק מה שהיא טוענת!). כלומר, יש לנו טענה אמיתית שהמערכת לא יכולה להוכיח. משמע, המערכת אינה שלמה.

מכאן נובעים משפטי אי-השלמות של גֶדֵל, שקבעו שני דברים מהפכניים:

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

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

טיורינג: מגבולות ההוכחה לגבולות החישוב

צעיר בריטי מבריק בשם אלן טיורינג קרא את עבודתו של גֶדֵל והבין את משמעותה העמוקה. הוא שאל את השאלה הבאה: אם יש אמיתות שלא ניתן להוכיח, האם ייתכן שיש בעיות שלא ניתן לחשב?

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

האם אפשר לכתוב תוכנה אחת, נקרא לה `HaltChecker`, שתוכל לבחון כל תוכנה אחרת ולקבוע בוודאות, ובלי לטעות אף פעם, אם היא תעצור בסופו של דבר, או שתרוץ לנצח בלולאה אינסופית?

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

נניח שקיימת תוכנת `HaltChecker` שלא טועה אף פעם.

עכשיו, נבנה תוכנה חדשה ו"מתחכמת", נקרא לה `Trickster`. היא מקבלת כקלט תוכנה אחרת (נקרא לה P), ועושה את הדבר הבא: היא מריצה את `HaltChecker` על P. אם `HaltChecker` קובע ש-Pתעצור, אז `Trickster` נכנסת בכוונה ללולאה אינסופית. אם `HaltChecker` קובע ש-Pתרוץ לנצח, אז `Trickster` עוצרת מיד.

הנה המהלך המכריע: מה יקרה אם נזין את התוכנה `Trickster` כקלט לעצמה? (Trickster(Trickster))

• אם `HaltChecker` יקבע ש-`Trickster`תעצור, אז לפי ההגדרה שלה, היא תיכנס ללולאה אינסופית. סתירה.
• אם `HaltChecker` יקבע ש-`Trickster`תרוץ לנצח, אז לפי ההגדרה שלה, היא תעצור. שוב סתירה.

המסקנה בלתי נמנעת: ההנחה הראשונית שלנו, שניתן לבנות `HaltChecker` שלעולם אינה טועה, שגויה.

המשמעות אדירה: ישנן בעיות ששום מחשב, חזק ככל שיהיה, לעולם לא יוכל לפתור. לא כי הן "קשות מדי" או דורשות יותר מדי זמן, אלא כי הן בלתי ניתנות לחישוב באופן עקרוני. יש גבול מובנה ביקום לכוחו של החישוב.

מהמגבלה אל המכונה

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

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

גֶדֵל וטיורינג לא השאירו אותנו עם ייאוש, אלא עם תובנה עמוקה:

• לא כל מה שנכון ניתן להוכחה.
• לא כל מה שניתן לשאול ניתן לחישוב.

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

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

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

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

1. קבוצות שהן איברים של עצמן.
   לדוגמה: קבוצת כל המושגים המופשטים גם היא מושג מופשט, ולכן היא איבר של עצמה.

2. קבוצות שאינן איברים של עצמן.
   לדוגמה: קבוצת כל קנקני התה אינה קנקן תה, ולכן אינה מכילה את עצמה.

כעת נביט בקבוצה המיוחדת (R) שמגדיר ראסל:

R = קבוצת כל הקבוצות שאינן איברים של עצמן.

R = { x | x ∉ x }

השאלה היא: האם R עצמה איבר של עצמה?

אם R אינה איבר של עצמה הרי שהיא עונה על הקריטריון של עצמה, ולכן כן צריכה להיות איבר של עצמה. אבל אם היא כן איבר של עצמה אז היא מפרה את הקריטריון, כי היא כוללת את עצמה, ולכן אינה יכולה להיות איבר של עצמה.

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

לעיון נוסף

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

גֶדל, אֶשר, בּאך: גביש בן-אלמוות פוגה מטפורית על נפשות ומכונות ברוח לואיס קרול דאגלס ר' הופשטטר

[YouTube] Turing Machines Explained - Computerphile

סיפורי מדע - היקום שבפנים

המערה של אפלטון - שורשי הידיעה

התובנה שבקעה מפתח צר בקירות הכלא

נר בעלטה — אנשי חזון על סף העולם החדש

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים