בתשובה לגדי אלכסנדרוביץ', 10/01/07 9:16
 |
|
 |
||
|
||||
 |
למיטב הבנתי, בעולם שבו קיימים אורקלים, אם מכונה אוניברסלית עושה אמולציה למכונה אחרת, וזו קוראת לאורקל במהלך האמולציה - על המכונה האוניברסלית להחזיר לה את התשובה שהאורקל היה מחזיר לה. לצורך כך מותר לה כמובן להשתמש באורקל שלה עצמה, אבל לא באורקל של המכונה המורצת, שאליו אין לה גישה. אני יכול לחשוב על שתי הגדרות אלטרנטיביות של אורקל או של מכונה אוניברסלית שיפגמו בטיעון הנ"ל: הראשונה - שאורקל לא מוגדר עבור מכונה מסוימת, אלא קיים בעולם אורקל שכל מכונה יכולה לפנות אליו עם קלט, והוא יחזיר לה את הפלט. השניה - שהאורקל הוא כן ספציפי לכל מכונה, אבל ממכונה אוניברסלית לא נדרש לסמלץ את האורקל של המכונה המורצת, אלא היא מקבלת גישה לאורקל של המכונה המורצת. אני התיחסתי למקרה שבו לכל מכונה יש אורקל אחר (או, לחליפין, שהאורקל מקבל כקלט את המכונה שקוראת לו, ואין למכונה אפשרות להחליף לו את הקלט). ייתכן שיש לקרוא ליצור כזה בשם אחר (שנורקל?), אבל בהנתן ההגדרה הזאת, אכן בעולם שהגדרתי אין מכונה אוניברסלית, ואולם ההוכחה של בעיית העצירה תקפה. בכל מקרה כמובן שאני לא דורש מאורקל שניתן יהיה לסמלץ אותו, אחרת אין בו צורך. |
 |
 |
 |
