אז מה זה בעצם אי דטרמיניזם? קשה להחליט

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

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

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

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

באופן פורמלי, הדרישה הזו נוצרת מכך ש”פונקצית המעברים” של המכונה היא אכן פונקציה - כלומר, לכל מצב פנימי של המכונה וקלט שהיא רואה כרגע הותאמה דרך פעולה אחת ויחידה. אם נרשה התאמה של כמה דרכי פעולה, זו כבר איננה פונקציה במובן המקובל של המילה (כשם שפונקציה f שמוגדרת כ”f(1)=x כש-x הוא או 1 או 2” אינה פונקציה), אך אם מתעקשים על פורמליסטיקה אפשר להגיד שזו כן פונקציה, אך בין קבוצות שונות - מקבוצת הזוגות של קלט/מצב פנימי לקבוצת כל תת הקבוצות של המעברים האפשריים. מבלבל? בטח. אז בשביל מה להתעסק בפורמליסטיקה?

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

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

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

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

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

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

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

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

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

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