אורקל (מדעי המחשב) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ רובוט מוסיף: ja:神託機械 |
הגדרה יותר פורמלית |
||
שורה 1:
בתורת ה[[חישוביות]] ובתורת ה[[סיבוכיות]], '''אורקל''' היא מכונה מופשטת שבאמצעותה נחקרות [[בעיית הכרעה|בעיות הכרעה]]. ניתן לדמות אותה לקופסה שחורה, שמחוברת ל[[מכונת טיורינג]], ושיש לה יכולת להכריע בעיה מסוימת בצעד חישוב יחיד. הבעיות עשויות להיות מכל מחלקת סיבוכיות, וניתן להשתמש אף בבעיות שאינן ניתנות לחישוב כלל, כגון [[בעיית העצירה]].
'''מכונת טיורינג עם אורקל''' היא מכונת טיורינג בעלת שני סרטים, שיש באפשרותה לתת לאורקל הוראה להחליף את הקלט שעל אחד הסרטים של המכונה בפלט החישוב של האורקל עבור אותו קלט. הוראה זו נחשבת לצעד חישוב יחיד. ניתן להגדיר גם מכונת טיורינג עם יותר מאורקל אחת,
שימוש נפוץ באורקלים, הוא יצירת קשר בין שאלות פתוחות שונות, העוסקות בהיותן של פונקציות [[חישוביות|ניתנות לחישוב]] או ניתנות לחישוב ב[[זמן ריצה פולינומי]]. זאת כיוון שמושג האורקל מאפשר להגדיר היררכיה בין [[פונקציה|פונקציות]] מהטבעיים לעצמם. פונקציה f נחשבת לניתנת לחישוב מתוך הפונקציה g אם ניתן לחשב את f, על ידי מכונת טיורינג לדוגמה, כאשר g משמשת כאורקל. הגדרה כזו יוצרת [[חצי יחס סדר]] על אוסף הפונקציות הנבחר. באופן הזה, כאשר נבחר בתור הקבוצה את כלל הפונקציות מהטבעיים לעצמם, ניתן להגדיר את [[דרגות טיורינג]] ואת יחס הסדר החלקי של "ניתנות לחישוב". ניתן ליצור את אותה ההגדרה גם על [[שפה (מדעי המחשב)|שפות]]. כמו כן, ניתן לעדן את היחס על ידי דרישה שזמן החישוב של f מתוך g יהיה [[פולינום|פולינומיאלי]], לינארי וכו'. לדוגמה, עבור דרישה של זמן חישוב פולינומיאלי ועל ידי בחירה מתאימה של אוסף הפונקציות או השפות, מתקבלת [[ההיררכייה הפולינומית]].
==אורקל ורדוקציות==
קיומה של [[רדוקציה חישובית]] מפונקציה <math>\ f</math> לפונקציה <math>\ g</math>, היא למעשה מקרה פרטי של הטענה, לפיה קיים אלגוריתם לפונקציה <math>\ f</math> בהינתן אורקל לפונקציה <math>\ g</math>. באופן דומה, משמעות קיומה של [[רדוקציה פולינומית]] מפונקציה <math>\ f</math> לפונקציה <math>\ g</math>,
[[קטגוריה:סיבוכיות]]
| |||