מה דחף לוגיקנים לחקור מהו חישוב יעיל?

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

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

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

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

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

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

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

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

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

Facebook
Twitter
LinkedIn
WhatsApp
Email

7 תגובות

  1. רק לא הצלחתי להבין למה הגדרת היא חשובה. למה היא בפועל תועיל?

    1. הגדרה או הגדרת המונח "אלגוריתם".. בכל מקרה הגדרות חשובות מאד. התחומים שבהם אין חשיבות להגדרות הם עשירים בוויכוחים ללא קץ. בלי הגדרות תיפגע מאד המתמטיקה. ללא מתמטיקה ברורה אין מדעים מדויקים, וללא מדעים מדויקים אין טכנולוגיה. ללא הגדרות אין מדעים בינתחומיים וידע מתחום אחד אינו יכול לעזור לתחום אחר (ראה במאמר קודם שדן בהשלכות בינתחומיות בקישור: https://jokopost.com/thoughts/23426/). ייתכן ואצטרך לפרט נימוקים לטענותי אלה במאמר, כדי להוכיח שההגדרות אכן מספקות לנו "רצועות חיזוק" בקירות המבנה המפואר של הידע האנושי.

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

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

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

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

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *

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

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

תמונה של יהודה

חופשה נעימה

היעדים של הישראלים היוצאים לחו"ל בפסח ובקיץ

תמונה של עמירם

השלכות

על תכונותיו של אדם בוגר

דילוג לתוכן