موضوع مقاله: ماشین تورینگ غیرقطعی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ماشین تورینگ غیرقطعی | مقدمه: در علوم کامپیوتر نظری، ماشین تورینگ نظری یک ماشین است که در آزمایش‌های فکری برای آزمایش توانایی‌ها و محدودیت‌های کامپیوتر استفاده می‌شود. | ## بخش 1: ماشین تورینگ غیرقطعی | دراصل، ماشین تورینگ به صورت یک کامپیوتر ساده تصور می‌شود که با دنبال کردن مجموئه‌ای از قوانین، نمادها را در واحد زمان می‌خواند و بر روی یک نوار بی پایان می‌نویسد؛ و با توجه به وضعیت جاری نمادی که دیده است، تعیین می‌کند چه عملی باید انجام دهد. یک مثال از قوانین ماشین تورینگ: «اگر در وضعیت ۲ هستید و نماد 'A' دیدید، آن را به 'B' تغییر دهید و به چپ بروید.» در ماشین تورینگ قطعی، مجموعهٔ قوانین به ازای هر وضعیت داده شده، حداکثر یک حرکت را مجاز می‌کند. ماشین تورینگ غیرقطعی برخلاف ماشین تورینگ قطعی، دارای مجموعه قوانینی است که به ازای هر وضعیت، بیشتر از یک حرکت را مجاز می‌کند. برای مثال، ماشین تورینگ غیرقطعی ممکن است هر دو قوانین «اگر در وضعیت ۲ هستید و نماد ‘A’ دیدید، آن را به ‘B’ تغییردهید و به چپ بروید.» و «اگر در وضعیت ۲ هستید و نماد ‘A’ دیدید، آن را به ‘C’ تغییر دهید و به راست بروید» را در مجموعه قوانینش داشته باشد. ماشین تورینگ معمولی (قطعی - DTM) دارای تابع انتقال است که برای وضعیت داده شده و نمادی که روی نوار به آن اشاره می‌شود، ۳ چیز را مشخص می‌کند: نمادی که باید روی نوار نوشته شود، جهت حرکت هد (چپ، راست یا هیچکدام) و وضعیت بعدی ... برای مثال، X روی نوار در وضعیت ۳ ممکن است DTM را وادار به نوشتن Y روی نوار، حرکت هد به راست و انتقال به وضعیت ۵ کند. تفاوت ماشین تورینگ غیرقطعی (NTM) این است که وضعیت داده شده و نماد روی نوار ۳چیز منحصربه فرد را مشخص نمی‌کند، بلکه برای ترکیب مشابه از وضعیت و نماد ممکن است انتقال‌های متفاوتی انجام شود. برای مثال، X روی نوار در وضعیت۳ ممکن است به ماشین اجازه دهد Y را روی نوار بنویسد، به راست برود و به وضعیت ۵ برود یا X را بنویسد، به چپ برود و در وضعیت ۳ بماند. تعاریف ماشین تورینگ غیرقطعی به‌طور رسمی یک ۶-تایی است به طوریکه: مجموعه متناهی از وضعیت‌ها مجموعهٔ متناهی از الفبای ورودی وضعیت شروع نماد خالی مجموعه حالت‌های پذیرش ارتباط بین وضعیت‌ها و نمادها که رابطهٔ انتقال نامیده می‌شود. تفاوت بین ماشین تورینگ استاندارد (قطعی) و غیرقطعی این است که در قطعی رابطه انتقال تابع است (تابع انتقال). | ## بخش 2: ماشین تورینگ غیرقطعی | حالت‌ها و عملکرد رابطه روی حالت‌ها که انتقال‌های ممکن تورینگ ماشین با اجزای ممکن نوار را توصیف می‌کند، مانند ماشین تورینگ استاندار است بجزاینکه حاصل رابطه دیگر یک مقدار تنها نیست. مفهوم پذیرش رشته بدون تغییر است: ماشین تورینگ غیرقطعی یک رشته را می‌پذیرد اگر، زمانی که ماشین شروع به کار می‌کند هد روی اولین کاراکتر رشته و در غیراینصورت کل نوار خالی باشد. حداقل یکی از محاسبات ماشین ماشین را از آن حالت در وضعیت قرار می‌دهد (اگر ماشین قطعی باشد، محاسبات ممکن، پیشوندی از یک، واحتمالا نامحدود مسیر می‌باشد) حل قوانین متعدد چگونه NTM تشخیص می‌دهد کدام حرکت را باید انجام دهد؟ اولی اینکه بگوییم «ماشین خوش شانس ترین حدس زنندهٔ ممکن است»؛ همیشه انتقالی را انتخاب می‌کند که به وضعیت پذیرش می‌رود (اگرچنین انتقالی موجود باشد). راه دیگر تصور این است که ماشین به چند کپی از خودش تقسیم می‌شود که هرکدام یکی از حرکت‌های ممکن را دنبال می‌کند. اگر حداقل یکی از شاخه‌های درخت به وضعیت پذیرش برود، می‌گوییم NTM ورودی را پذیرفته است. هم‌ارزی DTMها به‌طور ویژه ماشین‌های تورینگ غیرقطعی با ماشین‌های تورینگ قطعی هم‌ارزند. ممکن است به نظر برسد که NTMها از DTMها قدرتمندترند، زیرا آن‌ها یک درخت از محاسبات ممکن را ناشی از حالت مشابه ممکن می‌سازند و رشته را اگر هر یک از شاخه‌های درخت پذیرشش کند، می‌پذیرند. اما شبیه‌سازی NTMها با DTMها امکان‌پذیراست: روش اول استفاده از DTM است به طوریکه هر حالت نشان دهندهٔ چند حالت در NTM است وعملیات DTM شامل مراجعه به هر کدام به نوبهٔ خود، انجام یک مرحله در هر مراجعه و جابه‌جایی به حالت جدید هرگاه رابطه انتقال چند حالت را تعریف کند، می‌باشد. روش دیگر شبیه‌سازی NTM، استفاده از DTM با ۳ نواراست؛ که نوار اول همیشه ورودی اولیه را نگهداری می‌کند، نوار دوم محاسبات مشخص NTM را شبیه‌سازی می‌کند و نوار سوم مسیر را در درخت محاسبات NTM کدگذاری می‌کند. | ## بخش 3: ماشین تورینگ غیرقطعی | در این روش ساخت، ِDTM حاصل جستجوی اول سطحی از درخت محاسبات NTM را انجام می‌دهد؛ و همهٔ حالات ممکن را می‌بیند تا وقتی که یک کدام را پذیرش کند. بنابراین، طول مسیرپذیرش در DTM نمایی است با توجه به طول کوتاهترین مسیر پذیرش درNTM. مثلاً اگر NTM با ورودی نوار داده شده متوقف شود آنگاه روی تعداد مراحل محدودی متوقف شده بنابراین تنها می‌تواند تعداد محدودی حالت ممکن داشته باشد. مقایسه با کامپیوترهای کوانتوم این یک تصور غلط است که کامپیوترهای کوانتوم NTM می‌باشند. این باورشده‌است اما هنوز اثبات نشده‌است که قدرت کامپیوترهای کوانتوم قابل مقایسه با NTMهاست. مسئله‌ای وجود دارد که NTM به‌طور مؤثر می‌تواند حلش کند اما کامپیوتر کوانتوم نمی‌تواند. مثلاً اگر NTM با ورودی نوار داده شده متوقف شود آنگاه روی تعداد مراحل محدودی متوقف شده بنابراین تنها می‌تواند تعداد محدودی حالت ممکن داشته باشد. مقایسه با کامپیوترهای کوانتومی این یک تصور غلط است که کامپیوترهای کوانتوم NTM می‌باشند. این باور شده ‌است اما هنوز اثبات نشده‌است که قدرت کامپیوترهای کوانتوم قابل مقایسه با NTMهاست. | ## جمع‌بندی | مسئله‌ای وجود دارد که NTM به‌طور مؤثر می‌تواند حلش کند اما کامپیوتر کوانتوم نمی‌تواند.