ماشین تورینگ غیرقطعی

در علوم کامپیوتر نظری، ماشین تورینگ نظری یک ماشین است که در آزمایش‌های فکری برای آزمایش توانایی‌ها و محدودیت‌های کامپیوتر استفاده می‌شود. دراصل، ماشین تورینگ به صورت یک کامپیوتر ساده تصور می‌شود که با دنبال کردن مجموئه‌ای از قوانین، نمادها را در واحد زمان می‌خواند و بر روی یک نوار بی پایان می‌نویسد؛ و با توجه به وضعیت جاری نمادی که دیده است، تعیین می‌کند چه عملی باید انجام دهد. یک مثال از قوانین ماشین تورینگ: «اگر در وضعیت ۲ هستید و نماد 'A' دیدید، آن را به 'B' تغییر دهید و به چپ بروید.»

در ماشین تورینگ قطعی، مجموعهٔ قوانین به ازای هر وضعیت داده شده، حداکثر یک حرکت را مجاز می‌کند. ماشین تورینگ غیرقطعی (به انگلیسی: Non-deterministic Turing machine) برخلاف ماشین تورینگ قطعی، دارای مجموعه قوانینی است که به ازای هر وضعیت، بیشتر از یک حرکت را مجاز می‌کند. برای مثال، ماشین تورینگ غیرقطعی ممکن است هر دو قوانین «اگر در وضعیت ۲ هستید و نماد ‘A’ دیدید، آن را به ‘B’ تغییردهید و به چپ بروید.» و «اگر در وضعیت ۲ هستید و نماد ‘A’ دیدید، آن را به ‘C’ تغییر دهید و به راست بروید» را در مجموعه قوانینش داشته باشد.

ماشین تورینگ معمولی (قطعی - DTM) دارای تابع انتقال است که برای وضعیت داده شده و نمادی که روی نوار به آن اشاره می‌شود، ۳ چیز را مشخص می‌کند: نمادی که باید روی نوار نوشته شود، جهت حرکت هد (چپ، راست یا هیچکدام) و وضعیت بعدی ...

برای مثال، X روی نوار در وضعیت ۳ ممکن است DTM را وادار به نوشتن Y روی نوار، حرکت هد به راست و انتقال به وضعیت ۵ کند. تفاوت ماشین تورینگ غیرقطعی (NTM) این است که وضعیت داده شده و نماد روی نوار ۳چیز منحصربه فرد را مشخص نمی‌کند، بلکه برای ترکیب مشابه از وضعیت و نماد ممکن است انتقال‌های متفاوتی انجام شود. برای مثال، X روی نوار در وضعیت۳ ممکن است به ماشین اجازه دهد Y را روی نوار بنویسد، به راست برود و به وضعیت ۵ برود یا X را بنویسد، به چپ برود و در وضعیت ۳ بماند.

تعاریف

ماشین تورینگ غیرقطعی به‌طور رسمی یک ۶-تایی $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )$ است به طوریکه:

• $Q$ مجموعه متناهی از وضعیت‌ها
• $\Sigma$ مجموعهٔ متناهی از الفبای ورودی
• $\iota \in Q$ وضعیت شروع
• $\sqcup \in \Sigma$ نماد خالی
• $A\subseteq Q$ مجموعه حالت‌های پذیرش
• $\delta \subseteq \left(Q\backslash A\times \Sigma \right)\times \left(Q\times \Sigma \times \{L,R\}\right)$ ارتباط بین وضعیت‌ها و نمادها که رابطهٔ انتقال نامیده می‌شود.

تفاوت بین ماشین تورینگ استاندارد (قطعی) و غیرقطعی این است که در قطعی رابطه انتقال تابع است (تابع انتقال).

حالت‌ها و عملکرد رابطه روی حالت‌ها که انتقال‌های ممکن تورینگ ماشین با اجزای ممکن نوار را توصیف می‌کند، مانند ماشین تورینگ استاندار است بجزاینکه حاصل رابطه دیگر یک مقدار تنها نیست. مفهوم پذیرش رشته بدون تغییر است: ماشین تورینگ غیرقطعی یک رشته را می‌پذیرد اگر، زمانی که ماشین شروع به کار می‌کند هد روی اولین کاراکتر رشته و در غیراینصورت کل نوار خالی باشد. حداقل یکی از محاسبات ماشین ماشین را از آن حالت در وضعیت $A$ قرار می‌دهد (اگر ماشین قطعی باشد، محاسبات ممکن، پیشوندی از یک، واحتمالا نامحدود مسیر می‌باشد)

حل قوانین متعدد

