האם טיורינג טעה?

המחשב מבצע רק את הוראותינו
תמונת אלן בשחור לבן
אלן טיורינג commons.wikimedia.org

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

את טענתו ניתן להבין בשתי דרכים.

  1. בהינתן קוד של כלי ספרתי, אפשר לעקוב אחר ביצועו צעד-צעד, ולדעת מה הוא יעשה בכל צעד. מובן שטענה זו נכונה, ואף שהיא נראית טריוויאלית, היא חשובה לגזירת המסקנה שניתן לבנות כלי ספרתי אחד שיוכל לבצע את המעקב הזה. הכלי העוקב יפעל כמו הכלי ספרתי הנתון לו לפי הקוד שלו. היות שניתן לנסח את המעקב כשיטה אחידה, ניתן לבנות עבורה כלי שהכינוי "אוניברסלי" מתאים לו. טיורינג עשה זאת במפורש במאמרו הראשון משנת 1936 (ראו https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf). אינני בטוח שבהצהרתו "לנבא מה היא תעשה" טיורינג התכוון שאפשר לעקוב אחרי הכלי הנתון בעזרת ביצוע כלליו – זה לא ניבוי. הוא מזכיר את הגדרת המחשב ככלי שניתן לתכנת אותו לביצוע תיאור של כל כלי ספרתי – כך הוא מוגדר במאמר בפסקה העוקבת את ההצהרה – אבל מבלי לקשר הגדרה זו עם אפשרות הניבוי על סמך הטבלאות. בהצהרתו השתמש טיורינג בביטוי "אפשר לנבא" ולא "אפשר לעקוב", ולכן קשה לקבל שהתכוון למעקב. לעומת זאת –
  2. האם טיורינג התכוון שאפשר לנבא תשובה לכל שאלה ביחס לכלי הנתון? עוד בשנות ה-30 הוא ידע שהתשובה לשאלה זו היא שלילית. אז מה אפשר לנבא על הכלי מידיעת כל כללי הגדרתו?

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

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

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

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

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

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

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

(a) נבדוק אם המספר זוגי

– אם הוא אכן זוגי נחלק אותו לשתיים;

– אם איננו זוגי, אז נכפול אותו ב-3 ונוסיף למכפלה 1;

(b) כעת נבחן את התוצאה שבידינו. אם היא איננה 1, נחזור ונבצע את הוראה (a), אחרת נמשיך הלאה ונעבור להוראה הבאה.

(c) הגענו למספר 1, בזאת אנו מסיימים את התהליך.

לדוגמה, אם נבחר להתחיל במספר 17: המספר איננו זוגי, ולכן נעבור למספר 52 (17*3 + 1); המספר 52 הוא זוגי, ולכן נעבור למספר 26, וממנו למספר 13; 13 איננו זוגי, ולכן נעבור למספר 40 (13*3 + 1); וכך נמשיך, מ-40 ל-20, מ-20 ל-10, מ-10 ל-5; 5 איננו זוגי, ולכן נעבור למספר 16 (5*3 + 1); וכך נמשיך, מ-16 ל-8, מ-8 ל-4, מ-4 ל-2 ומ-2 ל-1. כאן התהליך מסתיים. הוא הסתיים אחרי 12 צעדים.

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

איש איננו יודע לנבא אם זה מה שיקרה בתהליך – אם הוא יסתיים בכל בחירה של מספר שלם וחיובי כלשהו. איש לא הצליח אפילו לגלות חוקיות כלשהי בתהליך עצמו. למשל, איש לא הצליח למצוא חוקיות המקשרת את מספר הצעדים הנדרש לסיום ממספר נבחר אחד למספר הבא אחריו, לעוקב שלו. לכן התהליך נקרא "אבני ברד". תוכלו למצוא ברשת דיונים רבים בתהליך הזה אם תחפשו טקסטים המכילים את הביטויים "3x+1" או "Hailstone" או "השערת קולץ'".

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

(a) נבדוק אם הסדרה ניתנת לחצייה לשני חלקים השווים באורכם מבחינת מספר האותיות שבהם;

– אם כן, נחתוך את הסדרה לשני חלקים שווים באורכם וניקח אחד מהם;

– אם לא, נצמיד לסדרה עוד שני עותקים שלה, נוסיף אות אחת (נניח 'q') וניקח את הסדרה החדשה;

(b) אם הסדרה שבידינו איננה מכילה בדיוק אות אחת, נחזור ונבצע את הוראה (a). אחרת, נעבור להוראה הבאה.

(c) הגענו לסדרה בת אות אחת ונסיים את התהליך.

דוגמה לביצוע התהליך:

