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