چگونه NTM تشخیص می‌دهد کدام حرکت را باید انجام دهد؟ ۲ روش وجود دارد. اولی اینکه بگوییم «ماشین خوش شانس ترین حدس زنندهٔ ممکن است»؛ همیشه انتقالی را انتخاب می‌کند که به وضعیت پذیرش می‌رود (اگرچنین انتقالی موجود باشد). راه دیگر تصور این است که ماشین به چند کپی از خودش تقسیم می‌شود که هرکدام یکی از حرکت‌های ممکن را دنبال می‌کند. درحالیکه DTM یک مسیر محاسباتی را دنبال می‌کند، NTM دارای درخت محاسباتی است. اگر حداقل یکی از شاخه‌های درخت به وضعیت پذیرش برود، می‌گوییم NTM ورودی را پذیرفته است.

هم‌ارزی DTMها

به‌طور ویژه ماشین‌های تورینگ غیرقطعی با ماشین‌های تورینگ قطعی هم‌ارزند. این هم‌ارزی به اینکه چه چیزی می‌تواند محاسبه شود برمی‌گردد، برخلاف سرعتش.

NTMها درموارد خاص شامل DTMها می‌شوند؛ بنابراین واضح است که DTMها قدرتمندتر نیستند. ممکن است به نظر برسد که NTMها از DTMها قدرتمندترند، زیرا آن‌ها یک درخت از محاسبات ممکن را ناشی از حالت مشابه ممکن می‌سازند و رشته را اگر هر یک از شاخه‌های درخت پذیرشش کند، می‌پذیرند.

اما شبیه‌سازی NTMها با DTMها امکان‌پذیراست: روش اول استفاده از DTM است به طوریکه هر حالت نشان دهندهٔ چند حالت در NTM است وعملیات DTM شامل مراجعه به هر کدام به نوبهٔ خود، انجام یک مرحله در هر مراجعه و جابه‌جایی به حالت جدید هرگاه رابطه انتقال چند حالت را تعریف کند، می‌باشد.

روش دیگر شبیه‌سازی NTM، استفاده از DTM با ۳ نواراست؛ که نوار اول همیشه ورودی اولیه را نگهداری می‌کند، نوار دوم محاسبات مشخص NTM را شبیه‌سازی می‌کند و نوار سوم مسیر را در درخت محاسبات NTM کدگذاری می‌کند.

DTMهای ۳ نواره به آسانی با DTM تک نواره معمولی شبیه‌سازی می‌شود. در این روش ساخت، ِDTM حاصل جستجوی اول سطحی از درخت محاسبات NTM را انجام می‌دهد؛ و همهٔ حالات ممکن را می‌بیند تا وقتی که یک کدام را پذیرش کند.

بنابراین، طول مسیرپذیرش در DTM نمایی است با توجه به طول کوتاهترین مسیر پذیرش درNTM. این یک ویژگی کلی شبیه‌سازی NTM با DTM است. مشهورترین مسئلهٔ حل نشده در علوم کامپیوتر مسئله P = NP به این موضوع مربوط است.

NTM این خاصیت را دارد. مثلاً اگر NTM با ورودی نوار داده شده متوقف شود آنگاه روی تعداد مراحل محدودی متوقف شده بنابراین تنها می‌تواند تعداد محدودی حالت ممکن داشته باشد. مقایسه با کامپیوترهای کوانتوم این یک تصور غلط است که کامپیوترهای کوانتوم NTM می‌باشند. این باورشده‌است اما هنوز اثبات نشده‌است که قدرت کامپیوترهای کوانتوم قابل مقایسه با NTMهاست. مسئله‌ای وجود دارد که NTM به‌طور مؤثر می‌تواند حلش کند اما کامپیوتر کوانتوم نمی‌تواند. از مسائل قابل حل با NTM اما غیرقابل حل با کامپیوترهای کوانتوم در زمان چندجمله‌ای مسائل NP-complete می‌باشند.

عدم قطعیت محدود

NTM این خاصیت را دارد. مثلاً اگر NTM با ورودی نوار داده شده متوقف شود آنگاه روی تعداد مراحل محدودی متوقف شده بنابراین تنها می‌تواند تعداد محدودی حالت ممکن داشته باشد.

مقایسه با کامپیوترهای کوانتومی

این یک تصور غلط است که کامپیوترهای کوانتوم NTM می‌باشند. این باور شده ‌است اما هنوز اثبات نشده‌است که قدرت کامپیوترهای کوانتوم قابل مقایسه با NTMهاست. مسئله‌ای وجود دارد که NTM به‌طور مؤثر می‌تواند حلش کند اما کامپیوتر کوانتوم نمی‌تواند. از مسائل قابل حل با NTM اما غیرقابل حل با کامپیوترهای کوانتوم در زمان چندجمله‌ای مسائل NP-complete می‌باشند.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Non-deterministic Turing machine». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۸ دی ۱۳۹۳.