בתשובה להאייל האלמוני, 06/01/07 14:48
 |
|
 |
||
|
||||
 |
מה שאורי אמר. אם אין לנו מושג איך לקודד אורקל, אי אפשר להעביר אורקל כקלט. מה ש*כן* אפשר לעשות הוא לנסח *לכל אורקל בנפרד* בעיית עצירה משל עצמו. יותר במדוייק, הבעיה אינה בעצירת האורקל (אורקלים תמיד עוצרים) אלא בעצירת מכונות הטיורינג שמשתמשות באורקל (מכונות כאלו אפשר לקודד בקלות - אפשר להציג אותן כמכונות רגילות, עם שני מצבים מיוחדים חדשים, וראש קורא/כותב נוסף). העניין הוא שלא ניתן להעביר את האורקל (או חשוב מכך, את השפה שהוא מכריע) כקלט, ולכן הבעיה מכילה כאחד מנתוניה את האורקל, ולא כחלק מהקלט. את האפשרות לפתור את הבעיה הזו עם מכונת טיורינג שיש לה אורקל *אחר* אי אפשר להפיל באותה הדרך שבה מפילים את בעיית העצירה. |
 |
 |
 |
|
|
|
||
|
||||
|
וזה מזכיר לי את ההוכחה הנחמדה שאי אפשר לעשות אובפוסקציה למכונת טורינג, כלומר, אי אפשר לקחת תוכנה וליצור ממנה תוכנה מעורבלת כך שמי שיסתכל על התוכנה המעורבלת לא יוכל ללמוד ממנה יותר מאשר מאורקל שמבצע את אותו דבר. | |
|
|
|
|
|
||
|
||||
|
אתה מוזמן לפרט (בינתיים התיאור לא כל כך ברור לי - האם אחרי הערבול עדיין ניתן להריץ את התוכנית? למה הצפנה באמצעות פנקס חד פעמי לא תוביל לתוצאה שכזו? ומה הכוונה ב"ללמוד מאורקל"?) | |
|
|
|
|
|
||
|
||||
|
אני מניח שהכוונה למאמר המשובח הנ"ל |
|
|
|
|
|
|
||
|
||||
|
נשמע מעניין. התווסף לרשימת הקריאה. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |