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

למ הכוונה במילה "כוח" במשפט "רוב הדרכים שקולות או שאינן מוסיפות למכונה כוח משמעותי"? יאיר ח. 16:58, 8 אוגוסט 2006 (IDT)

כוח חישוב. כלומר, תוספת של שפות שניתן להכריע. אני לא בטוח אם לא כל המודלים שקולים (ואז לא מוסיפים כוח) פשוט כי זו נקודה טכנית די מעצבנת: אם עובדים רק בשיטת הפיצול לשניים, לא ברור איך אפשר ליצור בצורה מדוייקת הסתברות קבלה של 1/3 (למרות שאפשר להתקרב אליה כרצוננו) ולכן לא ברור עד כמה אפשר לסמלץ מכונה שיש בה הסתברות 1/3 עם מכונה שיש בה רק הסתברות 1/2. דברים כאלו. גדי אלכסנדרוביץ' 17:19, 8 אוגוסט 2006 (IDT)

חשיבות המודל

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

מה חשיבות אותן מחלקות סיבוכיות שהוגדרו? כנראה שגם כאן מדובר בדרגת הסיבוך של בעית הכרעה כאשר היא נפתרת (בהסתברות) ע"י אלגוריתם הסתברותי. מעולם לא למדתי בצורה מסודרת את התחום של אלגוריתמים הסתברותיים ולכן השערותי כאן הן בגדר ניחוש.אורי מוסנזון 23:44, 1 במאי 2007 (IDT)

תשובה טובה תבוא בגוף הערך, אז בינתיים תשובה לא טובה: מכונת טיורינג הסתברותית שקולה "כמעט" לכל אלגוריתם הסתברותי (יש איזה עניין טכני קטן - על פי ההגדרה הסטנדרטית, היא לא יכולה "לסמלץ" במדוייק הסתברות של 1/3 אלא רק הסתברות קרובה ל-1/3, אבל זה לא מעניין אף אחד), ומכאן גם חשיבותה. באשר למחלקות הסיבוכיות, כדאי באמת לומר במפורש ש-BPP היא מה שיש לנו בראש כשאנחנו חושבים על חישוב הסתברותי (סטייל מונטה קרלו) יעיל שגם מעניין אותנו - חישוב הסתברותי שבו אנחנו יכולים להקטין את השגיאה כרצוננו. RP ו-coRP הן פשוט חיזוקים של זה. ZPP היא גישה אחרת (סטייל לאס וגאס) - חישוב שלא טועה אף פעם, אבל יכול לקחת הרבה זמן. אלו שתי הגישות המרכזיות לאלגוריתמים הסתברותיים כפי שאני מכיר אותם. גדי אלכסנדרוביץ' 23:49, 1 במאי 2007 (IDT)

כמובן, כל זה כשמדובר על בעיות הכרעה בלבד, אבל הרעיונות תקפים גם לאלגוריתמים שמנסים להחזיר משהו. גדי אלכסנדרוביץ' 23:52, 1 במאי 2007 (IDT)

התשובה ה"לא טובה" די מספקת אותי. תודה.אורי מוסנזון 00:31, 2 במאי 2007 (IDT)