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