آموزش ماشین تورینگ | اجرای ماشین تورینگ

شروع اجرا

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

فرض کنید یک ماشین تورینگ داریم. این ماشین از سه بخش اصلی تشکیل شده است:

• یک نوار (tape) که به خانه‌های بی‌شمار تقسیم شده و هر خانه می‌تواند یک نماد از الفبای نوار را نگه دارد.
• یک سر (head) که روی یکی از خانه‌های نوار قرار می‌گیرد و می‌تواند نماد آن خانه را بخواند، نماد جدیدی بنویسد، یا یک خانه به چپ یا راست حرکت کند.
• یک واحد کنترل که وضعیت فعلی ماشین را نگه می‌دارد. وضعیت‌ها با نام‌هایی مثل q0، q1، q2 و… مشخص می‌شوند.

اکنون برای شروع اجرا، مراحل زیر به ترتیب انجام می‌شود:

1. ورودی روی نوار نوشته می‌شود. رشته ورودی به صورت نمادهایی از الفبای نوار، از خانه اول نوار به سمت راست قرار می‌گیرد.
2. خانه‌های باقی‌مانده نوار که ورودی در آن‌ها قرار نگرفته است، با نماد خاصی به نام «نماد خالی» (blank) پر می‌شوند. این نماد معمولاً با علامت ⊔ یا B نشان داده می‌شود و یعنی این خانه هیچ داده‌ای ندارد.
3. سر خواندن/نوشتن روی اولین نماد ورودی (یعنی چپ‌ترین خانه‌ای که ورودی از آن شروع شده) قرار می‌گیرد. به این ترتیب ماشین آماده است تا اولین نماد را بخواند.
4. واحد کنترل در وضعیت آغازین قرار می‌گیرد. وضعیت آغازین معمولاً با q0 نشان داده می‌شود و به ماشین می‌گوید که از کجا باید شروع کند.
5. اجرا از همین نقطه آغاز می‌شود. ماشین نماد زیر سر را می‌خواند، وضعیت فعلی خود را در نظر می‌گیرد، و بر اساس قوانین انتقال، نماد جدیدی می‌نویسد، سر را حرکت می‌دهد و به وضعیت جدید می‌رود.

به این ترتیب، شروع اجرا در واقع شامل «آماده‌سازی اولیه» است. ورودی روی نوار قرار می‌گیرد، سر روی اولین نماد ورودی می‌ایستد، وضعیت روی q0 تنظیم می‌شود و سپس اولین گام انتقال اجرا می‌شود.

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

برای روشن‌تر شدن مطلب، یک مثال ساده را در نظر بگیرید. فرض کنید ماشین تورینگی داریم که می‌خواهد بررسی کند آیا رشته ورودی فقط شامل نماد «1» است یا نه. ورودی ما رشته «111» است. در شروع اجرا:

• نوار به این صورت پر می‌شود: خانه اول «1»، خانه دوم «1»، خانه سوم «1» و بقیه خانه‌ها نماد خالی.
• سر روی خانه اول که «1» است قرار می‌گیرد.
• وضعیت روی q0 تنظیم می‌شود.
• سپس اولین گام انتقال انجام می‌شود.

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

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

پس به طور خلاصه، شروع اجرا یعنی:

• نوشتن ورودی روی نوار
• پر کردن بقیه نوار با نماد خالی
• قرار دادن سر روی اولین نماد ورودی
• تنظیم وضعیت روی q0
• انجام اولین گام انتقال

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