בתשובה להאייל האלמוני, 10/01/07 22:20
 |
|
 |
||
|
||||
 |
עכשיו אני ממש מבולבל. מה זה "אורקל" בשבילך? בשבילי אורקל הוא קופסה שחורה שמכריעה שפות - שואלים אותה על מילה והיא עונה "כן" אם המילה בשפה ו"לא" אם לא. ממה שכתבת כאן אני מקבל את הרושם שאתה תופס אורקל (לפחות בהקשר הזה) בתור משהו שיכול לענות רק תשובה אחת, שוב ושוב. מה שזה בעצם אומר הוא שכל מכונת טיורינג מגיעה עם עוד "ביט מידע חבוי" (שני ביטים, בעצם, כי יכולים להיות שלושה ערכים) שאינו חלק מהקידוד שלה ורק לה יש גישה אליו. |  |
 |
 |
|
|
|
||
|
||||
|
האורקל הזה הוא קופסה שחורה ששואלים אותה על מילה והיא עונה אחד מ- 3 ערכים. העניין הוא שבמודל הזה המכונה שניגשת לאורקל חייבת לתת כקלט לאורקל את עצמה. זה שקול לכך שכל מכונה מגיעה עם עוד טריט מידע חבוי, שאינו חלק מהקידוד שלה (אם כי מוגדר חד ערכית ע"י הקידוד שלה) ושרק לה יש גישה אליו. | |
|
|
|
|
|
||
|
||||
|
טוב ויפה, אבל בוא נניח שעל קלט כלשהו P פונה לאורקל שלה פעמיים כדי לבדוק שתי מילים שונות, והוא מחזיר לה פעם 0 ופעם 1. אף אחת משלוש המכונות שהצעת לא מסמלצת את ההתנהגות הזו. (אם הכוונה שלך היא "המכונה יכולה לשאול את האורקל אך ורק על מילה בודדת - המילה שמייצגת אותה עצמה" - אז כאמור, אין צורך בדיבורים על אורקל ומספיק לדבר על ביט חבוי). |
|
|
|
|
|
|
||
|
||||
|
אתה צודק בהחלט. הגדרתי את האורקל כך בדיוק כדי שאכן אחת משלוש המכונות תסמלץ את ההתנהגות. למעשה, כמו שאתה מציין - ביט חבוי הוא תיאור פחות עקום, והוא אפילו מרשה קיום של שתי מכונות זהות עם ביט חבוי שונה: מהסיבה שאתה אמרת לפני כמה תגובות לא קיימת מכונה אוניברסלית למודל כזה (היא לא תדע להבדיל בין המכונות הזהות עם ביט חבוי שונה), אבל קיימות שתי מכונות כמעט אוניברסליות, כך שכל מכונה מסומלצת ע"י אחת מהן לפחות - וזה כבר מספיק כדי שההוכחה תהיה תקפה. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |