ماشین اوراکل

ماشین اوراکل را می‌توان یک ماشین تورینگ متصّل به یک اوراکل تصوّر کرد. اوراکل، در این مبحث، موجودیّتی قادر به حل یک سری مسائل است، که به عنوان مثال می‌تواند مسئلۀ تصمیم یا مسئلۀ تابع باشد. مسئله ممکن است محاسبه‌پذیر نباشد؛ اوراکل یک ماشین تورینگ یا برنامۀ کامپیوتری تلقّی نمی‌شود. اوراکل به طورِ ساده یک «جعبۀ سیاه» است که قادر به تولید پاسخی برای هر نمونه از یک مسئلۀ محاسباتی است:

• یک مسئلۀ تصمیم به صورت مجموعۀ A از اعداد طبیعی (یا رشته‌ها) بیان می‌شود. یک نمونه از مسئله یک عدد طبیعی (یا رشته)ی دل‌خواه است. پاسخ به این نمونه در صورتی که عدد (یا رشته) عضو این مجموعه باشد «بله» و در غیر این صورت «نه» می‌باشد.
• مسئلۀ تابع به صورت یک تابع f از اعداد طبیعی (یا رشته‌ها) به اعداد طبیعی (یا رشته‌ها) بیان می‌شود. یک نمونه از این مسئله یک ورودی x برای f؛ و پاسخ آن مقدار (f(x است.

یک ماشین اوراکل می‌تواند تمام اعمال معمول یک ماشین تورینگ را به انجام برساند، و هم‌چنین می‌تواند از اوراکل برای به دست آوردن پاسخی برای هر نمونه از مسئلۀ محاسباتی برای آن اوراکل بهره ببرد. برای مثال اگر مسئله یک مسئلۀ تصمیم بر روی یک مجموعۀ A از اعداد طبیعی باشد، ماشین اوراکل یک عدد طبیعی به اوراکل عرضه می‌دارد، و اوراکل بسته به این که آن عدد عضو 'A' باشد با «بله» یا «نه» پاسخ می‌دهد.

تعاریف هم‌ارز متعدّدی برای ماشین تورینگ اوراکل وجود دارد، که در پایین در مورد آن‌ها بحث شده‌است. موردی که این‌جا ارائه شده‌است از van Melkebeek است (۲۰۰۰:۴۳).

یک ماشین اوراکل مانند یک ماشین تورینگ شامل اجزای زیر است:

• یک نوار کار: دنباله‌ای از خانه‌ها بدون شروع یا انتها، که هر کدام می‌تواند شامل یک B (برای خانۀ خالی) یا یک نماد از الفبای نوار باشد؛
• یک هِد خواندن/نوشتن، که بر روی یک خانه از نوار کار می‌ایستد و می‌تواند دادۀ آن را بخواند، دادۀ جدید بنویسد، و بر روی نوار به راست یا چپ حرکت کند؛
• یک سازوکار کنترلی، که می‌تواند در یکی از متناهی تعداد حالت‌هایش باشد، و بسته به حالت فعلی و دادۀ خوانده‌شده اعمال متفاوتی (خواندن داده، نوشتن داده، حرکت سازوکار کنترلی، و تغییر حالت‌ها) را انجام می‌دهد.

علاوه بر این اجزا، یک ماشین اوراکل شامل اجزای زیر نیز هست:

• یک نوار اوراکل، که نواری نیمه‌نامتناهی جدای از نوار کار است. الفبای نوار اوراکل می‌تواند متفاوت از الفبای نوار کار باشد؛
• یک هِد اوراکل که، همانند هِد خواندن/نوشتن، می‌تواند روی نوار اوراکل به چپ یا راست حرکت کرده و نمادها را بخواند یا بنویسد؛
• دو حالت ویژه: حالت پرسش و حالت پاسخ.

گاه‌به‌گاه، ماشین اوراکل ممکن است وارد حالت پرسش شود. هنگام این رخ‌داد، اعمال زیر در یک مرحلۀ محاسباتی انجام می‌شوند:

• محتویّات نوار پرس‌وجو به عنوان یک نمونه از مسئلۀ محاسباتی اوراکل دیده می‌شود؛
• پس از مشورت با اوراکل، محتویّات نوار پرس‌وجو با پاسخ آن نمونه از مسئله جای‌گزین می‌شود؛
• هِد اوراکل به اوّلین خانه از نوار اوراکل منتقل می‌شود؛
• حالت ماشین اوراکل به وضعیّت پاسخ تغییر می‌یابد.

بنابراین تأثیر تغییر به حالت پرسش، گرفتن پاسخ، در یک مرحله، به نمونه‌ای از مسئله است که بر روی نوار اوراکل نوشته شده‌است.

تعاریف جای‌گزین

علاوه بر تعریفی که در بالا ارائه شد تعاریف جای‌گزینِ دیگری نیز وجود دارند. تعدادی از آن‌ها خاصِّ موردی هستند که اوراکِل یک مسئلۀ تصمیم را حل می‌کند. در این مورد:

• در بعضی تعاریف، به جای نوشتن پاسخ در نوار اوراکِل، دو حالت خاصِّ بله و خیر علاوه بر حالت پرسش وجود دارد. وقتی اوراکِل مورد مشورت قرار می‌گیرد، حالت بله انتخاب می‌شود اگر محتویّات نوار اوراکِل درون مجموعۀ اوراکِل باشد، و حالت خیر انتخاب می‌شود اگر محتویّات درون مجموعۀ اوراکِل نباشد (Adachi ۱۹۹۰:۱۱۱).
• بعضی تعاریف از نوار اوراکِل مجزّا خودداری می‌کنند. هنگامی که وارد حالت اوراکِل می‌شویم، یک نماد نوار مشخّص می‌شود. تعداد دفعاتی که این نماد روی نوار کار ظاهر شده‌است از اوراکِل پرسیده‌ می‌شود. اگر آن عدد درون مجموعۀ اوراکِل باشد، حالت بعدی حالت بله است؛ در غیر این صورت، حالت بعدی حالت خیر است (Rogers ۱۹۶۷:۱۲۹).
• تعریف جای‌گزین دیگر نوار اوراکِل را فقط‌خواندنی می‌کند، و حالت‌های پرسش و پاسخ را به‌طور کلّی حذف می‌کند. قبل از شروع به کار ماشین، تابع مشخّصه‌ی مجموعۀ اوراکِل با استفاده از نمادهای ۰ و ۱ روی نوار اوراکِل نوشته می‌شود. پس از آن ماشین قادر است تا با پیدا کردن خانۀ مناسب بر روی نوار اوراکِل و خواندن مقدار ازقبل نوشته‌شده در آن، از اوراکل پرس‌وجو کند (Soare ۱۹۸۷:۴۷، Rogers ۱۹۶۷:۱۳۰).

این تعاریف از منظر محاسبه‌پذیری تورینگ معادل هستند: تابعی که تحت اوراکِل یکی از این تعاریف، اوراکِل‌محاسبه‌پذیر باشد، تحت هر دیگری نیز اوراکِل‌محاسبه‌پذیر است. هرچند از منظر پیچیدگی محاسباتی، این تعاریف معادل نیستند. تعریفی مانند آن‌چه که van Melkebeek ارائه داده‌بود، که در آن از نوار اوراکِلی که ممکن است الفبای خود را داشته باشد استفاده می‌شود، در حالت عمومی لازم است.

کلاس پیچیدگی مسائل تصمیمِ حل‌پذیر توسّط الگوریتمی در کلاس A با استفاده از اوراکِلی برای زبان A، L نامیده می‌شود. به‌طور مثال، P کلاس مسائل حل‌پذیر در زمان چندجمله‌ای توسّط یک ماشین تورینگ قطعی با اوراکلی برای مسئلۀ ارضاپذیری بولی (SAT) است. نمادگذاری A را می‌توان برای مجموعۀ زبان‌های B (یا کلاس پیچیدگی B)، با استفاده از تعریف زیر، تعمیم داد:

${\displaystyle A^{B}=\bigcup _{L\in B}A^{L}}$

زمانی که یک زبانِ L برای کلاس B کامل باشد، آن‌گاه A=A در صورتی که ماشین‌های درون A بتوانند تقلیل‌های استفاده‌شده در تعریف کامل بودن کلاس B را اجرا نمایند. به‌طور خاص، از آن‌جایی که مسئلۀ ارضاپذیریِ بولی نسبت به تقلیل‌های زمان چندجمله‌ای ان‌پی کامل است، P=P. هرچند، اگر A=DLOGTIME (کلاس مسائل حل‌پذیر در زمان لگاریتمی توسّط ماشین تورینگ قطعی)، آن‌گاه A ممکن است برابر با A نباشد.

واضح است که NP ⊆ P، ولی این پرسش که آیا NP، P، NP و P برابر هستند یا نه، در بهترین حالت عملی باقی می‌مانند. باور بر تفاوت آن‌هاست و این باعث تعریف سلسله‌مراتب چندجمله‌ای می‌شود.

ماشین‌های اوراکل، با در نظر گرفتن رابطۀ بین P و NP برای یک اوراکل A، برای بررسی رابطۀ بین کلاس‌های پیچیدگی P و NP مفید هستند. به‌طور خاص، نشان داده شده‌است که وجود دارند زبان‌های A و B، به قسمی که P=NP و (Gill P≠NP، Baker و Solovay 1975). این حقیقت که پرسش P = NP از هر دو جهت به صورت نسبی است، به این دلیل است که پاسخ به این پرسش دشوار است، زیرا تکنیک اثباتی که به صورت نسبی انجام می‌گیرد (بدون تأثیر گرفتن از اضافه شدن یک اوراکل) نمی‌تواند به پرسش P = NP پاسخ دهد. بسیاری از تکنیک‌های اثبات از نسبی سازی استفاده می‌کنند.

در نظر گرفتن حالتی که یک اوراکل از میان تمام اوراکل‌های ممکن(یک مجموعه بینهایت) به صورت تصادفی انتخاب شود، قابل توجه است. در این حالت نشان داده شده‌است که با احتمال یک، P≠NP (Bennet و Gill 1981). هنگامی که پاسخ سوالی برای همۀ اوراکل‌ها درست باشد، در آن صورت پاسخ پرسش برای یک اوراکل تصادفی نیز درست است. این انتخاب اصطلاحات با دانستن این حقیقت که اوراکل‌های تصادفی یک عبارت را فقط با احتمال 1 یا 0 تأیید می‌کنند، قابل توجیه است. (این از روی قانون یک‌صفر Kolmogorov بدست می‌آید.) به عنوان یک گواه P≠NP. یک عبارت ممکن است همزمان برای یک اوراکل تصادفی درست و برای یک ماشین تورینگ عادی غلط باشد؛ برای مثال برای اوراکل‌های A، IP≠PSPACE، در حالی که IP = PSPACE (Chang et al، 1994).

ممکن است که وجود اوراکلی را فرض کرد که قادر به محاسبۀ یک تابع محاسبه‌ناپذیر باشد، مانند پاسخ به مسئلۀ توقّف یا مسائل مشابه دیگر. ماشینی با چنین اوراکلی یک فراکامپیوتر است.

به طرز جالبی، پارادوکس پایان‌پذیری هنوز در مورد این ماشین‌ها نیز صدق می‌کند؛ با وجود اینکه این ماشین‌ها می‌توانند تعیین کنند که آیا ماشین تورینگ خاصی با ورودی‌های خاصی به حالت پایان خواهد رسید، به‌طور کلی، آن‌ها نمی‌توانند تعیین کنند که آیا ماشین‌های معادل خودشان به حالت پایان خواهند رسید. این حقیقت منجر به ایجاد سلسله مراتبی از ماشین‌ها به نام سلسله مراتب محاسباتی می‌شود، که هر رده دارای اوراکل پایان‌پذیری قوی‌تر و مسئلۀ پایان‌پذیری قوی‌تری است.

در رمزنگاری، اوراکل‌ها برای استدلال در مورد امنیت قراردادهای رمزنگاری که در آن‌ها یک تابع درهم‌ساز استفاده شده‌است، به کار می‌رود. یک کاهش امنیت برای یک قرارداد در حالتی داده می‌شود که، به جای یک تابع درهم‌ساز، یک اوراکل تصادفی به هر درخواست به صورت تصادفی ولی سازگار پاسخ می‌دهد؛ فرض می‌شود که اوراکل در دسترس همۀ طرف‌ها، از جمله حمله‌کننده قرار دارد، همان‌گونه که تابع درهم‌ساز در دسترس همه می‌باشد. چنین اثباتی نشان می‌دهد که مگر در حالتی که حمله‌کننده مسئلۀ دشوار را در قلب کاهش امنیت حل کند، حمله‌کننده باید از خواص جالب توجه تابع درهم‌ساز برای شکستن قرارداد استفاده کند؛ آن‌ها نمی‌توانند با تابع درهم‌ساز به عنوان یک جعبۀ سیاه برخورد کنند (به عنوان یک اوراکل تصادفی).

• ماشین تورینگ

صفحۀ ماشین اوراکِل در ویکی‌پدیایِ انگلیسی