ماشین تورینگ غیرقطعی

ماشین تورینگ غیرقطعی به‌طور رسمی یک ۶-تایی ${\displaystyle M=(Q,\mathrm{\Sigma },\iota ,\bigsqcup ,A,\delta )}$

• ${\displaystyle Q}$
  مجموعه متناهی از وضعیت‌ها
• ${\displaystyle \mathrm{\Sigma }}$
  مجموعهٔ متناهی از الفبای ورودی
• ${\displaystyle \iota \in Q}$
  وضعیت شروع
• ${\displaystyle \bigsqcup \in \mathrm{\Sigma }}$
  نماد خالی
• ${\displaystyle A\subseteq Q}$
  مجموعه حالت‌های پذیرش
• ${\displaystyle \delta \subseteq \left(Q\mathrm{\setminus }A\times \mathrm{\Sigma }\right)\times \left(Q\times \mathrm{\Sigma }\times \{L,R\}\right)}$
  ارتباط بین وضعیت‌ها و نمادها که رابطهٔ انتقال نامیده می‌شود.

تفاوت بین ماشین تورینگ استاندارد (قطعی) و غیرقطعی این است که در قطعی رابطه انتقال تابع است (تابع انتقال).

حالت‌ها و عملکرد رابطه روی حالت‌ها که انتقال‌های ممکن تورینگ ماشین با اجزای ممکن نوار را توصیف می‌کند، مانند ماشین تورینگ استاندار است بجزاینکه حاصل رابطه دیگر یک مقدار تنها نیست. مفهوم پذیرش رشته بدون تغییر است: ماشین تورینگ غیرقطعی یک رشته را می‌پذیرد اگر، زمانی که ماشین شروع به کار می‌کند هد روی اولین کاراکتر رشته و در غیراینصورت کل نوار خالی باشد. حداقل یکی از محاسبات ماشین ماشین را از آن حالت در وضعیت ${\displaystyle A}$

حل قوانین متعدد

چگونه NTM تشخیص می‌دهد کدام حرکت را باید انجام دهد؟ ۲ روش وجود دارد. اولی اینکه بگوییم «ماشین خوش شانس ترین حدس زنندهٔ ممکن است»؛ همیشه انتقالی را انتخاب می‌کند که به وضعیت پذیرش می‌رود (اگرچنین انتقالی موجود باشد). راه دیگر تصور این است که ماشین به چند کپی از خودش تقسیم می‌شود که هرکدام یکی از حرکت‌های ممکن را دنبال می‌کند. درحالیکه DTM یک مسیر محاسباتی را دنبال می‌کند، NTM دارای درخت محاسباتی است. اگر حداقل یکی از شاخه‌های درخت به وضعیت پذیرش برود، می‌گوییم NTM ورودی را پذیرفته است.

هم‌ارزی DTMها

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

NTMها درموارد خاص شامل DTMها می‌شوند؛ بنابراین واضح است که DTMها قدرتمندتر نیستند. ممکن است به نظر برسد که NTMها از DTMها قدرتمندترند، زیرا آن‌ها یک درخت از محاسبات ممکن را ناشی از حالت مشابه ممکن می‌سازند و رشته را اگر هر یک از شاخه‌های درخت پذیرشش کند، می‌پذیرند.

اما شبیه‌سازی NTMها با DTMها امکان‌پذیراست: روش اول استفاده از DTM است به طوریکه هر حالت نشان دهندهٔ چند حالت در NTM است وعملیات DTM شامل مراجعه به هر کدام به نوبهٔ خود، انجام یک مرحله در هر مراجعه و جابه‌جایی به حالت جدید هرگاه رابطه انتقال چند حالت را تعریف کند، می‌باشد.

روش دیگر شبیه‌سازی NTM، استفاده از DTM با ۳ نواراست؛ که نوار اول همیشه ورودی اولیه را نگهداری می‌کند، نوار دوم محاسبات مشخص NTM را شبیه‌سازی می‌کند و نوار سوم مسیر را در درخت محاسبات NTM کدگذاری می‌کند.

DTMهای ۳ نواره به آسانی با DTM تک نواره معمولی شبیه‌سازی می‌شود. در این روش ساخت، ِDTM حاصل جستجوی اول سطحی از درخت محاسبات NTM را انجام می‌دهد؛ و همهٔ حالات ممکن را می‌بیند تا وقتی که یک کدام را پذیرش کند.

بنابراین، طول مسیرپذیرش در DTM نمایی است با توجه به طول کوتاهترین مسیر پذیرش درNTM. این یک ویژگی کلی شبیه‌سازی NTM با DTM است. مشهورترین مسئلهٔ حل نشده در علوم کامپیوتر مسئله P = NP به این موضوع مربوط است.

NTM این خاصیت را دارد. مثلاً اگر NTM با ورودی نوار داده شده متوقف شود آنگاه روی تعداد مراحل محدودی متوقف شده بنابراین تنها می‌تواند تعداد محدودی حالت ممکن داشته باشد. مقایسه با کامپیوترهای کوانتوم این یک تصور غلط است که کامپیوترهای کوانتوم NTM می‌باشند. این باورشده‌است اما هنوز اثبات نشده‌است که قدرت کامپیوترهای کوانتوم قابل مقایسه با NTMهاست. مسئله‌ای وجود دارد که NTM به‌طور مؤثر می‌تواند حلش کند اما کامپیوتر کوانتوم نمی‌تواند. از مسائل قابل حل با NTM اما غیرقابل حل با کامپیوترهای کوانتوم در زمان چندجمله‌ای مسائل NP-complete می‌باشند.

NTM این خاصیت را دارد. مثلاً اگر NTM با ورودی نوار داده شده متوقف شود آنگاه روی تعداد مراحل محدودی متوقف شده بنابراین تنها می‌تواند تعداد محدودی حالت ممکن داشته باشد.

این یک تصور غلط است که کامپیوترهای کوانتوم NTM می‌باشند. این باور شده ‌است اما هنوز اثبات نشده‌است که قدرت کامپیوترهای کوانتوم قابل مقایسه با NTMهاست. مسئله‌ای وجود دارد که NTM به‌طور مؤثر می‌تواند حلش کند اما کامپیوتر کوانتوم نمی‌تواند. از مسائل قابل حل با NTM اما غیرقابل حل با کامپیوترهای کوانتوم در زمان چندجمله‌ای مسائل NP-complete می‌باشند.