אורקל (מדעי המחשב)

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

מכונת טיורינג עם אורקל היא מכונה תיאורטית שיש לה אפשרות לשלוח קלט לאורקל ולקבל בחזרה פלט. ההחלפה של הקלט בפלט נעשית כצעד חישוב יחיד. ניתן להגדיר מכונות עם יותר מאורקל אחד, ואפשר גם לשקול אינסוף אורקלים.

אורקלים משמשים כדי לקשר בין שאלות על אילו פונקציות ניתנות לחישוב או ניתנות לחישוב בזמן קצר. אומרים שפונקציה f ניתנת לחישוב מתוך פונקציה g אם קיימת מכונת טיורינג שמחשבת את f כשהיא משתמשת ב-g כאורקל. הגדרה כזו יוצרת קדם-סדר על אוסף פונקציות, ומובילה למושגים כמו דרגות טיורינג וסדר חלקי של "ניתנות לחישוב". אפשר לעדן את היחס הזה על ידי דרישות זמן חישוב, למשל זמן פולינומי, וכך מקבלים היררכיות כמו ההיררכיה הפולינומית.

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

אורקל הוא קופסה שחורה שנותנת תשובות לשאלה בודדת בצעד אחד. קופסה שחורה הוא דבר שאפשר לשאול אבל לא לראות איך הוא עובד. אורקלים יכולים לפתור בעיות מאוד קשות, אפילו בעיות שלא תמיד אפשר לחשב, כמו בעיית העצירה (שאלה אם תוכנה תפסיק או תרוץ לנצח).

מכונת טיורינג היא דרך לתאר מחשב פשוט בתור מודל. מכונת טיורינג עם אורקל שואלת את הקופסה וקופסת התשובות מחזירה פלט מיד.

רדוקציה היא דרך להמיר בעיה אחת לשאלה שאורקל אחר יודע לפתור. אם אפשר לחשב פונקציה f כשיש אורקל עבור g, אומרים שיש רדוקציה מ-f ל-g. רדוקציות קארפ קוראות לאורקל פעם אחת. רדוקציות טיורינג יכולות לקרוא לאורקל כמה פעמים על קלטים שונים.