ماشین تورینگ چیست؟

ماشین تورینگ یکی از مفاهیم مهم در حوزه علوم کامپیوتر و تئوری محاسبات است. این مفهوم توسط دانشمند برجسته انگلیسی به نام آلن ماتیسون تورینگ (Alan Mathison Turing) در سال 1936 معرفی شد و اساساً به عنوان یک مدل مفهومی برای توصیف قدرت محاسباتی ماشین‌ها ارائه شد.

ماشین تورینگ چیست؟

ماشین تورینگ، به عنوان یک مدل ریاضی (تئوری محاسباتی)، یک دستگاه فرضی بوده که شامل یک نوار با طول بی‌نهایت با خانه‌های متوالی است که هر خانه می‌تواند حاوی یک نماد از یک مجموعه معین باشد. همچنین، این ماشین دارای یک سرخوان(head) است که قادر می‌باشد بر روی نوار حرکت کند و عملیات‌های مختلفی را بر روی نمادها انجام دهد. (سرخوان یا هد دستگاه در ماشین تورینگ، یک قسمت مهم است که مسئول خواندن و نوشتن نمادها روی نوار است. سرخوان قادر است بر روی نوار جابجا شود و با خواندن نمادهای موجود در هر خانه از نوار و براساس قوانین ماشین تورینگ، عملیات‌های مختلفی را انجام دهد.)

ماشین تورینگ چه عمکردی دارد؟

عملکرد ماشین تورینگ بر اساس یک جدول قوانین تعریف می‌شود که شامل مجموعه‌ای از حالت‌ها، نمادها، قوانین انتقال و حالت‌های پذیرفته شدن است. این قوانین مشخص می‌کنند که با دریافت یک حالت خاص و خواندن یک نماد مشخص از نوار، ماشین چه کارهایی انجام می‌دهد. این عملیات می‌تواند شامل حذف یا اضافه کردن نمادها، جابجایی سرخوان روی نوار، تغییر حالت ماشین و غیره باشد.

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

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

تعریف تخصصی‌تر ماشین تورینگ

ماشین تورینگ یا Turing Machine در واقع با 7 علامت یا قانون توصیف می شود که این علامت ها عبارت اند از Q, Γ, ∑, δ, q0, B, F و هر کدام دارای مفهموم خاصی می باشند که در ذیل به آن اشاره شده است.

• Q: مجموعه ایی محدود(متناهی) از حالات.
• Γ: مجموعه ای متنهای که با عنوان الفبای ماشین شناخته می شود.
• B: نمادی زیر مجموعه Γ برای نمایش یک فاصله خالی روی ماشین تورینگ.
• ∑: افبای ورودی می باشد که شامل B(فاصله خالی) نیست. نوار خالی نمی تواند ورودی باشد.
• δ: این نماد در واقع یک تابع انتقال است با دامنه Q*Γ و برد {Lچپ , Rراست}*Q*Γ.
• q0: حالتی از ماشین است که ما محاسبه را در آن حالت شروع می کنیم.
• F: مجموعه ای از حالت نهایی می باشد.

نحوه کار ماشین تورینگ (Turing Machine)

ماشین تورینگ با استفاده از قوانینی که به آنها اشاه نمودیم، به صورت تک مرحله‌ای و ترتیبی عمل می‌کند. در ابتدا، ماشین تورینگ در یک حالت اولیه قرار دارد (q0) و هد دستگاه (سرخوان) در یک موقعیت خاص روی نوار قرار می‌گیرد. نحوه کار ماشین تورینگ به شکل ذیل می باشد:

1. سرخوان نماد خانه ای که در آن قرار دارد را می خواند.
2. بر اساس حالت فعلی ماشین، قانون انتقال مناسب را بررسی می کند. (این قانون مشخص می‌کند که با دریافت نماد و در حالت فعلی، ماشین چه کارهایی باید انجام دهد.)

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

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

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

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

• اگر ماشین تورینگ به یک حالت پذیرفته شده برسد، به این معنی است که محاسبه با موفقیت به پایان رسیده و نتیجه مورد انتظار به دست آمده است.
• اگر ماشین تورینگ به یک حالت رد شده برسد، یعنی محاسبه ناموفق بوده و نتیجه مورد انتظار به دست نیامده است.
• ممکن است قوانین ماشین تورینگ مشخص کنند که ماشین در یک حالت متوقف قرار بگیرد، بدون رسیدن به حالت پذیرفته یا رد شده. به این صورت، محاسبه تمام می‌شود.

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

ماشین تورینگ کامل چیست؟

ماشین تورینگ کامل یا Turing Completeness در واقع ماشینی است که قادر به محاسبه همه‌‌ی عملگر های ریاضی را می باشد. عملگرهایی از جمله:

• عملگرهای ریاضی (+ - * ...)
• حلقه یا loop
• انشعاب و انتقال
• توابع ریاضیات
• انواع شرط یا if & else

آیا ماشین تورینگ دارای محدودیت می باشد؟

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