در نظریه پیچیدگی محاسباتی، یک ماشین تورینگ متناوب (به انگلیسی: Alternating Turing machine) (مخفف انگلیسی: ATM)، ماشین تورینگی غیر قطعی است و شامل قانونی برای پذیرش محاسباتی است که قوانین استفاده شده در تعریف کلاس های پیچیدگی NP و co-NP را کلیت می بخشد.مفهوم ATM توسط Chandra و Stockmeyer و مستقلاً توسط Kozen در سال ۱۹۷۶، و سپس به صورت مشترک، باانتشار در یک مجله در سال ۱۹۸۱ مطرح شد.
Q {\displaystyle Q} مجموعه متناهی از حالت است.
Γ {\displaystyle \Gamma } مجموعه متناهی الفبای نوار است.
δ : Q × Γ → P ( Q × Γ × { L , R } ) {\displaystyle \delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})} تابع انتقال نام دارد (L کلاهک را به سمت چپ و R کلاهک را به سمت راست می برد)
q 0 ∈ Q {\displaystyle q_{0}\in Q} حالت اولیه است.
g : Q → { ∧ , ∨ , a c c e p t , r e j e c t } {\displaystyle g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}} نوع هر حالت را مشخص می کند.
تعریفNPاز حالت وجودی محاسبات استفاده می کند: اگر انتخابی منجر به حالت پذیرش شود، در این صورت همهٔ محاسبات پزیرفته می شوند. تعریف CO-NP از حالت عمومی محاسبات استفاده می کند: اگر همهٔ انتخاب ها منجر به حالت پذیرش شوند، در این صورت تمام محاسبات پذیرفته می شوند. ماشین تورینگ متقارن (به طور دقیق تر، تعریف نحوه پذیرش این ماشین) بین این ۲ حالت در تناوب است.ماشین تورینگ متقارن ماشین تورینگی غیر قطعی است که حالاتش به ۲ قسمت تقسیم می شوند: حالات وجودی و حالات عمومی.یک حالت وجودی پذیرفته می شود اگر انتقالی وجود داشته باشد که منجر به یک حالت پذیرش شود. یک حالت عمومی پذیرفته می شود اگر همهٔ انتقال ها به حالت پذیرش ختم شوند .(حالت عمومی بدون انتقال، به طور پیش فرض پذیرفته و حالت وجودی بدون انتقال به طور پیش فرض رد می شود). ماشین (به صورت یک واحد) پذیرفته می شود اگر حالت اول آن پذیرفته شود.
ماشین تورینگ متقارن یک ۵ تایی به صورت M = ( Q , Γ , δ , q 0 , g ) {\displaystyle M=(Q,\Gamma ,\delta ,q_{0},g)} است که:
اگرM در وضعیت Q با g ( q ) = a c c e p t {\displaystyle g(q)=accept} باشد، در این صورت این موقعیت، موقعیتی پذیرفتنی است و اگر g ( q ) = r e j e c t {\displaystyle g(q)=reject} ، موقعیتی پذیرفتنی نیست.
Q {\displaystyle Q} مجموعه متناهی از حالت است.
Γ {\displaystyle \Gamma } مجموعه متناهی الفبای نوار است.
δ : Q × Γ → P ( Q × Γ × { L , R } ) {\displaystyle \delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})} تابع انتقال نام دارد (L کلاهک را به سمت چپ و R کلاهک را به سمت راست می برد)
q 0 ∈ Q {\displaystyle q_{0}\in Q} حالت اولیه است.
g : Q → { ∧ , ∨ , a c c e p t , r e j e c t } {\displaystyle g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}} نوع هر حالت را مشخص می کند.
تعریفNPاز حالت وجودی محاسبات استفاده می کند: اگر انتخابی منجر به حالت پذیرش شود، در این صورت همهٔ محاسبات پزیرفته می شوند. تعریف CO-NP از حالت عمومی محاسبات استفاده می کند: اگر همهٔ انتخاب ها منجر به حالت پذیرش شوند، در این صورت تمام محاسبات پذیرفته می شوند. ماشین تورینگ متقارن (به طور دقیق تر، تعریف نحوه پذیرش این ماشین) بین این ۲ حالت در تناوب است.ماشین تورینگ متقارن ماشین تورینگی غیر قطعی است که حالاتش به ۲ قسمت تقسیم می شوند: حالات وجودی و حالات عمومی.یک حالت وجودی پذیرفته می شود اگر انتقالی وجود داشته باشد که منجر به یک حالت پذیرش شود. یک حالت عمومی پذیرفته می شود اگر همهٔ انتقال ها به حالت پذیرش ختم شوند .(حالت عمومی بدون انتقال، به طور پیش فرض پذیرفته و حالت وجودی بدون انتقال به طور پیش فرض رد می شود). ماشین (به صورت یک واحد) پذیرفته می شود اگر حالت اول آن پذیرفته شود.
ماشین تورینگ متقارن یک ۵ تایی به صورت M = ( Q , Γ , δ , q 0 , g ) {\displaystyle M=(Q,\Gamma ,\delta ,q_{0},g)} است که:
اگرM در وضعیت Q با g ( q ) = a c c e p t {\displaystyle g(q)=accept} باشد، در این صورت این موقعیت، موقعیتی پذیرفتنی است و اگر g ( q ) = r e j e c t {\displaystyle g(q)=reject} ، موقعیتی پذیرفتنی نیست.
wiki: ماشین تورینگ متناوب