ماشین اوراکل

در نظریۀ پیچیدگی و نظریۀ محاسبه پذیری، ماشین اوراکل (یا ماشین سروش) یک ماشین انتزاعی برای مطالعۀ مسائل تصمیم است. می توان آن را به عنوان ماشین تورینگ همراه با یک جعبۀ سیاه ، که به آن اوراکل گفته می شود، در نظر گرفت که قادر به تصمیم گیریِ مسائل تصمیم خاصّی در یک تک اقدام است. مسئله می تواند از هر ردۀ پیچیدگی باشد. حتّی مسائل تصمیم ناپذیر، مثلِ مسئلۀ توقّف، می توانند استفاده شوند.
یک مسئلۀ تصمیم به صورت مجموعۀ A از اعداد طبیعی (یا رشته ها) بیان می شود. یک نمونه از مسئله یک عدد طبیعی (یا رشته)ی دل خواه است. پاسخ به این نمونه در صورتی که عدد (یا رشته) عضو این مجموعه باشد «بله» و در غیر این صورت «نه» می باشد.
مسئلۀ تابع به صورت یک تابع f از اعداد طبیعی (یا رشته ها) به اعداد طبیعی (یا رشته ها) بیان می شود. یک نمونه از این مسئله یک ورودی x برای f؛ و پاسخ آن مقدار (f(x است.
ماشین اوراکل را می توان یک ماشین تورینگ متصّل به یک اوراکل تصوّر کرد. اوراکل، در این مبحث، موجودیّتی قادر به حل یک سری مسائل است، که به عنوان مثال می تواند مسئلۀ تصمیم یا مسئلۀ تابع باشد. مسئله ممکن است محاسبه پذیر نباشد؛ اوراکل یک ماشین تورینگ یا برنامۀ کامپیوتری تلقّی نمی شود. اوراکل به طورِ ساده یک «جعبۀ سیاه» است که قادر به تولید پاسخی برای هر نمونه از یک مسئلۀ محاسباتی است:
یک ماشین اوراکل می تواند تمام اعمال معمول یک ماشین تورینگ را به انجام برساند، و هم چنین می تواند از اوراکل برای به دست آوردن پاسخی برای هر نمونه از مسئلۀ محاسباتی برای آن اوراکل بهره ببرد. برای مثال اگر مسئله یک مسئلۀ تصمیم بر روی یک مجموعۀ A از اعداد طبیعی باشد، ماشین اوراکل یک عدد طبیعی به اوراکل عرضه می دارد، و اوراکل بسته به این که آن عدد عضو 'A' باشد با «بله» یا «نه» پاسخ می دهد.
تعاریف هم ارز متعدّدی برای ماشین تورینگ اوراکل وجود دارد، که در پایین در مورد آن ها بحث شده است. موردی که این جا ارائه شده است از van Melkebeek است (۲۰۰۰:۴۳).