بخش تصمیمپذیری معمولاً آخرین فصل نظریهٔ زبانهاست و خیلیها به آن نمیرسند یا فقط تعریفهایش را حفظ میکنند. ولی تستهای این بخش بیشتر طبقهبندیاند تا اثبات: این مسئله تصمیمپذیر است یا نه؟ این زبان قابلشناسایی است؟ مکملش چطور؟ اگر نقشهٔ کلی را داشته باشی و چند ابزار را درست به کار ببری، بیشتر این تستها چند ثانیهای حل میشوند.
ماشین تورینگ در یک پاراگراف
ماشین تورینگ یک ماشین متناهی است با یک نوار بیپایان که میتواند رویش بنویسد و به چپ و راست حرکت کند. روی هر ورودی سه حالت ممکن است: بپذیرد، رد کند، یا هیچوقت متوقف نشود. همین حالت سوم است که کل بحث تصمیمپذیری را میسازد.
گونههای مختلف ماشین تورینگ قدرت یکسانی دارند: ماشین چندنواره را ماشین تکنواره با کندی درجهدوم شبیهسازی میکند و ماشین غیرقطعی را ماشین قطعی با کندی نمایی. پس در سؤال «تصمیمپذیر است یا نه» نوع ماشین فرقی نمیکند؛ فقط در سؤالهای پیچیدگی زمانی فرق دارد.
نقشهٔ زبانها
هر ردیف این جدول زیرمجموعهٔ سرهای از ردیف بعدی است:
| دسته | ماشین | گرامر | نمونهای که در دستهٔ قبلی نیست |
|---|---|---|---|
| منظم | ماشین متناهی | منظم | — |
| مستقل از متن | ماشین پشتهای غیرقطعی | مستقل از متن | aⁿbⁿ |
| حساس به متن | ماشین کراندار خطی | حساس به متن | aⁿbⁿcⁿ |
| تصمیمپذیر (بازگشتی) | ماشین تورینگی که همیشه متوقف میشود | — | زبانی که با قطریسازی روی همهٔ ماشینهای کراندار خطی ساخته میشود |
| قابلشناسایی (شمارشپذیر بازگشتی) | ماشین تورینگ | بدون محدودیت | مسئلهٔ توقف |
| همهٔ زبانها | — | — | مکمل مسئلهٔ توقف |
یک استدلال شمارشی هم نشان میدهد زبانهای غیرقابلشناسایی حتماً وجود دارند: تعداد ماشینهای تورینگ شماراست، چون هر ماشین یک رشتهٔ متناهی است، ولی تعداد زبانها ناشماراست.
تصمیمپذیر، قابلشناسایی، همقابلشناسایی
سه دسته را از هم جدا کن. زبان قابلشناسایی ماشینی دارد که روی عضوها میپذیرد. زبان همقابلشناسایی زبانی است که مکملش قابلشناسایی است. قضیهٔ کلیدی این است که زبان تصمیمپذیر است اگر و فقط اگر هر دو باشد: دو ماشین را همزمان و قدمبهقدم اجرا کن؛ هر ورودی عضو یکی از دو زبان است، پس یکی از دو ماشین بالاخره میپذیرد.
نتیجهٔ مستقیم: مسئلهٔ پذیرش ماشین تورینگ قابلشناسایی است ولی تصمیمپذیر نیست، پس مکملش نمیتواند قابلشناسایی باشد. اگر مکملش هم قابلشناسایی بود، خودش تصمیمپذیر میشد.
جدول مسئلههای تصمیم برای سه نوع ماشین
این جدول بیشترین کاربرد را در تستها دارد. «پذیرش» یعنی آیا ماشین رشتهٔ w را میپذیرد، «تهی بودن» یعنی آیا زبانش خالی است و «همارزی» یعنی آیا دو ماشین یک زبان را میپذیرند:
| مسئله | DFA | گرامر مستقل از متن | ماشین تورینگ |
|---|---|---|---|
| پذیرش (عضویت) | تصمیمپذیر | تصمیمپذیر (مثلاً با CYK) | قابلشناسایی، نه تصمیمپذیر |
| تهی بودن | تصمیمپذیر | تصمیمپذیر | همقابلشناسایی، نه تصمیمپذیر |
| همارزی | تصمیمپذیر | تصمیمناپذیر | نه قابلشناسایی، نه همقابلشناسایی |
| تولید همهٔ رشتهها (Σ*) | تصمیمپذیر | تصمیمناپذیر | تصمیمناپذیر |
یک الگو در جدول هست: هرچه ماشین قویتر میشود، مسئلههای بیشتری تصمیمناپذیر میشوند. همارزی اولین چیزی است که با گرامرهای مستقل از متن از دست میرود، در حالی که عضویت و تهی بودن هنوز تصمیمپذیرند.
قضیهٔ رایس با سه سؤال
قضیهٔ رایس میگوید هر ویژگی غیربدیهی از زبانِ پذیرفتهشده توسط ماشین تورینگ تصمیمناپذیر است. برای اینکه در تست درست به کارش ببری، سه سؤال را به ترتیب بپرس:
- این ویژگی دربارهٔ زبان ماشین است یا دربارهٔ خود ماشین؟ اگر دو ماشین با زبان یکسان ممکن است جواب متفاوت بگیرند، ویژگی دربارهٔ ماشین است و رایس به کار نمیآید.
- غیربدیهی است؟ یعنی دستکم یک ماشین این ویژگی را دارد و دستکم یکی ندارد.
- اگر جواب هر دو «بله» است، ویژگی تصمیمناپذیر است.
| ویژگی | دربارهٔ زبان؟ | نتیجه |
|---|---|---|
| زبان M تهی است | بله | تصمیمناپذیر (رایس) |
| زبان M منظم است | بله | تصمیمناپذیر (رایس) |
| M رشتهٔ 01 را میپذیرد | بله | تصمیمناپذیر (رایس) |
| M بیشتر از ۵ حالت دارد | نه | تصمیمپذیر؛ توصیف ماشین را بخوان |
| M روی ورودی خالی بیش از ۱۰۰ قدم اجرا میشود | نه | تصمیمپذیر؛ ۱۰۱ قدم شبیهسازی کن |
| زبان M قابلشناسایی است | بله، ولی بدیهی | تصمیمپذیر؛ زبان هر ماشین تورینگ قابلشناسایی است، پس جواب همیشه بله است |
کاهش: جهتش را اشتباه نکن
برای اثبات اینکه مسئلهٔ B تصمیمناپذیر است، یک مسئلهٔ تصمیمناپذیر شناختهشده مثل A را به B کاهش میدهی: A ≤ B. منطقش این است که اگر B تصمیمپذیر بود، با آن A را هم حل میکردی، که ممکن نیست.
اشتباه رایج این است که B را به A کاهش بدهی. B ≤ A فقط میگوید B از A سختتر نیست و دربارهٔ تصمیمناپذیر بودن B چیزی نمیگوید؛ حتی یک مسئلهٔ ساده را هم میشود به مسئلهٔ توقف کاهش داد.
یک نمونهٔ کامل: برای نشان دادن اینکه تهی بودن زبان ماشین تورینگ تصمیمناپذیر است، از هر جفت ماشین M و رشتهٔ w ماشین تازهای بساز که روی ورودی x، اگر x با w فرق داشت رد کند و اگر x همان w بود M را روی w اجرا کند. زبان ماشین تازه تهی است دقیقاً وقتی که M رشتهٔ w را نپذیرد. پس اگر تهی بودن تصمیمپذیر بود، پذیرش هم تصمیمپذیر میشد.
پرسشهای پرتکرار
فرق تصمیمپذیر و قابلشناسایی چیست؟
ماشین تصمیمگیر روی هر ورودی متوقف میشود و بله یا نه میگوید. ماشین شناساییگر فقط روی عضوهای زبان باید بپذیرد و روی غیرعضوها ممکن است تا ابد اجرا شود. هر زبان تصمیمپذیر قابلشناسایی است، ولی برعکسش درست نیست؛ مسئلهٔ توقف مثال نقض است.
آیا مکمل یک زبان قابلشناسایی هم قابلشناسایی است؟
لزوماً نه. زبانهای قابلشناسایی زیر اجتماع و اشتراک بستهاند، ولی زیر مکمل نه. اگر زبانی و مکملش هر دو قابلشناسایی باشند، آن زبان تصمیمپذیر است. زبانهای تصمیمپذیر زیر مکمل بستهاند.
قضیهٔ رایس کی به کار نمیآید؟
وقتی ویژگی دربارهٔ خود ماشین است، مثل تعداد حالتها یا تعداد قدمها روی یک ورودی مشخص، یا وقتی ویژگی بدیهی است، یعنی همهٔ ماشینها آن را دارند یا هیچکدام ندارند. در این موارد ویژگی ممکن است تصمیمپذیر باشد.
همارزی دو گرامر مستقل از متن تصمیمپذیر است؟
نه. عضویت و تهی بودن برای گرامرهای مستقل از متن تصمیمپذیرند، ولی همارزی دو گرامر، و حتی اینکه یک گرامر همهٔ رشتهها را تولید میکند یا نه، تصمیمناپذیر است. برای DFA هر سه تصمیمپذیرند.
این مبحث در کلاس
من ارشدم را در دانشگاه صنعتی شریف، در نرمافزار با گرایش الگوریتم و محاسبات گرفتم و نظریهٔ زبانها و ماشینها را، از زبانهای منظم تا تصمیمپذیری، در کلاس نظریه درس میدهم؛ با ویدیو، جزوهٔ کامل و تستهای حلشده. نتیجهٔ شاگردهایی که نظریه را کامل زدند در صفحهٔ مستندات هست. دورهها بهزودی روی همین سایت منتشر میشوند و ویدیوی رایگان چند جلسه از کلاسهایم هم بهزودی در صفحهٔ ویدیوهای رایگان همین سایت قرار میگیرد.
قدم بعدی تو
این سه ویژگی را طبقهبندی کن: ۱) زبان ماشین تورینگ M متناهی است. ۲) ماشین M روی ورودی 0 در کمتر از ۵۰ قدم متوقف میشود. ۳) مکمل مسئلهٔ توقف قابلشناسایی است.
جوابها: ۱) تصمیمناپذیر؛ ویژگی غیربدیهی زبان است و رایس به کار میآید. ۲) تصمیمپذیر؛ ۵۰ قدم شبیهسازی کن. ۳) نادرست؛ اگر مکمل هم قابلشناسایی بود، مسئلهٔ توقف تصمیمپذیر میشد.
روش کار را در روش تولید محتوا ببین.
منابع این مطلب
- اطلاعیه و جدول مجموعههای امتحانی کارشناسی ارشد ناپیوسته سال ۱۴۰۶سازمان سنجش آموزش کشور · بررسی ۱۷ شهریور ۱۴۰۵ · اطلاعیه و جدول مجموعههای امتحانی کارشناسی ارشد ناپیوسته سال ۱۴۰۶
نظریهٔ زبانها و ماشینها در بستهٔ تخصصی مجموعهٔ ۱۲۷۷ و نظریهٔ محاسبه در مجموعهٔ ۱۲۰۹
سازمان سنجش آموزش کشور — اطلاعیه و جدول مجموعههای امتحانی کارشناسی ارشد ناپیوسته سال ۱۴۰۶