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