בתשובה להאייל האלמוני, 06/01/07 14:48
שאלת תם 428052
מה שאורי אמר. אם אין לנו מושג איך לקודד אורקל, אי אפשר להעביר אורקל כקלט.

מה ש*כן* אפשר לעשות הוא לנסח *לכל אורקל בנפרד* בעיית עצירה משל עצמו. יותר במדוייק, הבעיה אינה בעצירת האורקל (אורקלים תמיד עוצרים) אלא בעצירת מכונות הטיורינג שמשתמשות באורקל (מכונות כאלו אפשר לקודד בקלות - אפשר להציג אותן כמכונות רגילות, עם שני מצבים מיוחדים חדשים, וראש קורא/כותב נוסף). העניין הוא שלא ניתן להעביר את האורקל (או חשוב מכך, את השפה שהוא מכריע) כקלט, ולכן הבעיה מכילה כאחד מנתוניה את האורקל, ולא כחלק מהקלט.

את האפשרות לפתור את הבעיה הזו עם מכונת טיורינג שיש לה אורקל *אחר* אי אפשר להפיל באותה הדרך שבה מפילים את בעיית העצירה.
שאלת תם 428071
וזה מזכיר לי את ההוכחה הנחמדה שאי אפשר לעשות אובפוסקציה למכונת טורינג, כלומר, אי אפשר לקחת תוכנה וליצור ממנה תוכנה מעורבלת כך שמי שיסתכל על התוכנה המעורבלת לא יוכל ללמוד ממנה יותר מאשר מאורקל שמבצע את אותו דבר.
שאלת תם 428087
אתה מוזמן לפרט (בינתיים התיאור לא כל כך ברור לי - האם אחרי הערבול עדיין ניתן להריץ את התוכנית? למה הצפנה באמצעות פנקס חד פעמי לא תוביל לתוצאה שכזו? ומה הכוונה ב"ללמוד מאורקל"?)
שאלת תם 428175
אני מניח שהכוונה למאמר המשובח הנ"ל
שאלת תם 428191
נשמע מעניין. התווסף לרשימת הקריאה.

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים