ماشین تورینگ متناوب
در نظریه پیچیدگی محاسباتی، یک ماشین تورینگ متناوب ، ماشین تورینگی غیر قطعی است و شامل قانونی برای پذیرش محاسباتی است که قوانین استفاده شده در تعریف کلاس‌های پیچیدگی NP و co-NP را کلیت می‌بخشد. مفهوم ATM توسط Chandra و Stockmeyer و مستقلاً توسط Kozen در سال ۱۹۷۶، و سپس به صورت مشترک، باانتشار در یک مجله در سال ۱۹۸۱ مطرح شد.
تعریفNPاز حالت وجودی محاسبات استفاده می‌کند: اگر انتخابی منجر به حالت پذیرش شود، در این صورت همهٔ محاسبات پذیرفته می‌شوند. تعریف CO-NP از حالت عمومی محاسبات استفاده می‌کند: اگر همهٔ انتخاب‌ها منجر به حالت پذیرش شوند، در این صورت تمام محاسبات پذیرفته می‌شوند. ماشین تورینگ متقارن (به‌طور دقیق تر، تعریف نحوه پذیرش این ماشین) بین این ۲ حالت در تناوب است. ماشین تورینگ متقارن ماشین تورینگی غیر قطعی است که حالاتش به ۲ قسمت تقسیم می‌شوند: حالات وجودی و حالات عمومی. یک حالت وجودی پذیرفته می‌شود اگر انتقالی وجود داشته باشد که منجر به یک حالت پذیرش شود. یک حالت عمومی پذیرفته می‌شود اگر همهٔ انتقال‌ها به حالت پذیرش ختم شوند .(حالت عمومی بدون انتقال، به‌طور پیش فرض پذیرفته و حالت وجودی بدون انتقال به‌طور پیش فرض رد می‌شود). ماشین (به صورت یک واحد) پذیرفته می‌شود اگر حالت اول آن پذیرفته شود.
ماشین تورینگ متقارن یک ۵ تایی به صورتformula_1است که:
اگرM در وضعیت Q با formula_7 باشد، در این صورت این موقعیت، موقعیتی پذیرفتنی است و اگر formula_8، موقعیتی پذیرفتنی نیست.
موقعیتی با formula_9 پذیرفتنی است اگر همهٔ موقعیت‌هایی که با یک گام می‌توان به آن‌ها دست یافت پذیرفتنی باشند و غیر پذیرفتنی است اگر بعضی از موقعیت‌هایی که با یک گام قابل دسترسی هستند غیر پذیرفتنی باشند.
موقعیتی با formula_10 موقعیتی پذیرفتنی است اگر موقعیتی پذیرفتنی وجود داشته باشد که با یک گام بتوان به آن دست یافت و غیر پذیرفتنی است اگر تمام موقعیت‌هایی که بتوان طی یک گام به آنها دست یافت، غیر پذیرفتنی باشند. ماشین M رشتهٔ W را در صورتی می‌پذیرد که موقعیت اولیه آن پذیرفتنی باشد و در صورتی آن را رد می‌کند که موقعیت اولیه آن پذیرفتنی نباشد.
هنگامی که می‌خوایم پذیرفتنی بودن یا نبودن یک موقعیت از ماشین ATM را طبق تعریف بالا بررسی کنیم، احتیاجی به بررسی تمام حالت‌های دست یافتنی نیست. به‌طور کلی یک موقعیت وجودی در صورتی پذیرفتنی است که هر موقعیتی جانشین آن پذیرفتنی باشد و یک موقعیت عمومی در صورتی پذیرفتنی نیست که هر موقعیتی جانشین آن، پذیرفتنی نباشد.
ماشین تورینگ متقارن زبان‌های صوری (فرمال) را در مرتبهٔ زمانی formula_11 پردازش می‌کند اگر به ازای هر رشته به طول formula_12، تعیین پذیرفتنی بودن یا نبودن موقعیت اولی با حد اکثر با formula_11 گام امکان‌پذیر باشد
ماشین تورینگ متقارن، زبان را در مرتبهٔ حافظهٔ formula_14 پردازش می‌کند اگر تنها بررسی موقعیت‌هایی که تا formula_14 خانه از سمت چپ را تغییر نمی‌دهند، کافی باشد.
زبانی که توسط ATM در مرتبهٔ زمانی formula_16 (به ازای formula_17) بررسی می‌شود در کلاس formula_18 و زبانی که در مرتبهٔ حافظه‌ای formula_19 بررسی می‌شود در کلاس formula_20 قرار دارد.
احتمالاً آسان‌ترین مسئلهٔ قابل حل برای ATM، مسئلهٔ quantified Boolean formula problem است. این مسئله تعمیم یافتهٔ مسئلهٔ Boolean satisfiability problem که در آن هر متغیر می‌تواند به یک کمیت عمومی یا وجودی محدود شود.
ATM برای بررسی تمام مقادیر متغیرهای وجودی (از چپ به راست) به صورت وجودی و برای بررسی تمام مقادیر متغیرهای عمومی (از چپ به راست) به صورت عمومی منشعب می‌شود. پس از بررسی یک مقدار برای تمامی متغیرها، اگر نتیجه Boolean formula برابر true باشد ماشین آن را پذیرش و اگر false باشد ماشین آن را نمی‌پذیرد.
بنابر این اگر مقداری جایگزین برای متغیر وجودی، موجود باشد که ادامه مسئله سازگار بماند، یا به ازای تمام مقادیر جایگزین برای متغیر عمومی، ادامه مسئله سازگار باقی بماند، ماشین در شرایط پذیرش قرار می‌گیرد.
این ماشین quantified Boolean formulas را در مرتبهٔ زمانی formula_21 و مرتبهٔ حافظه formula_12 بررسی می‌کند.
Boolean satisfiability می‌تواند به عنوان حالت خاصی در نظر گرفته شود که در آن تمام متغیرها به صورت وجودی بین شده و فقط از انشعاب به صورت وجودی استفاده برای حل کارایی استفاده می‌شود. در این حالت استفاده از عدم قطعیت مجاز است.
کلاس‌های پیچیدگی زیر برای تعریف ماشین تورینگ متناوب مورد استفاده قرار می‌گیرند:
این کلاس‌ها، با در نظر گرفتن منابعی که یک ATM به جای ماشین تورینگ قطعی استفاده می‌کند، شبیه به تعریف‌های P و PSPACE و EXPTIME هستند.
Chandra, Kozen, و Stockmeyer قضایای زیر را در شرایطی که formula_26 و formula_27 ثابت کرده‌اند.
شکل کلی تر این روابط توسط تز پردازش موازی، نشان داده می‌شود.
ماشین تورینگ متناوب با K تناوب، ماشین تورینگی متناوب است که حد اکثر K-1 دفعه می‌تواند بین حالت عمومی و حالت وجودی جابجا شود .(در واقع ماشین تورینگی است که حالت‌هایش به K مجموعه تقسیم شده‌اند. حالت‌های با شمارهٔ فرد حالت‌های عمومی و حالت‌های با شماره زوج حالت‌های وجودی در نظر گرفته می‌شوند (عکس آن هم درست است). ماشین هیچ انتقالی از حالت i به j، که j{\rm ATIME}(C,j)=\Sigma_j {\rm TIME}(C) کلاس توابعی است که که در زمان formula_31، از یک حالت وجودی شروع می‌شوند و حد اکثر j-1 بر تناوب می‌کنند و به آن j-امین سطح از سلسله مراتب formula_32 هم گفته می‌شود
formula_35 به صورت مشابه برای محاسبات با حافظهٔ محدود تعریف می‌شود.
مسئلهٔ circuit minimization problem را در نظر بگیرید. مدار A که یک تابع بولی F را محاسبه می‌کند، به همراه عدد N به عنوان ورودی داده می‌شوند.
برای خروجی، وجود یا عدم وجود مداری که با K گیت بتواند تابع F را پیاده‌سازی کند، بررسی می‌شود.
ماشین تورینگ متناوبی که یک تناوب دارد و از حالتی وجودی آغاز به کار می‌کند می‌تواند این مسئله را در مرتبهٔ زمانی چند جمله‌ای حل کند.(این کار با آزمایش مدارهای احتمالی با K گیت و مقایسه خروجی آنها با مدار اصلی انجام می‌شود).
یک سلسله مرتبه هنگامی به مرتبهٔ J کاهش پیدا می‌کند که تمام زبان‌های مرتبهٔ K، در مرتبهٔ J موجود باشند. به عنوان نتیجه‌ای از قضیه Immerman–Szelepcsényi theorem، سلسله مراتب حافظه لگاریتمی، به اولین سطح آن کاهش می‌یابد.
ماشین تورینگ متناوب با مرتبهٔ زمانی چند جمله‌ای و K تناوب، با شروع از یک حالت وجودی (عمومی) می‌تواند تمام مسائل کلاس formula_36(formula_37) را بررسی کند. از این کلاس‌ها اغلب به صورتformula_38(formula_39) در مسائل یاد می‌شود.
نمونهٔ دیگری از حالات خاص سلسله مراتب زمانی، logarithmic hierarchy است.