יום הולדת 100 לאלן טיורינג!

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

טיורינג היה מתמטיקאי בריטי שנולד בשנת 1912, הישר אל התקופה הסוערת של המתמטיקה של תחילת המאה ה-20. הייתה זו מתמטיקה שהשליכה מעליה את דרכי הביסוס הישנות שלה (גאומטריה, אנליזה) ובמובנים מסויימים “חיפשה את עצמה”. נותן הטון של אותו חיפוש עצמי היה המתמטיקאי דויד הילברט, שהציב בפני עמיתיו המתמטיקאים כמה יעדים כבירים, שאם היו מושגים היו משנים לחלוטין את האופן שבו אנחנו תופסים מתמטיקה. אחד מהם היה נסיון לבסס את המתמטיקה כולה על מערכת אקסיומות “סופית” באופיה, כזו שלא יהיו ספקות באשר לנכונותה, וזאת לאחר הפרדוקסים שהתגלו בתורת הקבוצות (ונבעו מכך שהיא אפשרה קבוצות אינסופיות שהן גדולות “מדי”). אתגר אחר של הילברט, אותו הציג בשנת 1928 וזכה לשם הקליל Entscheidungsproblem, היה הבעיה הבאה: למצוא אלגוריתם אשר בהינתן טענה כלשהי שמנוסחת בשפה הפורמלית של הלוגיקה (לוגיקה מסדר ראשון, שזה עתה השלמתי פוסט עליה), לקבוע האם היא נכונה או לא (כאשר “נכונה” כאן פירושו “נכונה בכל עולם שמקיים את האקסיומות של הטענה”). קשה להפריז בעוצמה של אלגוריתם כזה, אם היה מתגלה; אם היה אפשר להריץ אותו ולקבל תשובות בפועל, הוא היה פותר את כל השאלות הפתוחות במתמטיקה, בערך. קרוב לודאי שהילברט עצמו היה מודע לאפשרות שאלגוריתם כזה לא יתקיים, אבל איך אפשר להוכיח שאלגוריתם פשוט לא יכול להתקיים? עזבו את זה, מה זה בכלל אלגוריתם?

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

כמובן, אני חייב לסייג את עצמי. מכונות חישוב היו קיימות כבר מאות שנים לפני כן - כבר פסקל ולייבניץ המציאו כאלו. קרדיט משמעותי ביותר צריך להינתן גם למתמטיקאי צ’רלס בבאג’ ולשותפתו עדה לאבלייס שהקדימו את זמנם (בפרט, את הטכנולוגיה שלהם) במאה שנים לפחות והמציאו גם הם מחשב, אבל מעולם לא הצליחו לסיים את בנייתו. אבל טיורינג היה במקום הנכון בזמן הנכון, ועם רעיונות מקוריים משל עצמו. למרות שתחום המחקר שלו בתואר השני היה לוגיקה הוא היה מחובר לקרקע ואהב מכונות. לכן, בעוד שמעבר לים המתמטיקאי אלונזו צ’רץ’ תקף את בעיית ה-Entscheidungsproblem על ידי פורמליזם לחישובים שנקרא “תחשיב למבדא” והיה מאוד מתמטי-אבסטקרטי באופיו, טיורינג חשב על מכונה. הוא הגדיר באופן פורמלי ומדויק מכונה דמיונית שיודעת לבצע חישובים בצורה הכי ארצית שאפשר - מתרוצצת אנה ואנה על גבי סרט, בכל רגע נתון רואה רק את מה שכתוב במקום שבו היא נמצאת, ועל פי זה מבצעת שינויים אלו ואחרים. זה נראה מודל פרימיטיבי, אפילו מגוחך. בכלל לא ברור שיצור כזה יוכל לעשות משהו מעניין. טיורינג ידע שהוא יוכל, ובשנת 1936, כשהוא עדיין לא בדוקטורט אפילו, פרסם מאמר בשם ”On computable numbers, with an application to the Entscheidungsproblem”. אם תשאלו אותי, זהו כנראה המאמר החשוב ביותר בתולדות מדעי המחשב.

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

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

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

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

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

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

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

טיורינג היה הומוסקסואל, וכנראה שלא עשה מאמצים מיוחדים להסתיר זאת. בשנת 1952 נפרץ ביתו, כנראה בסיוע אדם שטיורינג קיים אותו יחסים. כאשר טיורינג קרא למשטרה לחקור את הפריצה, והתגלה להם על מערכת היחסים ההומוסקסואלית של טיורינג (מפיו שלו עצמו), הוא הפך פתאום לפושע, שכן הומוסקסואליות הייתה עבירה פלילית באנגליה של אותם ימים (“gross indecency”). לא עזר לטיורינג מעמדו המכובד בחברה, ובוודאי שלא עזרה לו העובדה שהיה גיבור מלחמה (שכן אז כל מעשיו במהלך המלחמה היו סוד מוחלט), והוא נאלץ לבחור בין מאסר ובין זריקות הורמונליות לדיכוא היצר המיני. הוא בחר בזריקות.

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

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

יום הולדת שמח, טיורינג!