ماشین تورینگ

تاریخچه

معرفی ماشین تورینگ توسط دانشمند انگلیسی آلن تورینگ در سال ۱۹۳۶ میلادی، گام دیگری را در مسیر ایجاد و پیدایش ماشین‌های محاسباتی حالات متناهی به نمایش می‌گذارد. رابین گندی یکی از دانشجویان آلن تورینگ و دوست صمیمی تمام عمرش، ریشه‌های نظریه ماشین محاسباتی بابیج (۱۸۳۴) را کاوش کرد و در حقیقت نظریه بابیج را دوباره ارائه کرد:
آنالیز گندی در مورد ماشین تحلیلی بابیج پنج عملیات زیر را توضیح می‌دهد:
۱-عملگرهای ریاضی + و - و *
۲-هر ترتیبی از عملگرها قابل قبول است.
۳-تکرار عملگر
۴-تکرار شرطی
۵-انتقال شرطی

مقایسه با ماشین‌های واقعی

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

چرا ماشین‌های تورینگ مدل‌های مناسبی برای رایانه‌های واقعی هستند؟

۱. هرچیزی که ماشین واقعی می‌تواند محاسبه کند، ماشین تورینگ هم می‌تواند. برای مثال ماشین تورینگ، می‌تواند هرچیز طبق روالی که در زبان‌های برنامه‌نویسی پیدا می‌شود شبیه‌سازی کند. همچنین می‌تواند فرایندهای بازگشتی و هریک از پارامترهای مکانیسم شناخته شده را شبیه‌سازی کند.
۲. تفاوت، تنها در قابلیت ماشین تورینگ برای دخالت در مقدار محدودی اطلاعات نهفته است؛ بنابراین، ماشین تورینگ می‌تواند در مدت زمان محدودی، در اطلاعات دخالت داشته باشد.
۳. ماشین واقعی همانند ماشین‌های تورینگ می‌توانند حافظه مورد نیازش را به کمک دیسک‌های بیشتر، بزرگ کند. اما حقیقت این است که هم ماشین تورینگ و هم ماشین واقعی، برای محاسبات نیازی به فضا در حافظه‌شان ندارند.
۴. شرح برنامه‌های ماشین واقعی که از مدل ساده‌تر انتزاعی استفاده می‌کنند، پیچیده‌تر از شرح برنامه‌های ماشین تورینگ است.
۵. ماشین تورینگ الگوریتم‌های مستقل را که چقدر از حافظه استفاده می‌کنند، توصیف می‌کند. در دارایی حافظه همهٔ ماشین‌ها، محدودیتی وجود دارد؛ ولی این محدودیت می‌تواند خود سرانه در طول زمان افزایش یابد.
ماشین تورینگ به ما اجازه می‌دهد دربارهٔ الگوریتم‌هایی که برای همیشه نگه داشته می‌شوند، توصیفاتی ارائه دهیم؛ بدون در نظر گرفتن پیش رفت در معماری محاسبات با ماشین معمولی.
۶. ماشین تورینگ جملات الگوریتم را ساده می‌کند. الگوریتم‌های در حال اجرا در ماشین آلات انتزاعی معادل تورینگ، معمولاً نسبت به همتایان خود که در ماشین‌های واقعی در حال اجرا هستند عمومی ترند. زیرا آن‌ها دارای دقت دلخواه در انواع اطلاعات قابل دسترس هستند و هیچوقت با شرایط غیرمنتظره روبرو نمی‌شوند. یکی از نقطه ضعف‌های ماشین تورینگ این است که برنامه‌های واقعی که نوشته می‌شوند ورودی‌های نامحدودی را در طول زمان دریافت می‌کنند؛ در نتیجه هرگز متوقف نمی‌شوند.

نظریه پیچیدگی محاسباتی

یکی از محدودیت‌ها و معایب ماشین‌های تورینگ این است که آن‌ها توانایی چیدمان خوب را ندارند. برای مثال کامپیوترهای برنامه‌ای با ذخیره مدرن، نمونه‌هایی از یک مدل خاص ماشین انتزاعی که به نام ماشین برنامه دسترسی رندم یا مدل ماشین RASP می‌باشند.

همزمانی

یکی دیگر از محدودیت‌های ماشین تورینگ این است که همزمانی را خوب ارائه نمی‌دهد. برای مثال برای اندازه عدد صحیحی که می‌تواند توسط «متوقف کننده غیر قطعی دایمی» محاسبه شود، محدودیت وجود دارد. ماشین تورینگ روی یک نوار خالی شروع می‌کند. در مقابل، ماشین‌های «همیشه متوقف» همزمان هستند که بدون ورودی می‌توانند عدد صحیح نامتناهی را محاسبه کنند.