abcdeabcde, abcde, abcdeabcdeabcseq, abcdeabc, abcd, ab, a

חשוב להבין שתהליכים כאלה יכולים להתגלגל לאחת משלוש האפשרויות שלהלן, ורק לאחת מהן:

  1. התהליך ייכנס ללולאה החוזרת על עצמה מבלי שיגיע לתנאי הסיום שלו;
  2. התהליך, בכל כמה שלבים, יגיע למספרים גדולים יותר ויותר (או לסדרות ארוכות יותר ויותר) ולכן לעולם לא יגיע לידי סיום;
  3. התהליך יגיע תמיד למספר 1 (או לסדרה של אות בודדת אחת) ויסתיים.

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

כדאי לנסות כמה מספרים כדי לקבל תחושה כללית במה הדברים אמורים. לדוגמה, אם תתחילו במספר 41 תגיעו למספר 9232, ותזדקקו ל-110 צעדים בסך הכול כדי להגיע ל-1. ואילו אם תתחילו במספר 42 לא תגיעו אפילו ל-100, ואחרי 9 צעדים התהליך יסתיים. ואם תתחילו במספר 40 התהליך יסתיים אף הוא ב-9 צעדים. וכדי שלא תקפצו להשערות נמהרות, התחילו במספר הראשוני 53, ותראו שאחרי 12 צעדים התהליך יסתיים.

מתעורר כאן עניין עקרוני שחשיבותו עולה על כל דוגמה מספרית: האם ידיעת הכללים לביצוע של תהליך כלשהו מספיקה כדי להבטיח את ידיעת כל הפרטים על התהליך עצמו בכל אפשרויות ביצועו? התשובה המפתיעה היא: לא ולא! הניסוח החשבוני של הדוגמה מראה שאף על פי ששפת החשבון היא חד-משמעית, המעבר מידיעת כללי ביצוע תהליך לידיעת התהליך המבוצע לפי הכללים איננו מובן מאליו. גם אם יתברר סוף סוף שאכן התהליך הוא תמיד בר-סיום, 80 שנות חיפושים ללא תוצאות מוכיחות שיש קושי עקרוני בהסקת מסקנות על תכונה של תהליך מידיעה של הכללים לביצועו. על אחת כמה וכמה אם מדובר בתהליכים שאינם חשבוניים ובהגדרות שאינן חד-משמעיות.

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

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

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

שיתוף ב facebook
Facebook
שיתוף ב twitter
Twitter
שיתוף ב linkedin
LinkedIn
שיתוף ב whatsapp
WhatsApp
שיתוף ב email
Email

18 תגובות

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

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

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

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

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

        1. יש שני מכשולים בדרך להארה שאתה מבקש: (1) חלק ממה שעשה טיורינג ועוזרותיו עדיין חסוי; (2) אי אפשר בעמוד וחצי לתאר ותהסביר את מה שידוע על מה שהם עשו; ויש עוד מכשולים ערטילאים יותר: (3) סוד ההצלחה של טיורינג ועוזרותיו טמון בדרך שבה הם השתמשו באלגוריתמים ובאלגוריתמים עצמם – זה חסוי. (4) כדאי להבין מה טירינג הבין לפני המלחמה לגבי אלגוריתמים ומנגנוני חישוב…
          אז אינני יכול להאיר את עיניך בתנאים הנוכחיים…
          מועדים לשמחה

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

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

          1. תודה נעמה,

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

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

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

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

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

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

      מועדים לשמחה,

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

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

    אני מביא את ההשערה של קולאטץ' כדוגמה פשוטה לכאורה להמחשת תכונות האלגוריתמים שהוכחו על-ידי טיורינג ועמיתיו עוד בשנות ה-30. אבל אני שמח אם זה מעורר את הקוראים להעמיק אפילו בדוגמה.

    הנה כמה מקורות עם נתונים, תוכנות ומקורות שיספקו לך נתונים עשירים יותר מויקיפדיה:

    https ://oeis.org/A006577
    http ://members.chello.nl/k.ijntema/
    http ://bit.ly/2gcbUZY

    בהצלחה,

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

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

  7. אני מנסה להבין איך אתה קופץ מטיענים מתמטיים נכונים למסקנות חברתיות (נכונות לדעתי).

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

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

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

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

כתיבת תגובה

האימייל לא יוצג באתר.

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

עשוי לעניין אותך

מייצג כסאות

רות הישראלית

תובנות אקטואליות מקריאה ישראלית במגילת רות

מהי שחיתות?

הגיגים על מה שמתרחש אצלנו בצמרת ההנהגה

מדביר מועך חרק

הדברת נמלים

למה כדאי לעשות את זה בצורה מקצועית?