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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در نظریه پیچیدگی محاسباتی، یک ماشین تورینگ متناوب (به انگلیسی: Alternating Turing machine) (مخفف انگلیسی: ATM)، ماشین تورینگی غیر قطعی است و شامل قانونی برای پذیرش محاسباتی است که قوانین استفاده شده در تعریف کلاس‌های پیچیدگی NP و co-NP را کلیت می‌بخشد. مفهوم ATM توسط Chandra و Stockmeyer[۱] و مستقلاً توسط Kozen[۲] در سال ۱۹۷۶، و سپس به صورت مشترک، باانتشار در یک مجله در سال ۱۹۸۱ مطرح شد.[۳]

تعاریف[ویرایش]

توضیحات غیر رسمی[ویرایش]

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

تعریف علمی[ویرایش]

ماشین تورینگ متقارن یک ۵ تایی به صورتاست که:

  • مجموعه متناهی از حالت است.
  • مجموعه متناهی الفبای نوار است.
  • تابع انتقال نام دارد (L کلاهک را به سمت چپ و R کلاهک را به سمت راست می‌برد)
  • حالت اولیه است.
  • نوع هر حالت را مشخص می‌کند.

اگرM در وضعیت Q با باشد، در این صورت این موقعیت، موقعیتی پذیرفتنی است و اگر ، موقعیتی پذیرفتنی نیست.

موقعیتی با پذیرفتنی است اگر همهٔ موقعیت‌هایی که با یک گام می‌توان به آن‌ها دست یافت پذیرفتنی باشند و غیر پذیرفتنی است اگر بعضی از موقعیت‌هایی که با یک گام قابل دسترسی هستند غیر پذیرفتنی باشند.

موقعیتی با موقعیتی پذیرفتنی است اگر موقعیتی پذیرفتنی وجود داشته باشد که با یک گام بتوان به آن دست یافت و غیر پذیرفتنی است اگر تمام موقعیت‌هایی که بتوان طی یک گام به آنها دست یافت، غیر پذیرفتنی باشند. ماشین M رشتهٔ W را در صورتی می‌پذیرد که موقعیت اولیه آن پذیرفتنی باشد و در صورتی آن را رد می‌کند که موقعیت اولیه آن پذیرفتنی نباشد.

محدودیت‌های منابع[ویرایش]

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

ماشین تورینگ متقارن زبان‌های صوری (فرمال) را در مرتبهٔ زمانی پردازش می‌کند اگر به ازای هر رشته به طول ، تعیین پذیرفتنی بودن یا نبودن موقعیت اولی با حد اکثر با گام امکان‌پذیر باشد

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

زبانی که توسط ATM در مرتبهٔ زمانی (به ازای ) بررسی می‌شود در کلاس و زبانی که در مرتبهٔ حافظه‌ای بررسی می‌شود در کلاس قرار دارد.

مثال[ویرایش]

احتمالاً آسان‌ترین مسئلهٔ قابل حل برای ATM، مسئلهٔ quantified Boolean formula problem است. این مسئله تعمیم یافتهٔ مسئلهٔ Boolean satisfiability problem که در آن هر متغیر می‌تواند به یک کمیت عمومی یا وجودی محدود شود.

ATM برای بررسی تمام مقادیر متغیرهای وجودی (از چپ به راست) به صورت وجودی و برای بررسی تمام مقادیر متغیرهای عمومی (از چپ به راست) به صورت عمومی منشعب می‌شود. پس از بررسی یک مقدار برای تمامی متغیرها، اگر نتیجه Boolean formula برابر true باشد ماشین آن را پذیرش و اگر false باشد ماشین آن را نمی‌پذیرد.

بنابر این اگر مقداری جایگزین برای متغیر وجودی، موجود باشد که ادامه مسئله سازگار بماند، یا به ازای تمام مقادیر جایگزین برای متغیر عمومی، ادامه مسئله سازگار باقی بماند، ماشین در شرایط پذیرش قرار می‌گیرد.

این ماشین quantified Boolean formulas را در مرتبهٔ زمانی و مرتبهٔ حافظه بررسی می‌کند.

Boolean satisfiability می‌تواند به عنوان حالت خاصی در نظر گرفته شود که در آن تمام متغیرها به صورت وجودی بین شده و فقط از انشعاب به صورت وجودی استفاده برای حل کارایی استفاده می‌شود. در این حالت استفاده از عدم قطعیت مجاز است.

کلاس‌های پیچیدگی و مقایسه با ماشین تورینگ قطعی[ویرایش]

