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

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

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

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

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

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

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

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

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

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

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

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

ماشین ونگ

در این ماشین فقط اعداد ۰ و ۱ روی نوار قابل نوشتن هستند و قوانین آن محدودند به

１)نوشتن ۰

２)نوشتن ۱

３)رفتن به راست.

４)رفتن به چپ

５)با دیدن ۰ رفتن به قانون i

６)با دیدن ۱ رفتن به قانون j

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

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

در این ماشین‌ها به جای نوار از رجیسترها استفاده می‌شود؛ و در هر کدام تعداد معینی رجیستر و قواعد وجود دارد. به ماشین‌های دارای رجیستر ماشین‌های شمارنده یا ماشین‌های برنامه نیز گفته می‌شود.

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

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

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

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

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

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

الگوریتم مارکو که سیستمی برای جایگزینی نمادها با رشته هاست نمونه ای دیگر از ابزارهای معادل ماشین تورینگ است.

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

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Turing machine equivalents». در دانشنامهٔ ویکی‌پدیای انگلیسی
• Elements of the Theory of Computation, by Harry R. Lewis and Christos H. Papadimitriou, Prentice-Hall, Englewood Cliffs, New Jersey, 1981, ISBN 0-13-273417-6, pp. 206–211
• (John C. Martin (1997). Introduction to Languages and the Theory of Computation (2nd ed
• https://users.cs.duke.edu/~rodger/courses/cps140/lects/secttm2H.pdf
• Weisstein, Eric W. "Register Machine." From MathWorld—A Wolfram Web Resource. http://mathworld.wolfram.com/RegisterMachine.html