در علوم کامپیوتر نظری، ماشین تورینگ نظری یک ماشین است که در آزمایش های فکری برای آزمایش توانایی ها و محدودیت های کامپیوتر استفاده می شود.دراصل، ماشین تورینگ به صورت یک کامپیوتر ساده تصور می شود که با دنبال کردن مجموئه ای از قوانین، نمادها را در واحد زمان می خواند و بر روی یک نوار بی پایان می نویسد؛ و با توجه به وضعیت جاری نمادی که دیده است، تعیین می کند چه عملی باید انجام دهد. یک مثال از قوانین ماشین تورینگ: «اگر در وضعیت ۲ هستید و نماد 'A' دیدید، آن را به 'B' تغییر دهید و به چپ بروید.»
Q {\displaystyle Q} مجموعه متناهی از وضعیت ها
Σ {\displaystyle \Sigma } مجموعهٔ متناهی از الفبای ورودی
ι ∈ Q {\displaystyle \iota \in Q} وضعیت شروع
⊔ ∈ Σ {\displaystyle \sqcup \in \Sigma } نماد خالی
A ⊆ Q {\displaystyle A\subseteq Q} مجموعه حالت های پذیرش
δ ⊆ ( Q ∖ A × Σ ) × ( Q × Σ × { L , R } ) {\displaystyle \delta \subseteq \left(Q\backslash A\times \Sigma \right)\times \left(Q\times \Sigma \times \{L,R\}\right)} ارتباط بین وضعیت ها و نمادها که رابطهٔ انتقال نامیده می شود.
در ماشین تورینگ قطعی، مجموعهٔ قوانین به ازای هر وضعیت داده شده، حداکثر یک حرکت را مجاز می کند.ماشین تورینگ غیرقطعی (به انگلیسی: Non-deterministic Turing machine) برخلاف ماشین تورینگ قطعی، دارای مجموعه قوانینی است که به ازای هر وضعیت، بیشتر از یک حرکت را مجاز می کند.برای مثال، ماشین تورینگ غیرقطعی ممکن است هر دو قوانین «اگر در وضعیت ۲ هستید و نماد ‘A’ دیدید، آن را به ‘B’ تغییردهید و به چپ بروید.» و «اگر در وضعیت ۲ هستید و نماد ‘A’ دیدید، آن را به ‘C’ تغییر دهید و به راست بروید» را در مجموعه قوانینش داشته باشد.
ماشین تورینگ معمولی (قطعی - DTM) دارای تابع انتقال است که برای وضعیت داده شده و نمادی که روی نوار به آن اشاره می شود، ۳ چیز را مشخص می کند: نمادی که باید روی نوار نوشته شود، جهت حرکت هد (چپ، راست یا هیچکدام) و وضعیت بعدی ...
برای مثال، X روی نوار در وضعیت ۳ ممکن است DTM را وادار به نوشتن Y روی نوار، حرکت هد به راست و انتقال به وضعیت ۵ کند.تفاوت ماشین تورینگ غیرقطعی (NTM) این است که وضعیت داده شده و نماد روی نوار ۳چیز منحصربه فرد را مشخص نمی کند، بلکه برای ترکیب مشابه از وضعیت و نماد ممکن است انتقال های متفاوتی انجام شود. برای مثال، X روی نوار در وضعیت۳ ممکن است به ماشین اجازه دهد Y را روی نوار بنویسد، به راست برود و به وضعیت ۵ برود یا X را بنویسد، به چپ برود و در وضعیت ۳ بماند.
Q {\displaystyle Q} مجموعه متناهی از وضعیت ها
Σ {\displaystyle \Sigma } مجموعهٔ متناهی از الفبای ورودی
ι ∈ Q {\displaystyle \iota \in Q} وضعیت شروع
⊔ ∈ Σ {\displaystyle \sqcup \in \Sigma } نماد خالی
A ⊆ Q {\displaystyle A\subseteq Q} مجموعه حالت های پذیرش
δ ⊆ ( Q ∖ A × Σ ) × ( Q × Σ × { L , R } ) {\displaystyle \delta \subseteq \left(Q\backslash A\times \Sigma \right)\times \left(Q\times \Sigma \times \{L,R\}\right)} ارتباط بین وضعیت ها و نمادها که رابطهٔ انتقال نامیده می شود.
در ماشین تورینگ قطعی، مجموعهٔ قوانین به ازای هر وضعیت داده شده، حداکثر یک حرکت را مجاز می کند.ماشین تورینگ غیرقطعی (به انگلیسی: Non-deterministic Turing machine) برخلاف ماشین تورینگ قطعی، دارای مجموعه قوانینی است که به ازای هر وضعیت، بیشتر از یک حرکت را مجاز می کند.برای مثال، ماشین تورینگ غیرقطعی ممکن است هر دو قوانین «اگر در وضعیت ۲ هستید و نماد ‘A’ دیدید، آن را به ‘B’ تغییردهید و به چپ بروید.» و «اگر در وضعیت ۲ هستید و نماد ‘A’ دیدید، آن را به ‘C’ تغییر دهید و به راست بروید» را در مجموعه قوانینش داشته باشد.
ماشین تورینگ معمولی (قطعی - DTM) دارای تابع انتقال است که برای وضعیت داده شده و نمادی که روی نوار به آن اشاره می شود، ۳ چیز را مشخص می کند: نمادی که باید روی نوار نوشته شود، جهت حرکت هد (چپ، راست یا هیچکدام) و وضعیت بعدی ...
برای مثال، X روی نوار در وضعیت ۳ ممکن است DTM را وادار به نوشتن Y روی نوار، حرکت هد به راست و انتقال به وضعیت ۵ کند.تفاوت ماشین تورینگ غیرقطعی (NTM) این است که وضعیت داده شده و نماد روی نوار ۳چیز منحصربه فرد را مشخص نمی کند، بلکه برای ترکیب مشابه از وضعیت و نماد ممکن است انتقال های متفاوتی انجام شود. برای مثال، X روی نوار در وضعیت۳ ممکن است به ماشین اجازه دهد Y را روی نوار بنویسد، به راست برود و به وضعیت ۵ برود یا X را بنویسد، به چپ برود و در وضعیت ۳ بماند.
wiki: ماشین تورینگ غیرقطعی