مسئله توقف در ماشین تورینگ

در این ویدئوی آموزشی به بررسی مسئله توقف در ماشین تورینگ خواهیم پرداخت.

کیفیت فیلم بصورت پیش فرض بر روی حالت low تنظیم شده است و شما می توانید با استفاده از تنظیمات موجود، این آموزش را با بالاترین کیفیت مشاهده نمایید.

شما می توانید با استفاده از گزینه “متن فیلم”، متن مربوط به حل سوال را مشاهده کنید.

//******************************************************************************************************************************************//

پیشنهاد می شود قبل از مشاهده این آموزش مروری بر مبحث ماشین تورینگ داشته باشید.

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

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

نکته ای که باید در نظر گفت این است که مسئله توقف در ماشین‌های تورینگ، یک مسئله تصمیم‌پذیر نمی باشد.

می گوییم ماشین تورینگ M، زبان L را در زمان T(n) می پذیرد اگر برای هر رشته جز زبان L با طول کمتر مساوی n در O(T(n)) حرکت، پذیرفته شود.

حال یک مثال را بررسی می کنیم. ماشین تورینگ زیر را در نظر بگیرید.

این ماشین دارای سه حالت غیر نهایی A، B، C و دو الفبای ۱ و Π است. وضعیت A ،وضعیت شروع است.

سلول های جدول مثلاٌ سلولی که با رنگ آبی نشان داده شده است به این صورت خوانده می شود که در وضعیت A و وجود حرف Π بر روی نوار ماشین، ۱ را روی نوار نوشته به وضعیت B می رود وهد خواندن به سمت راست حرکت می کند.

ماشین در وضعیت A با ورودی نوار ۱ ، حرف ۱ را بازنویسی می کند و هد به سمت راست حرکت می کند و به وضعیت نهایی یا halt می رود و ماشین متوقف می شود.

برای نمونه، عملکرد این ماشین را برای  رشته رو به رو  بررسی می کنیم.ماشین با وضعیت اولیه A با حرف Π

با حرکت به سمت راست به وضعیت B و نوشتن ۱ در سلول به جلو می رود.

در این مرحله از وضعیت B با حرف Π به وضعیت C می رود و بدون تغییر محتوای نوار به سمت راست حرکت می کند.در مرحله  بعد ماشین در وضعیت C با حرف Π است. طبق قواعد ماشین با جایگزینی ۱ در سلول نوار بدون تغییر وضعیت به سمت چپ می رود. شرایط جدید وضعیت C و حرف Π است، بنابر ماشین تورینگ مثل مرحله قبل با نوشتن ۱ در سلول نوار بدون تغییر وضعیت به سمت چپ حرکت می کند.

در این مرحله با وضعیت C و حرف ۱ در نوار به وضعیت A  یعنی سمت چپ می رود.

ماشین به سمت راست با انتقال به وضعیت B و نوشتن حرف ۱ در نوار حرکت می کند. در شرایط جدید ماشین با حرف ۱ و وضعیت B بدون تغییر به سمت جلو می رود.

به این صورت…

در این مرحله ماشین یک سلول به عقب می رود .

در این مرحله ماشین با حرکت به سمت چپ وارد وضعیت A شده،

در این مرحله ماشین متوقف شده و وارد وضعیت نهایی خود شده و رشته پذیرفته می شود.

ماشین طراحی شده در این مثال را در نظر بگیرید . وضعیت A وضعیت شروع است.

توجه شود که این ماشین فقط بین دو حالت B و A  تغییر وضعیت می دهد و  وارد وضعیت C نمی شود .

این ماشین بر خلاف ماشین مثال قبل  برای هیچ رشته ای وارد وضعیت نهایی نمی شود یا به عبارت دیگر در هیچ رشته ای متوقف نمی شود.