בתשובה לגדי אלכסנדרוביץ', 10/01/07 22:00
אורקל 428649
האייל האלמוני • בתשובה לגדי אלכסנדרוביץ' יום ד', 10/1/2007, 22:20
תוותר לי על המשקל והחריזה, נכון?

נניח שקיימת מכונה P שמקבלת כקלט מכונה M וקלט x ומחזירה האם M עוצרת על x (לכל M ולכל x). נבנה 3 מכונות כמעט אוניברסליות Q0,Q1,Q2, שכל אחת מהן מקבלת כקלט מכונה Q ומריצה את P על הקלט M=Q, x=Q. לאחר מכן, אם P מחזירה "M עוצרת על x" אז היא נתקעת, אחרת היא עוצרת. ההבדל ביניהן הוא שאם במהלך הסימולציה P פונה לאורקל שלה, כל אחת מהן מחזירה לה משהו אחר: Qi מחזירה לה i. מכיוון שלכל מכונה, התשובה של האורקל לאותה המכונה לא תלויה בקלט אלא רק במכונה, נובע שאחת המכונות האלו (לפחות) תסמלץ את P נאמנה (כי P תקבל בדיוק את הקלט שהאורקל היה מעביר לה) (*). נניח שזו Qi. כלומר, Qi היא מכונה שמקבלת כקלט מכונה Q ועוצרת אמ"מ Q לא עוצרת על הקלט Q. כעת נריץ את Qi על הקלט Qi, ואידך זיל גמור.

אגב, שים לב ש- Qi כלל לא קוראת לאורקל של עצמה, ולכן זה לא משנה מה הוא היה מחזיר.

-------------------

(*) בהתחלה חשבתי שבכל מקרה Q2 מסמלצת את P נאמנה (לפחות, מספיק נאמנה כך שההוכחה תהיה תקפה). זאת משום שאם P לא קונסיסטנטית אז ממילא היא מקבלת 2 מהאורקל, ואם היא כן קונסיסטנטית, אז לא משנה מה היא מקבלת מהאורקל. העניין הוא שה"לא משנה" הזה מדבר רק על השאלה האם P תעצור, לא על השאלה איזה קלט היא תחזיר. לכן צריך להגדיר 3 מכונות "כמעט אוניברסליות", ולא אחת. אגב, אם אנחנו יודעים מראש שהמכונה P עוצרת על כל קלט אז בכל זאת מספיק להגדיר מכונה אחת - זו שמחזירה ל- P (כשהיא קואת לאורקל) את התשובה "מכונה זו עוצרת תמיד".
אורקל 428650
גדי אלכסנדרוביץ' • בתשובה להאייל האלמוני יום ד', 10/1/2007, 22:33
עכשיו אני ממש מבולבל. מה זה "אורקל" בשבילך? בשבילי אורקל הוא קופסה שחורה שמכריעה שפות - שואלים אותה על מילה והיא עונה "כן" אם המילה בשפה ו"לא" אם לא. ממה שכתבת כאן אני מקבל את הרושם שאתה תופס אורקל (לפחות בהקשר הזה) בתור משהו שיכול לענות רק תשובה אחת, שוב ושוב. מה שזה בעצם אומר הוא שכל מכונת טיורינג מגיעה עם עוד "ביט מידע חבוי" (שני ביטים, בעצם, כי יכולים להיות שלושה ערכים) שאינו חלק מהקידוד שלה ורק לה יש גישה אליו.
אורקל 428652
האייל האלמוני • בתשובה לגדי אלכסנדרוביץ' יום ד', 10/1/2007, 22:44
האורקל הזה הוא קופסה שחורה ששואלים אותה על מילה והיא עונה אחד מ- 3 ערכים. העניין הוא שבמודל הזה המכונה שניגשת לאורקל חייבת לתת כקלט לאורקל את עצמה. זה שקול לכך שכל מכונה מגיעה עם עוד טריט מידע חבוי, שאינו חלק מהקידוד שלה (אם כי מוגדר חד ערכית ע"י הקידוד שלה) ושרק לה יש גישה אליו.
אורקל 428653
גדי אלכסנדרוביץ' • בתשובה להאייל האלמוני יום ד', 10/1/2007, 22:51
טוב ויפה, אבל בוא נניח שעל קלט כלשהו P פונה לאורקל שלה פעמיים כדי לבדוק שתי מילים שונות, והוא מחזיר לה פעם 0 ופעם 1. אף אחת משלוש המכונות שהצעת לא מסמלצת את ההתנהגות הזו.

(אם הכוונה שלך היא "המכונה יכולה לשאול את האורקל אך ורק על מילה בודדת - המילה שמייצגת אותה עצמה" - אז כאמור, אין צורך בדיבורים על אורקל ומספיק לדבר על ביט חבוי).
אורקל 428655
האייל האלמוני • בתשובה לגדי אלכסנדרוביץ' יום ד', 10/1/2007, 23:04
אתה צודק בהחלט. הגדרתי את האורקל כך בדיוק כדי שאכן אחת משלוש המכונות תסמלץ את ההתנהגות.

למעשה, כמו שאתה מציין - ביט חבוי הוא תיאור פחות עקום, והוא אפילו מרשה קיום של שתי מכונות זהות עם ביט חבוי שונה: מהסיבה שאתה אמרת לפני כמה תגובות לא קיימת מכונה אוניברסלית למודל כזה (היא לא תדע להבדיל בין המכונות הזהות עם ביט חבוי שונה), אבל קיימות שתי מכונות כמעט אוניברסליות, כך שכל מכונה מסומלצת ע"י אחת מהן לפחות - וזה כבר מספיק כדי שההוכחה תהיה תקפה.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות