הצגת המקור של הדף "אורקל (מדעי המחשב)"

בתורת ה[[חישוביות]] וב[[תורת הסיבוכיות]], '''אורקל''' (לעיתים נקרא בעברית גם '''פונקציית אוב''') היא מכונה מופשטת שבאמצעותה נחקרות [[בעיית הכרעה|בעיות הכרעה]]. ניתן לדמות אותה ל[[קופסה שחורה (הנדסה)|קופסה שחורה]], שמחוברת ל[[מכונת טיורינג]], ושיש לה יכולת להכריע בעיה מסוימת בצעד [[חישוב (מדעי המחשב)|חישוב]] יחיד. הבעיות עשויות להיות מכל [[מחלקת סיבוכיות]], וניתן להשתמש אף בבעיות שאינן ניתנות לחישוב כלל, כגון [[בעיית העצירה]].

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

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

==אורקל ורדוקציות==

קיומה של [[רדוקציה חישובית]] מפונקציה <math>\ f</math> לפונקציה <math>\ g</math>, היא למעשה [[מקרה פרטי]] של ה[[טענה]], לפיה קיים [[אלגוריתם]] לפונקציה <math>\ f</math> בהינתן אורקל לפונקציה <math>\ g</math>. באופן דומה, משמעות קיומה של [[רדוקציה פולינומית]] מפונקציה <math>\ f</math> לפונקציה <math>\ g</math>, היא למעשה קיומו של אלגוריתם בעל [[זמן ריצה פולינומי]] לפונקציה <math>\ f</math> בהינתן אורקל לפונקציה <math>\ g</math>. לעיתים נוהגים לכנות רדוקציות במובן הרגיל בתור "רדוקציות קארפ" ולדבר גם על "רדוקציות טיורינג" כשהכוונה לאלגוריתם המחשב את <math>\ f</math> באמצעות אורקל ל-<math>\ g</math> (אלגוריתם שיכול לקרוא ל-<math>\ g</math> פעמים רבות על קלטים רבים ושונים, להבדיל מהקריאה הבודדת של רדוקציית קארפ). 

== לקריאה נוספת ==
* Akeo Adachi, ''Foundations of computation theory'', Ohmsha, 1990.
* T. P. Baker, J. Gill, [[Robert M. Solovay|R. Solovay]]. ''Relativizations of the P =? NP Question''. [[SIAM Journal on Computing]], 4(4): 431-442 (1975)
* C. H. Bennett, J. Gill. ''Relative to a Random Oracle A, P<sup>A</sup> != NP<sup>A</sup> != co-NP<sup>A</sup> with Probability 1''. SIAM Journal on Computing, 10(1): 96-113 (1981)
* Egon Börger. "Computability, Complexity, Logic". North-Holland, 1989.
* Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan, Pankaj Rohatgi. The Random Oracle Hypothesis is False. ''Journal of Computer and System Sciences'', volume 49, issue 1, pp. 24–39. August 1994. {{issn|0022-0000}}. http://citeseer.ist.psu.edu/282397.html
* [[Martin Davis]], editor: ''The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions'', Raven Press, New York, 1965. Turing's paper is in this volume. Papers include those by Gödel, Church, Rosser, Kleene, and Post.
* C. Papadimitriou. ''Computational Complexity''. Addison-Wesley, 1994. Section 14.3: Oracles, pp. 339–343.
* Hartley Rogers, Jr., ''Theory of Recursive Functions and Effective Computability'', McGraw-Hill, 1967. 
* [[Michael Sipser]]. ''Introduction to the Theory of Computation''. PWS Publishing, 1997. {{isbn|0-534-94728-X}}. Section 9.2: Relativization, pp. 318–321.
* Robert I. Soare, ''Recursively Enumerable Sets and Degrees'', Perspectives in Mathematical Logic, Springer, 1987. 
* Alan Turing, ''Systems of logic based on ordinals'', Proc. London math. soc., '''45''', 1939
* Dieter van Melkebeek, ''Randomness and Completeness in Computational Complexity'', Lecture Notes in Computer Science 1950, Springer, 2000.

{{קצרמר|מדעי המחשב}}
[[קטגוריה:סיבוכיות חישובית]]
[[קטגוריה:חישוביות]]