מכונת טיורינג לא-דטרמיניסטית

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

מכונות טיורינג אי-דטרמיניסטיות הובילו להגדרת מחלקות סיבוכיות מתאימות, ולשאלות רבות על הקשר בין מחלקות אלו למחלקות הסיבוכיות הדטרמיניסטיות. בעוד ידוע כי יכולת החישוב של שני המודלים שקולה (כל מה שמודל אחד יכול לחשב, גם המודל השני יכול לחשב), לא ידוע מה הקשר בין סיבוכיות המשאבים הנדרשים בכל אחד מהמודלים. במילים אחרות, לא ברור האם למכונות אי-דטרמיניסטיות יש "יעילות חישוב" יותר טובה מאשר מכונות דטרמיניסטיות (מבחינת משאבי הזמן הנדרשים^[1]). שאלה זו, האם מכונות אי-דטרמיניסטיות מחשבות בעיות "יותר מהר" היא שאלה פתוחה חשובה במדעי המחשב ומכונה בעיית P=NP.

הגדרה פורמלית

מכונת טיורינג לא-דטרמיניסטית מורכבת מהרכיבים הבאים:

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

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

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

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

דוגמה

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

הגדרות שקולות לבחירת מצב באופן לא-דטרמיניסטי

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

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

שקילות למודל הדטרמיניסטי

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

כאמור שקילות זו מוכחת מבחינת החישוביות, אך נושא הסיבוכיות פחות ברור.

משאבי זמן

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

משאבי זיכרון

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

מודל הסתברותי

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

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

ראו גם

• מחלקת הסיבוכיות האי-דטרמיניסטית NP
• סיבוכיות זמן וסיבוכיות מקום
• מחלקת הסיבוכיות ההסתברותית BPP

לקריאה נוספת

• דוד הראל, אלגוריתמיקה - יסודות מדעי המחשב, האוניברסיטה הפתוחה, 1991

קישורים חיצוניים

שמואל וינוגרד, ‏מכונת טיורינג, מחשבות 35, יולי 1972, עמ' 13–17

הערות שוליים

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