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