בתשובה להאייל האלמוני, 10/01/07 21:22
אורקל 428639
גדי אלכסנדרוביץ' • בתשובה להאייל האלמוני יום ד', 10/1/2007, 21:35
זה אכן מודל לא סטנדרטי, ולטעמי הוא גם די מוזר ומלאכותי (אורקל שמתנהג באופן שונה בהתבסס על המכונה שקוראת לו?) אבל על פניו אני אכן לא רואה איתו בעיה עקרונית.
אורקל 428645
האייל האלמוני • בתשובה לגדי אלכסנדרוביץ' יום ד', 10/1/2007, 21:51
פתחתי את הדיון הזה בכך שניסיתי להגיד שאת ההוכחה לבעיית העצירה ניתן להכליל כך שתחול לא רק על מכונות טיורינג, אלא על מודלים כלליים יותר. בהמשך הדיון הוברר שעדיין צריך להניח הנחות מסוימות על המודל. ניסיתי להפריך את הטענה שקיום מכונה אוניברסלית היא תנאי הכרחי לצורך ההוכחה, ולכן הבאתי מודל מאד מוזר, שכל מטרתו להוכיח את זה.

כעת נשאלת השאלה האם ניתן לנסח תנאי יותר חלש מקיום מכונה אוניברסלית (למשל קיום מכונה ''כמעט אוניברסלית'', שזו מכונה שעוצרת אמ''מ המכונה שהיא קיבלה כקלט עוצרת על הקלט שלה), שיספיק על מנת שהוכחה תהיה תקפה לכל מודל שמקיים אותו. שאלה נוספת היא האם קיים מודל מעניין שאין בו מכונה אוניברסלית אבל יש בו מכונה כמעט אוניברסלית (או שמקיים את התנאי החלש יותר, אם מנסחים אותו באופן אחר).
אורקל 428646
גדי אלכסנדרוביץ' • בתשובה להאייל האלמוני יום ד', 10/1/2007, 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 מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות