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

נלקח מויקיפדיה

הגדרות נוספות הקשורות לאורקל (מדעי המחשב):
•סיבוכיות חישובית
•חישוביות