|
|
|
||
|
||||
|
אני חשבתי דווקא על כך שיש אורקל אחד קבוע "ברקע", וגם למכונה האוניברסלית יש גישה אליו. אני מסכים שאם האורקל הוא שונה לכל מכונה אז כנראה שאין מכונה אוניברסלית - אבל לדעתי אנחנו נתקעים כבר ברמת ההגדרה. נניח שאני מכונה אוניברסלית. אני מקבל כקלט קידוד של מכונת טיורינג וקלט עבורה. עכשיו, איך אני מבדיל בין מכונת טיורינג A שיש לה אורקל K, ובין *אותה* מכונת טיורינג A רק עם אורקל שונה, T? (כלומר, ההבדל היחיד הוא בתשובות שהאורקל יחזיר, לא בהתנהגות של A כתלות בתשובות הללו). אני חייב לקודד את ההבדל בין K ו-T כחלק מהקלט, אבל כאן אני נתקע; יש אורקל לכל שפה, אבל מספר השפות הוא לא בן מניה, ואם אני מסוגל לקודד משהו כקלט למכונת טיורינג, הוא מן הסתם שייך לקבוצה בת מניה (קבוצת כל הקידודים). |
|
|
|
|
|
|
||
|
||||
|
בדוגמה שאני נתתי, יש אורקל שונה לכל מכונה, אבל לכל מכונה יש אורקל יחיד. לא קיימות שתי מכונות, שהן אותה מכונה עם אורקלים שונים. לצורך העניין, אפשר להגדיר שקיים אורקל קבוע ברקע, אבל הוא מקבל כקלט את המכונה שניגשת אליו, ולמכונה אין אפשרות לשנות את הקלט הזה. ייתכן שזה לא מודל סנטדרטי (ואתה מוזמן לקרוא לאורקל הזה בשם אחר), אבל הוא מוגדר היטב, והבעיה שאתה מציין לא קיימת בו. | |
|
|
|
|
|
||
|
||||
|
זה אכן מודל לא סטנדרטי, ולטעמי הוא גם די מוזר ומלאכותי (אורקל שמתנהג באופן שונה בהתבסס על המכונה שקוראת לו?) אבל על פניו אני אכן לא רואה איתו בעיה עקרונית. | |
|
|
|
|
|
||
|
||||
|
פתחתי את הדיון הזה בכך שניסיתי להגיד שאת ההוכחה לבעיית העצירה ניתן להכליל כך שתחול לא רק על מכונות טיורינג, אלא על מודלים כלליים יותר. בהמשך הדיון הוברר שעדיין צריך להניח הנחות מסוימות על המודל. ניסיתי להפריך את הטענה שקיום מכונה אוניברסלית היא תנאי הכרחי לצורך ההוכחה, ולכן הבאתי מודל מאד מוזר, שכל מטרתו להוכיח את זה. כעת נשאלת השאלה האם ניתן לנסח תנאי יותר חלש מקיום מכונה אוניברסלית (למשל קיום מכונה ''כמעט אוניברסלית'', שזו מכונה שעוצרת אמ''מ המכונה שהיא קיבלה כקלט עוצרת על הקלט שלה), שיספיק על מנת שהוכחה תהיה תקפה לכל מודל שמקיים אותו. שאלה נוספת היא האם קיים מודל מעניין שאין בו מכונה אוניברסלית אבל יש בו מכונה כמעט אוניברסלית (או שמקיים את התנאי החלש יותר, אם מנסחים אותו באופן אחר). |
|
|
|
|
|
|
||
|
||||
|
קצת הלכתי לאיבוד, אז אולי תוכל להחזיר אותי חזרה לתמונה - תוכיח לי שבמודל שהצעת כרגע בעיית העצירה לא פתירה. | |
|
|
|
|
|
||
|
||||
|
תוותר לי על המשקל והחריזה, נכון? נניח שקיימת מכונה 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 (כשהיא קואת לאורקל) את התשובה "מכונה זו עוצרת תמיד". |
|
|
|
|
|
|
||
|
||||
|
עכשיו אני ממש מבולבל. מה זה "אורקל" בשבילך? בשבילי אורקל הוא קופסה שחורה שמכריעה שפות - שואלים אותה על מילה והיא עונה "כן" אם המילה בשפה ו"לא" אם לא. ממה שכתבת כאן אני מקבל את הרושם שאתה תופס אורקל (לפחות בהקשר הזה) בתור משהו שיכול לענות רק תשובה אחת, שוב ושוב. מה שזה בעצם אומר הוא שכל מכונת טיורינג מגיעה עם עוד "ביט מידע חבוי" (שני ביטים, בעצם, כי יכולים להיות שלושה ערכים) שאינו חלק מהקידוד שלה ורק לה יש גישה אליו. | |
|
|
|
|
|
||
|
||||
|
האורקל הזה הוא קופסה שחורה ששואלים אותה על מילה והיא עונה אחד מ- 3 ערכים. העניין הוא שבמודל הזה המכונה שניגשת לאורקל חייבת לתת כקלט לאורקל את עצמה. זה שקול לכך שכל מכונה מגיעה עם עוד טריט מידע חבוי, שאינו חלק מהקידוד שלה (אם כי מוגדר חד ערכית ע"י הקידוד שלה) ושרק לה יש גישה אליו. | |
|
|
|
|
|
||
|
||||
|
טוב ויפה, אבל בוא נניח שעל קלט כלשהו P פונה לאורקל שלה פעמיים כדי לבדוק שתי מילים שונות, והוא מחזיר לה פעם 0 ופעם 1. אף אחת משלוש המכונות שהצעת לא מסמלצת את ההתנהגות הזו. (אם הכוונה שלך היא "המכונה יכולה לשאול את האורקל אך ורק על מילה בודדת - המילה שמייצגת אותה עצמה" - אז כאמור, אין צורך בדיבורים על אורקל ומספיק לדבר על ביט חבוי). |
|
|
|
|
|
|
||
|
||||
|
אתה צודק בהחלט. הגדרתי את האורקל כך בדיוק כדי שאכן אחת משלוש המכונות תסמלץ את ההתנהגות. למעשה, כמו שאתה מציין - ביט חבוי הוא תיאור פחות עקום, והוא אפילו מרשה קיום של שתי מכונות זהות עם ביט חבוי שונה: מהסיבה שאתה אמרת לפני כמה תגובות לא קיימת מכונה אוניברסלית למודל כזה (היא לא תדע להבדיל בין המכונות הזהות עם ביט חבוי שונה), אבל קיימות שתי מכונות כמעט אוניברסליות, כך שכל מכונה מסומלצת ע"י אחת מהן לפחות - וזה כבר מספיק כדי שההוכחה תהיה תקפה. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |