מכונת טיורינג הסתברותית

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

יש כמה דרכים להגדיר מכונת טיורינג הסתברותית. רוב ההגדרות שקולות או אינן מגבירות משמעותית את כוח החישוב ביחס לשאר ההגדרות. כולן מבוססות על מודל מכונת הטיורינג הרגיל, והוא נוסף לו מרכיב הסתברותי.

בעוד שבמכונת טיורינג סטנדרטית או אי־דטרמיניסטית קלט מקובל או נדחה כהחלטה ברורה, במכונה הסתברותית מקבלים קלט בהסתברות מסוימת ודוחים אותו בהסתברות אחרת. לכן היא עלולה לטעות בהסתברות כלשהי, כלומר לומר שהקלט נכון כאשר אינו כזה, או להפך. על בסיס מגבלות ההסתברות לשגיאה וזמן הריצה מגדירים מחלקות סיבוכיות שונות. יש גם גרסאות שדורשות זיכרון לוגריתמי, עם שמות כמו PL, BPL, RL, Co-RL ו‑ZPL.

קטגוריה:סיבוכיות חישובית
קטגוריה:אלן טיורינג

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

יש כמה דרכים לתאר את המכונה הזאת. כולן דומות למודל המכונה הרגיל, אבל מוסיפים אלמנט של מזל.

במחשב רגיל קלט מקובל או נדחה ברור. במכונה ההסתברותית הדברים אינם ברורים לגמרי. אפשר לקבל קלט עם סיכוי מסוים ולדחות אותו עם סיכוי אחר. לכן היא עלולה לטעות לפעמים. לפי כמה סיכוי לטעות וכמה זמן לוקח, מגדירים קבוצות בעיות שונות. יש גם גרסאות לחישוב שדורשות מעט זיכרון, בשמות כמו PL ו‑BPL ו‑RL.

קטגוריה:סיבוכיות חישובית
קטגוריה:אלן טיורינג