מדוע מושג האלגוריתם לא הוגדר?

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

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

אתחיל במאמרו המכונן של טיורינג משנת 1936 עם תיקון שגיאות בשנת 1937, שבו הוא הגדיר את מה שנקרא כיום "מכונת טיורינג" כמודל פשוט ובר-מימוש של עבודת המחשבות בראשית המאה הקודמת. במאמר, שרק מעטים קראו אותו, הגדיר טיורינג בשנים 1936-37 שמספר ניתן לחישוב כאשר ורק כאשר הוא יכול להיות פלט של מכונת טיורינג. אז מדוע הוא לא הגדיר שאלגוריתם זאת מכונת טיורינג? מסתבר שהסיבה טבעית למדי. טיורינג היה מודע היטב

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

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

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

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

במאמר מאוחר יותר שלו, הכריז טיורינג במפורש שמבחינת חוקרי החישובים, המונחים "מנגנון" ו-"כתיבה" הם "כמעט בעלי משמעות זהה" (ראו מאמרו על מכונות ותבונה משנת 1950, בעמ' 457). ידוע לי כי מלבד טיורינג, רק שלושה (!) חוקרים במדעי המחשב, אדזחר דייקסטרה (בשנת 1962), ארתור ברקס (בשנת 1963) ומשה ורדי (בשנת 2012) התייחסו בכובד ראש אל זהות זו כאל זהות חשובה. למשל, כדי להבין שמדובר במצב עניינים מעשי ולאו דווקא רק פילוסופי, דייקסטרה במאמרו "כמה הגיגים על תכנות מתקדם" בשנת 1962 (ניתן לאיתור ברשת באמצעות הקוד EWD32) כתב:

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

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

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

4 תגובות

  1. אתה היחידי שמצליח בעיני להפוך את העולם הממוחש לסוגיות פילוסופיות. מבט מזווית מעניינת

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

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

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

כתיבת תגובה

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

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

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