موضوع مقاله: ماشین تورینگ متناوب | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ماشین تورینگ متناوب | مقدمه: در نظریه پیچیدگی محاسباتی، یک ماشین تورینگ متناوب ، ماشین تورینگی غیر قطعی است و شامل قانونی برای پذیرش محاسباتی است که قوانین استفاده شده در تعریف کلاس‌های پیچیدگی NP و co-NP را کلیت می‌بخشد. | ## بخش 1: ماشین تورینگ متناوب | تعاریف توضیحات غیر رسمی تعریفNPاز حالت وجودی محاسبات استفاده می‌کند: اگر انتخابی منجر به حالت پذیرش شود، در این صورت همهٔ محاسبات پذیرفته می‌شوند. تعریف CO-NP از حالت عمومی محاسبات استفاده می‌کند: اگر همهٔ انتخاب‌ها منجر به حالت پذیرش شوند، در این صورت تمام محاسبات پذیرفته می‌شوند. ماشین تورینگ متقارن (به‌طور دقیق تر، تعریف نحوه پذیرش این ماشین) بین این ۲ حالت در تناوب است. ماشین تورینگ متقارن ماشین تورینگی غیر قطعی است که حالاتش به ۲ قسمت تقسیم می‌شوند: حالات وجودی و حالات عمومی. یک حالت وجودی پذیرفته می‌شود اگر انتقالی وجود داشته باشد که منجر به یک حالت پذیرش شود. یک حالت عمومی پذیرفته می‌شود اگر همهٔ انتقال‌ها به حالت پذیرش ختم شوند .(حالت عمومی بدون انتقال، به‌طور پیش فرض پذیرفته و حالت وجودی بدون انتقال به‌طور پیش فرض رد می‌شود). تعریف علمی ماشین تورینگ متقارن یک ۵ تایی به صورتاست که: مجموعه متناهی از حالت است. تابع انتقال نام دارد (L کلاهک را به سمت چپ و R کلاهک را به سمت راست می‌برد) حالت اولیه است. اگرM در وضعیت Q با باشد، در این صورت این موقعیت، موقعیتی پذیرفتنی است و اگر ، موقعیتی پذیرفتنی نیست. | ## بخش 2: ماشین تورینگ متناوب | موقعیتی با پذیرفتنی است اگر همهٔ موقعیت‌هایی که با یک گام می‌توان به آن‌ها دست یافت پذیرفتنی باشند و غیر پذیرفتنی است اگر بعضی از موقعیت‌هایی که با یک گام قابل دسترسی هستند غیر پذیرفتنی باشند. موقعیتی با موقعیتی پذیرفتنی است اگر موقعیتی پذیرفتنی وجود داشته باشد که با یک گام بتوان به آن دست یافت و غیر پذیرفتنی است اگر تمام موقعیت‌هایی که بتوان طی یک گام به آنها دست یافت، غیر پذیرفتنی باشند. ماشین M رشتهٔ W را در صورتی می‌پذیرد که موقعیت اولیه آن پذیرفتنی باشد و در صورتی آن را رد می‌کند که موقعیت اولیه آن پذیرفتنی نباشد. به‌طور کلی یک موقعیت وجودی در صورتی پذیرفتنی است که هر موقعیتی جانشین آن پذیرفتنی باشد و یک موقعیت عمومی در صورتی پذیرفتنی نیست که هر موقعیتی جانشین آن، پذیرفتنی نباشد. ماشین تورینگ متقارن زبان‌های صوری (فرمال) را در مرتبهٔ زمانی پردازش می‌کند اگر به ازای هر رشته به طول ، تعیین پذیرفتنی بودن یا نبودن موقعیت اولی با حد اکثر با گام امکان‌پذیر باشد ماشین تورینگ متقارن، زبان را در مرتبهٔ حافظهٔ پردازش می‌کند اگر تنها بررسی موقعیت‌هایی که تا خانه از سمت چپ را تغییر نمی‌دهند، کافی باشد. زبانی که توسط ATM در مرتبهٔ زمانی (به ازای ) بررسی می‌شود در کلاس و زبانی که در مرتبهٔ حافظه‌ای بررسی می‌شود در کلاس قرار دارد. ATM برای بررسی تمام مقادیر متغیرهای وجودی (از چپ به راست) به صورت وجودی و برای بررسی تمام مقادیر متغیرهای عمومی (از چپ به راست) به صورت عمومی منشعب می‌شود. بنابر این اگر مقداری جایگزین برای متغیر وجودی، موجود باشد که ادامه مسئله سازگار بماند، یا به ازای تمام مقادیر جایگزین برای متغیر عمومی، ادامه مسئله سازگار باقی بماند، ماشین در شرایط پذیرش قرار می‌گیرد. کلاس‌های پیچیدگی و مقایسه با ماشین تورینگ قطعی کلاس‌های پیچیدگی زیر برای تعریف ماشین تورینگ متناوب مورد استفاده قرار می‌گیرند: زبان‌هایی هستند که در مرتبهٔ زمانی چند جمله‌ای بررسی می‌شوند. | ## بخش 3: ماشین تورینگ متناوب | تناوب محدود تعریف ماشین تورینگ متناوب با K تناوب، ماشین تورینگی متناوب است که حد اکثر K-1 دفعه می‌تواند بین حالت عمومی و حالت وجودی جابجا شود .(در واقع ماشین تورینگی است که حالت‌هایش به K مجموعه تقسیم شده‌اند. حالت‌های با شمارهٔ فرد حالت‌های عمومی و حالت‌های با شماره زوج حالت‌های وجودی در نظر گرفته می‌شوند (عکس آن هم درست است). ماشین هیچ انتقالی از حالت i به j، که j<i، ندارد) کلاس توابعی است که که در زمان ، از یک حالت وجودی شروع می‌شوند و حد اکثر j-1 بر تناوب می‌کنند و به آن j-امین سطح از سلسله مراتب هم گفته می‌شود کلاسی مشابه با کلاس قبلی است با این تفاوت که از یک حالت عمومی شروع می‌شود و متمم زبان است. مدار A که یک تابع بولی F را محاسبه می‌کند، به همراه عدد N به عنوان ورودی داده می‌شوند. برای خروجی، وجود یا عدم وجود مداری که با K گیت بتواند تابع F را پیاده‌سازی کند، بررسی می‌شود. ماشین تورینگ متناوبی که یک تناوب دارد و از حالتی وجودی آغاز به کار می‌کند می‌تواند این مسئله را در مرتبهٔ زمانی چند جمله‌ای حل کند.(این کار با آزمایش مدارهای احتمالی با K گیت و مقایسه خروجی آنها با مدار اصلی انجام می‌شود). پایین آمدن مرتبهٔ کلاس‌ها یک سلسله مرتبه هنگامی به مرتبهٔ J کاهش پیدا می‌کند که تمام زبان‌های مرتبهٔ K، در مرتبهٔ J موجود باشند. | ## جمع‌بندی | حالت‌های خاص ماشین تورینگ متناوب با مرتبهٔ زمانی چند جمله‌ای و K تناوب، با شروع از یک حالت وجودی (عمومی) می‌تواند تمام مسائل کلاس را بررسی کند.