ماشین اوراکل
From Wikipedia, the free encyclopedia
در نظریۀ پیچیدگی و نظریۀ محاسبهپذیری، ماشین اوراکل (یا ماشین سروش) یک ماشین انتزاعی برای مطالعۀ مسائل تصمیم است. میتوان آنرا به عنوان ماشین تورینگ همراه با یک جعبۀ سیاه ، که به آن اوراکل گفته میشود، در نظر گرفت که قادر به تصمیمگیریِ مسائل تصمیم خاصّی در یک تکاقدام است. مسئله میتواند از هر ردۀ پیچیدگی باشد. حتّی مسائل تصمیمناپذیر، مثلِ مسئلۀ توقّف، میتوانند استفاده شوند.