موضوع مقاله: ماشین اوراکل | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ماشین اوراکل | مقدمه: در نظریۀ پیچیدگی و نظریۀ محاسبه‌پذیری، ماشین اوراکل (یا ماشین سروش) یک ماشین انتزاعی برای مطالعۀ مسائل تصمیم است. | ## بخش 1: ماشین اوراکل | می‌توان آن‌را به عنوان ماشین تورینگ همراه با یک جعبۀ سیاه ، که به آن اوراکل گفته می‌شود، در نظر گرفت که قادر به تصمیم‌گیریِ مسائل تصمیم خاصّی در یک تک‌اقدام است. اوراکِل‌ها ماشین اوراکل را می‌توان یک ماشین تورینگ متصّل به یک اوراکل تصوّر کرد. اوراکل، در این مبحث، موجودیّتی قادر به حل یک سری مسائل است، که به عنوان مثال می‌تواند مسئلۀ تصمیم یا مسئلۀ تابع باشد. مسئله ممکن است محاسبه‌پذیر نباشد؛ اوراکل یک ماشین تورینگ یا برنامۀ کامپیوتری تلقّی نمی‌شود. اوراکل به طورِ ساده یک «جعبۀ سیاه» است که قادر به تولید پاسخی برای هر نمونه از یک مسئلۀ محاسباتی است: یک مسئلۀ تصمیم به صورت مجموعۀ A از اعداد طبیعی (یا رشته‌ها) بیان می‌شود. پاسخ به این نمونه در صورتی که عدد (یا رشته) عضو این مجموعه باشد «بله» و در غیر این صورت «نه» می‌باشد. مسئلۀ تابع به صورت یک تابع f از اعداد طبیعی (یا رشته‌ها) به اعداد طبیعی (یا رشته‌ها) بیان می‌شود. یک ماشین اوراکل می‌تواند تمام اعمال معمول یک ماشین تورینگ را به انجام برساند، و هم‌چنین می‌تواند از اوراکل برای به دست آوردن پاسخی برای هر نمونه از مسئلۀ محاسباتی برای آن اوراکل بهره ببرد. برای مثال اگر مسئله یک مسئلۀ تصمیم بر روی یک مجموعۀ A از اعداد طبیعی باشد، ماشین اوراکل یک عدد طبیعی به اوراکل عرضه می‌دارد، و اوراکل بسته به این که آن عدد عضو 'A' باشد با «بله» یا «نه» پاسخ می‌دهد. تعاریف تعاریف هم‌ارز متعدّدی برای ماشین تورینگ اوراکل وجود دارد، که در پایین در مورد آن‌ها بحث شده‌است. یک ماشین اوراکل مانند یک ماشین تورینگ شامل اجزای زیر است: یک نوار کار: دنباله‌ای از خانه‌ها بدون شروع یا انتها، که هر کدام می‌تواند شامل یک B (برای خانۀ خالی) یا یک نماد از الفبای نوار باشد؛ یک هِد خواندن/نوشتن، که بر روی یک خانه از نوار کار می‌ایستد و می‌تواند دادۀ آن را بخواند، دادۀ جدید بنویسد، و بر روی نوار به راست یا چپ حرکت کند؛ یک سازوکار کنترلی، که می‌تواند در یکی از متناهی تعداد حالت‌هایش باشد، و بسته به حالت فعلی و دادۀ خوانده‌شده اعمال متفاوتی (خواندن داده، نوشتن داده، حرکت سازوکار کنترلی، و تغییر حالت‌ها) را انجام می‌دهد. علاوه بر این اجزا، یک ماشین اوراکل شامل اجزای زیر نیز هست: یک نوار اوراکل، که نواری نیمه‌نامتناهی جدای از نوار کار است. الفبای نوار اوراکل می‌تواند متفاوت از الفبای نوار کار باشد؛ یک هِد اوراکل که، همانند هِد خواندن/نوشتن، می‌تواند روی نوار اوراکل به چپ یا راست حرکت کرده و نمادها را بخواند یا بنویسد؛ دو حالت ویژه: حالت پرسش و حالت پاسخ. | ## بخش 2: ماشین اوراکل | هنگام این رخ‌داد، اعمال زیر در یک مرحلۀ محاسباتی انجام می‌شوند: محتویّات نوار پرس‌وجو به عنوان یک نمونه از مسئلۀ محاسباتی اوراکل دیده می‌شود؛ پس از مشورت با اوراکل، محتویّات نوار پرس‌وجو با پاسخ آن نمونه از مسئله جای‌گزین می‌شود؛ هِد اوراکل به اوّلین خانه از نوار اوراکل منتقل می‌شود؛ حالت ماشین اوراکل به وضعیّت پاسخ تغییر می‌یابد. بنابراین تأثیر تغییر به حالت پرسش، گرفتن پاسخ، در یک مرحله، به نمونه‌ای از مسئله است که بر روی نوار اوراکل نوشته شده‌است. تعاریف جای‌گزین علاوه بر تعریفی که در بالا ارائه شد تعاریف جای‌گزینِ دیگری نیز وجود دارند. در این مورد: در بعضی تعاریف، به جای نوشتن پاسخ در نوار اوراکِل، دو حالت خاصِّ بله و خیر علاوه بر حالت پرسش وجود دارد. وقتی اوراکِل مورد مشورت قرار می‌گیرد، حالت بله انتخاب می‌شود اگر محتویّات نوار اوراکِل درون مجموعۀ اوراکِل باشد، و حالت خیر انتخاب می‌شود اگر محتویّات درون مجموعۀ اوراکِل نباشد (Adachi ۱۹۹۰:۱۱۱). اگر آن عدد درون مجموعۀ اوراکِل باشد، حالت بعدی حالت بله است؛ در غیر این صورت، حالت بعدی حالت خیر است (Rogers ۱۹۶۷:۱۲۹). تعریف جای‌گزین دیگر نوار اوراکِل را فقط‌خواندنی می‌کند، و حالت‌های پرسش و پاسخ را به‌طور کلّی حذف می‌کند. قبل از شروع به کار ماشین، تابع مشخّصه‌ی مجموعۀ اوراکِل با استفاده از نمادهای ۰ و ۱ روی نوار اوراکِل نوشته می‌شود. پس از آن ماشین قادر است تا با پیدا کردن خانۀ مناسب بر روی نوار اوراکِل و خواندن مقدار ازقبل نوشته‌شده در آن، از اوراکل پرس‌وجو کند (Soare ۱۹۸۷:۴۷، Rogers ۱۹۶۷:۱۳۰). این تعاریف از منظر محاسبه‌پذیری تورینگ معادل هستند: تابعی که تحت اوراکِل یکی از این تعاریف، اوراکِل‌محاسبه‌پذیر باشد، تحت هر دیگری نیز اوراکِل‌محاسبه‌پذیر است. تعریفی مانند آن‌چه که van Melkebeek ارائه داده‌بود، که در آن از نوار اوراکِلی که ممکن است الفبای خود را داشته باشد استفاده می‌شود، در حالت عمومی لازم است. کلاس‌های پیچیدگی ماشین اوراکِل کلاس پیچیدگی مسائل تصمیمِ حل‌پذیر توسّط الگوریتمی در کلاس A با استفاده از اوراکِلی برای زبان AL، L نامیده می‌شود. به‌طور مثال، PSAT کلاس مسائل حل‌پذیر در زمان چندجمله‌ای توسّط یک ماشین تورینگ قطعی با اوراکلی برای مسئلۀ ارضاپذیری بولی (SAT) است. | ## بخش 3: ماشین اوراکل | نمادگذاری AB را می‌توان برای مجموعۀ زبان‌های B (یا کلاس پیچیدگی B)، با استفاده از تعریف زیر، تعمیم داد: زمانی که یک زبانِ L برای کلاس B کامل باشد، آن‌گاه AL=AB در صورتی که ماشین‌های درون A بتوانند تقلیل‌های استفاده‌شده در تعریف کامل بودن کلاس B را اجرا نمایند. به‌طور خاص، از آن‌جایی که مسئلۀ ارضاپذیریِ بولی نسبت به تقلیل‌های زمان چندجمله‌ای ان‌پی کامل است، PSAT=PNP. ماشین‌های اوراکل، با در نظر گرفتن رابطۀ بین PA و NPA برای یک اوراکل A، برای بررسی رابطۀ بین کلاس‌های پیچیدگی P و NP مفید هستند. این حقیقت که پرسش P = NP از هر دو جهت به صورت نسبی است، به این دلیل است که پاسخ به این پرسش دشوار است، زیرا تکنیک اثباتی که به صورت نسبی'' انجام می‌گیرد (بدون تأثیر گرفتن از اضافه شدن یک اوراکل) نمی‌تواند به پرسش P = NP پاسخ دهد. در نظر گرفتن حالتی که یک اوراکل از میان تمام اوراکل‌های ممکن(یک مجموعه بینهایت) به صورت تصادفی انتخاب شود، قابل توجه است. هنگامی که پاسخ سوالی برای همۀ اوراکل‌ها درست باشد، در آن صورت پاسخ پرسش برای یک اوراکل تصادفی نیز درست است. این انتخاب اصطلاحات با دانستن این حقیقت که اوراکل‌های تصادفی یک عبارت را فقط با احتمال 1 یا 0 تأیید می‌کنند، قابل توجیه است. اوراکِل‌ها و مسئلۀ پایان‌پذیری ممکن است که وجود اوراکلی را فرض کرد که قادر به محاسبۀ یک تابع محاسبه‌ناپذیر باشد، مانند پاسخ به مسئلۀ توقّف یا مسائل مشابه دیگر. به طرز جالبی، پارادوکس پایان‌پذیری هنوز در مورد این ماشین‌ها نیز صدق می‌کند؛ با وجود اینکه این ماشین‌ها می‌توانند تعیین کنند که آیا ماشین تورینگ خاصی با ورودی‌های خاصی به حالت پایان خواهد رسید، به‌طور کلی، آن‌ها نمی‌توانند تعیین کنند که آیا ماشین‌های معادل خودشان به حالت پایان خواهند رسید. این حقیقت منجر به ایجاد سلسله مراتبی از ماشین‌ها به نام سلسله مراتب محاسباتی می‌شود، که هر رده دارای اوراکل پایان‌پذیری قوی‌تر و مسئلۀ پایان‌پذیری قوی‌تری است. کاربردها در رمزنگاری در رمزنگاری، اوراکل‌ها برای استدلال در مورد امنیت قراردادهای رمزنگاری که در آن‌ها یک تابع درهم‌ساز استفاده شده‌است، به کار می‌رود. یک کاهش امنیت برای یک قرارداد در حالتی داده می‌شود که، به جای یک تابع درهم‌ساز، یک اوراکل تصادفی به هر درخواست به صورت تصادفی ولی سازگار پاسخ می‌دهد؛ فرض می‌شود که اوراکل در دسترس همۀ طرف‌ها، از جمله حمله‌کننده قرار دارد، همان‌گونه که تابع درهم‌ساز در دسترس همه می‌باشد. | ## جمع‌بندی | چنین اثباتی نشان می‌دهد که مگر در حالتی که حمله‌کننده مسئلۀ دشوار را در قلب کاهش امنیت حل کند، حمله‌کننده باید از خواص جالب توجه تابع درهم‌ساز برای شکستن قرارداد استفاده کند؛ آن‌ها نمی‌توانند با تابع درهم‌ساز به عنوان یک جعبۀ سیاه برخورد کنند (به عنوان یک اوراکل تصادفی).