אלגוריתם סופי דטרמיניסטי (או: מה זה בכלל?)

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

1. הבט במשוואה.
2. אם היא פתירה, אמור "כן".
3. אחרת, אמור "לא".

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

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

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

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

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

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

אם כן, אני מקווה ששכנעתי אתכם שאלגוריתם צריך להיות:

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

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

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

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

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

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

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

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

"The claim that interactive systems have richer behavior than algorithms is surprisingly easy to prove: Turing machines cannot model interaction machines because: interaction is not expressible by a finite initial input string."

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

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

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