מכונת טיורינג הסתברותית – הבדלי גרסאות

ב[[מדעי המחשב]], '''מכונת טיורינג הסתברותית''' היא [[מודל מתמטי]] של [[מחשב]] המהווה הרחבה של המודל הסטנדרטי של [[מכונת טיורינג]] על ידי הוספת אלמנט [[הסתברות|הסתברותי]] לחישוב שהמכונה מבצעת. תוספת זו גורמת לכך שמכונת הטיורינג תפעל על אותו הקלט בדרכים שונות. בניגוד ל[[מכונת טיורינג לא דטרמיניסטית]] שבה קלט מתקבל אם קיים מסלול חישוב כלשהו שבו הוא מתקבל, במכונת טיורינג הסתברותית, לכל קלט קיימת הסתברות לקבלתו או לדחייתו.