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

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

דוגמה

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

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

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

משאבי זמן

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

משאבי זיכרון

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

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

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