کلاس‌های پیچیدگی زیر برای تعریف ماشین تورینگ متناوب مورد استفاده قرار می‌گیرند:

  • زبان‌هایی هستند که در مرتبهٔ زمانی چند جمله‌ای بررسی می‌شوند.
  • زبان‌هایی هستند که در مرتبهٔ حافظه‌ای چند جمله‌ای بررسی می‌شوند.
  • زبان‌هایی هستند که در مرتبهٔ زمانی نمائی بررسی می‌شوند.

این کلاس‌ها، با در نظر گرفتن منابعی که یک ATM به جای ماشین تورینگ قطعی استفاده می‌کند، شبیه به تعریف‌های P و PSPACE و EXPTIME هستند.

Chandra, Kozen, و Stockmeyer[۳] قضایای زیر را در شرایطی که و ثابت کرده‌اند.

  • AP = PSPACE
  • APSPACE = EXPTIME
  • AEXPTIME = EXPSPACE

شکل کلی تر این روابط توسط تز پردازش موازی، نشان داده می‌شود.

تناوب محدود[ویرایش]

تعریف[ویرایش]

ماشین تورینگ متناوب با K تناوب، ماشین تورینگی متناوب است که حد اکثر K-1 دفعه می‌تواند بین حالت عمومی و حالت وجودی جابجا شود .(در واقع ماشین تورینگی است که حالت‌هایش به K مجموعه تقسیم شده‌اند. حالت‌های با شمارهٔ فرد حالت‌های عمومی و حالت‌های با شماره زوج حالت‌های وجودی در نظر گرفته می‌شوند (عکس آن هم درست است). ماشین هیچ انتقالی از حالت i به j، که j<i، ندارد)

  • کلاس توابعی است که که در زمان ، از یک حالت وجودی شروع می‌شوند و حد اکثر j-1 بر تناوب می‌کنند و به آن j-امین سطح از سلسله مراتب هم گفته می‌شود
  • کلاسی مشابه با کلاس قبلی است با این تفاوت که از یک حالت عمومی شروع می‌شود و متمم زبان است.

به صورت مشابه برای محاسبات با حافظهٔ محدود تعریف می‌شود.

مثال[ویرایش]

مسئلهٔ circuit minimization problem را در نظر بگیرید. مدار A که یک تابع بولی F را محاسبه می‌کند، به همراه عدد N به عنوان ورودی داده می‌شوند.

برای خروجی، وجود یا عدم وجود مداری که با K گیت بتواند تابع F را پیاده‌سازی کند، بررسی می‌شود.

ماشین تورینگ متناوبی که یک تناوب دارد و از حالتی وجودی آغاز به کار می‌کند می‌تواند این مسئله را در مرتبهٔ زمانی چند جمله‌ای حل کند.(این کار با آزمایش مدارهای احتمالی با K گیت و مقایسه خروجی آنها با مدار اصلی انجام می‌شود).

پایین آمدن مرتبهٔ کلاس‌ها[ویرایش]

یک سلسله مرتبه هنگامی به مرتبهٔ J کاهش پیدا می‌کند که تمام زبان‌های مرتبهٔ K، در مرتبهٔ J موجود باشند. به عنوان نتیجه‌ای از قضیه Immerman–Szelepcsényi theorem، سلسله مراتب حافظه لگاریتهمی، به اولین سطح آن کاهش می‌یابد.

حالت‌های خاص[ویرایش]

ماشین تورینگ متناوب با مرتبهٔ زمانی چند جمله‌ای و K تناوب، با شروع از یک حالت وجودی (عمومی) می‌تواند تمام مسائل کلاس () را بررسی کند.[۴] از این کلاس‌ها اغلب به صورت() در مسائل یاد می‌شود.

نمونهٔ دیگری از حالات خاص سلسله مراتب زمانی، logarithmic hierarchy است.

پانویس[ویرایش]

  1. Chandra, Ashok K.; Stockmeyer, Larry J. (1976). "Alternation". Proc. 17th IEEE Symp. on Foundations of Computer Science. Houston, Texas. pp. 98–108. doi:10.1109/SFCS.1976.4. 
  2. Kozen, D. (1976). "On parallelism in Turing machines". Proc. 17th IEEE Symp. on Foundations of Computer Science. Houston, Texas. pp. 89–97. doi:10.1109/SFCS.1976.20. 
  3. ۳٫۰ ۳٫۱ Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Alternation". Journal of the ACM 28 (1): 114–133. doi:10.1145/322234.322243. 
  4. Kozen, Dexter (2006). Theory of Computation. Springer-Verlag. p. 58. ISBN 9781846282973. 

منابع[ویرایش]