معادل‌های ماشین تورینگ

اثبات معادل بودن

ماشین تورینگ و معادل‌های آن توان محاسباتی یکسانی دارند یعنی زبان‌هایی که قابلیت شناسایی دارند برابر است و فقط ممکن است در زمان یا حافظهٔ کمتری محاسبات را انجام دهند و در نتیجه با آن‌ها می‌توان مسائل را راحت‌تر حل نمود.
برای این که نشان دهیم ماشین تورینگ معادل است باید بتوانیم توسط ماشین تورینگ آن را شبیه‌سازی کنیم.
برای مثال اگر بخوایم ماشین تورینگی که تابع انتقالش به جز امکان چپ و راست رفتن دارای امکان ماندن در خانه را دارد را با ماشین تورینگ شبیه‌سازی می‌کنیم. هر گاه در این ماشین از این امکان استفاده شد در ماشین تورینگ یک بار به سمت چپ و سپس یک بار به سمت راست می‌رویم پس این ماشین در واقع معادل ماشین تورینگ است. (اثبات کامل نیست)
و یا اگر بخواهیم نحوهٔ تبدیل ماشین چندنواره تورینگ را به ماشین تک نواره تورینگ نشان می‌دهیم. در این ماشین هر نوار دارای هد جداگانه برای نوشتن و خواندن است و تابع انتقال قابلیت خواندن، نوشتن و حرکت دادن هد را بر روی تمامی نوارها به صورت همزمان می‌دهد. باید نشان دهیم که با ماشین تک نواره می‌توانیم ماشین چندنواره را شبیه‌سازی کنیم، برای این کار نشان می‌دهیم که ماشین تک نواره می‌تواند تأثیر چندین نوار را بر روی یک نوار ذخیره‌سازی کند. برای ماشین تک نواره نماد # را تعریف می‌کنیم که به عنوان جداکنندهٔ محتوای نوارهاست. برای این که بدانیم محل هر هد در نوارها کجاست یک نقطه بر روی هر خانه که هد روی آن قرار دارد قرار می‌دهیم؛ و با استفاده از این نمادها اثبات را کامل می‌کنیم.

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

از مهم‌ترین معادل‌های ماشین تورینگ ماشین تورینگ غیرقطعی است. در ماشین تورینگ قطعی، مجموعهٔ قوانین به ازای هر وضعیت داده شده، حداکثر یک حرکت را مجاز می‌کند. ماشین تورینگ غیرقطعی برخلاف ماشین تورینگ قطعی، دارای مجموعه قوانینی است که به ازای هر وضعیت، بیشتر از یک حرکت را مجاز می‌کند. برای مثال، ماشین تورینگ غیرقطعی ممکن است هر دو قوانین «اگر در وضعیت ۳ هستید و نماد ‘D’ دیدید، آن را به ‘B’ تغییر دهید و به چپ بروید.» و «اگر در وضعیت ۳ هستید و نماد ‘D’ دیدید، آن را به ‘C’ تغییر دهید و به راست بروید» را در مجموعه قوانینش داشته باشد. برای این که بدانیم این ماشین رشتهٔ ورودی را پذیرش می‌کند یا نه در هر مرحله که چند حرکت ممکن ماشین به چند کپی از خودش تقسیم می‌شود و هرکدام یکی از حرکت‌های ممکن را دنبال می‌کند. اگر حداقل یکی از شاخه‌های درخت به وضعیت پذیرش برود، می‌گوییم ماشین تورینگ غیرقطعی ورودی را پذیرفته‌است.
برای شبیه‌سازی این ماشین توسط ماشین تورینگ قطعی می‌توان هر حالت را معادل چند حالت ممکن در ماشین غیرقطعی در نظر گرفت.

ماشین ونگ

در این ماشین فقط اعداد ۰ و ۱ روی نوار قابل نوشتن هستند و قوانین آن محدودند به
１)نوشتن ۰
２)نوشتن ۱
３)رفتن به راست.
４)رفتن به چپ
５)با دیدن ۰ رفتن به قانون i
６)با دیدن ۱ رفتن به قانون j
در این ماشین به جای نوار از یک طرف بینهایت از نوار بینهایت از دو طرف استفاده شده که قابل شبیه‌سازی با نوار یک طرفه است.

ماشین‌های دارای رجیستر

در این ماشین‌ها به جای نوار از رجیسترها استفاده می‌شود؛ و در هر کدام تعداد معینی رجیستر و قواعد وجود دارد. به ماشین‌های دارای رجیستر ماشین‌های شمارنده یا ماشین‌های برنامه نیز گفته می‌شود.
در ساده‌ترین این ماشین‌ها ماشین‌های شمارنده ای هستند که تعدادی قواعد محدودی دارند برای مثال دارای ۳ قاعدهٔ افزایش (عدد رجیستر را ۱ واحد افزایش می‌دهد) قاعدهٔ کاهش (عدد رجیستر را ۱ واحد کاهش می‌دهد) و قاعدهٔ پرش صفر (اگر رجیستر ۰ بود به قاعدهٔ مشخص شده برو و اگر نبود به قاعدهٔ بعدی برو.
از مدل‌های دیگر این ماشین‌ها ماشین‌های دارای پوینتر ماشین‌های دسترسی تصادفی و ماشین‌های دسترسی تصادفی با برنامهٔ ذخیره شده هستند. در ماشین‌های دسترسی تصادفی آدرس دهی غیرمستقیم به رجیسترها را داریم و در ماشین‌های دسترسی تصادفی با برنامهٔ ذخیره شده برنامه را در رجیسترها به صورت ذخیره شده داریم.

ماشین‌های دارای نوار ورودی و خروجی

در این ماشین‌ها به جای نوارهایی که قابلیت نوشتن و خواندن دارند نوارهایی داریم که فقط می‌توانیم از آن‌ها بخوانیم و نوارهایی داریم که فقط می‌توانیم روی آن‌ها بنویسیم. می‌توان اثبات نمود که این ماشین‌ها نیز معادل تورینگند.

ابزارهای معادل

جبر لاندا که توسط آلونزو چرچ مطرح شده‌است معادل با ماشین تورینگ است.
الگوریتم مارکو که سیستمی برای جایگزینی نمادها با رشته هاست نمونه ای دیگر از ابزارهای معادل ماشین تورینگ است.
ماشین تورینگ چند بعدی نیز از ابزارهای معادل است که برای هر خانهٔ یک ماشین nبعدی nعدد را در نظر می‌گیریم که خانه‌های مجاور فقط در یک عدد با هم تفاوت یک واحدی دارند.