محدوده‌ی محاسبات الگوریتمی

محدوده‌ی محاسبات الگوریتمی

اسلاید 1: فصل 12محدوده ي محاسبات الگوريتمي

اسلاید 2: مقدمهديديم كه ماشينهاي تورينگ چه كارهايي را مي توانند انجام دهند حال ببينيم كه چه كارهايي را نمي توانند انجام دهندبراي اينكه بهتر مسئله روشن شود مي توان گفت كه براي زبانه هاي غير بازگشتي هيچ الگوريتمي وجود نداردالبته زبانهاي غير بازگشتي كاربرد علمي بسيار كمي دارند اما مسئله به همين جا ختم نمي شودبراي مثال هيچ الگوريتمي براي تعيين اينكه يك گرامر مستقل از متن غير گنگ است وجود ندارد قطعا اين مسئله در مطالعه زبانهاي برنامه سازي مهم است.

اسلاید 3: مسائلي كه توسط ماشين تورينك قابل حل نيست اينكه قدرت محاسبه مكانيكي محدود است مسئله پذيرفته شده ايست و مسائلي وجود دارد كه از قدرت يك كامپيوتر خارج است.اانچه براي ما جالب است اينست كه مسائلي هستند كه به روشني و سادگي بيان ميشوند و به نظر مي رسند كه ممكن است راه حل الگوريتمي براي انها باشد اما غير قابل حل توسط كامپيوتر هستند.

اسلاید 4: مثال با گرامر مستقل از متنG زبان L(G)گنگ است.اين جمله براي بعضي Gها درست و براي بعضي غلط است. مسئله اينست كه تصميم بگيريم كه براي Gداده شده اين جمله صحيح است يا غلط.در اينجا دامنه اي وجود دارد كه انهم مجموعه تمامي زبانهاي مستقل از متن است.گفتيم كه مسئله اي تصميم پذير است كه يك ماشين تورينگ باشد كه به جملات مرتبط با دامنه ي مسئله پاسخ صحيح است.

اسلاید 5: مسئله ي توقف در ماشين تورينگاين مسئله انست كه ماشين تورينگ Mو ورودي wداده شده اند.سوال اينست كه ايا ماشين Mبا ورودي wتوقف مي كند؟يا به بيان ساده تر ايا (M,w)توقف مي كند يا خير؟در اينجا دامنه ي مسئله تمام ماشين هاي تورينگ و تمامي رشته هاي wاست و اگوريتمي براي ان وجود ندارد.حال تعريف رسمي تر مسئله را بيان مي كنيم.

اسلاید 6: تعريف 12-1 فرض كنيد كه Wmرشته اي باشد كه ماشين تورينگ M=(Q,Σ,Γ,δ,q0,□,F) را توصيف مي كندو w رشته اي از الفباي Mباشد.فرض مي كنيم كه Wmو wبه صورت رشته ايي از 0و1 باشند.راه حل مسئله توقف يك ماشين تورينگ به نام Hاست كه براي هر Wmوwمحاسبه ي زير را انجام مي دهد:q 0 Wm w ├* x1 qy x2و اگر Mروي wعمل كند متوقف مي شود.

اسلاید 7: ادامههم چنين در حالت ديگرq 0 Wm w ├ * y1 qn y2 اگر Mروي wعمل كند توقف نمي كند.در اينجا qnو qyهر دو وضعيت نهايي Hهستند.

اسلاید 8: قضيه 12-1 ماشين تورينگH كه مانند تعريف 12-1 عمل كند وجود ندارد و بنا براين مسئله غير تصميم پذير است.

اسلاید 9: قضيه 12-2اگر مسئله توقف تصميم پذير بود انوقت هر زبان بازگشتي برشمردني بازگشتي مي بود. نتيجتا مسئله ي توقف غير تصميم پذير بود.

اسلاید 10: مسائل غير تصميم پذير براي زبانهاي بازگشتي برشمردني مشخص كرديم كه براي زبانهاي بازگشتي برشمردني الگوريتم عضويت وجود ندارد.زبانهاي بازگشتي بر شمردني انقدر كلي هستند كه هر سوالي در مورد انهاغير تصميم پذير است.

اسلاید 11: قضيه 12-3ِفرض كنيد كه Gيك گرامر نامقيد باشد انوقت مسئله تعيين اينكهL(G)=Ø است يا خير،غير تصميم پذير است.

اسلاید 12: اثبات قضيه 12-3 مسئله عضويت براي زبانهاي بازگشتي برشمردني را به اين مسئله كاهش مي دهيم.فرض كنيد كه ماشين روتينگ M و رشته ي w را داريم.ميتوان Mرا به صورت زير تغيير داد.ابتدا M ورودي خود را در قسمت خاصي از نوار ذخيره مي كند.بعد هرگاه اماده ي ورود به يك وضعيت نهائي شد نگاه ميكند و اگر و فقط اگر ورودي ذخيره شده wبود انرا ميپذيرد.اينكار را با تغيير δو ايجاد يك ماشين Mwبراي هرw به طوريكهL(Mw)=L(M)∩{w} باشد انجام ميدهد.روشن استL(Gw) كه غيرتهي است اگر و فقط اگر w Є L(M)باشد.

اسلاید 13: ادامهحال فرض كنيد كه اگر الگوريتمي مانندA براي تصميم گيري در مورد اينكهL(G)=Ø است يا نه داريم. اگر Tالگوريتمي باشد كه با انGw را توليد مي كنيم انوقت مي توانيمT وA را روي هم بگذاريم.شكل 12-1 تورينگي است كه براي هرM وw به ماميگويد كهw درL(M) است يا خير.اگر چنين ماشين تورينگي وجود داشته ياشد الگوريتم عضويت براي هر زبان بازگشتي برشمردني داريم كه مغادير بانتيجه اي است كه قبلا گرفتيم.نتيجه مي گيريم كه مسئله L(G)=Ø غيرتصميم پذير است.

اسلاید 14: قضيه 12-4فرض كنيد كه Mيك ماشين تورينگ باشد.انگاه اينكه اياL(M) متناهي است يا خير ،غيرتصميم پذير است.

اسلاید 15: اثبات قضيه 12-4مسئله ي توقف (M,w)را در نظر بگيريد.ازM ماشين تورينگ ديگري مانند M*ميسازيم كه كار زير را انجام مي دهد.ابتدا تمامي وضعيت هاي توقفM به گونه اي تغير داده مي شوند كه اگر هريك دستيابي شود انوقت تمام ورودي توسط M*پذيرفته مي شود.اين كار را مي توان با اجازه دادن به هر پيكربندي توقف كه به يك وضعيت نهايي برود انجام داد.سپس ماشين اوليه به گونه اي تغيير داده مي شود كه ماشين جديد M*ابتدا w را روي نوار خود توليد مي كند و بعد همان محاسباتي را كه توسط Mانجام مي شود و با استفاده از wكه تازه ايجاد شده انجام مي دهد.

اسلاید 16: ادامه به عبارت ديگر حركات انجام شده توسط M*پس از اينكهw را روي نوار خود نوشت همان حركاتي است كهM انجام ميدهد اگر در پيكربنديq0w شروع كند.اگر توقف كند انوقتM* دريك وضعيت نهايي توقف مي كند.بنابراين اگر(M,w) توقف كند انوقت M*براي تمام ورودي ها به يك وضعيت نهايي مي رسد.اگر(M,w) توقف نكند M*هم توقف نمي كند و بنابراين چيزي را نميپذيرد.به عبارت ديگرM* يا زبان نامتناهيΣ+ را ميپذيرد و يا زبان متناهيØ را ميپذيرد.

اسلاید 17: ادامهمسائل غير تصميم پذيري براي زبانهاي مستقل از متن وجود دارند.براي نمونه الگوريتمي براي تصميم گيري در مورد اينكه يك گرامر مستقل از متن گنگ است وجود ندارندو هم چنين در زبانهاي مستقل از متن الگوريتمي براي تصميم گيري در مورد اينكه L(G1)∩L(G2)=Øبراي هرG1وG2 مستقل از متن وجود ندارد

اسلاید 18: فصل تمرينات12.1 همراه با جزئيات نشان دهيد كه ماشينM* در قضيه 12-4 چگونه ساخته مي شود..2 نشان دهيد كه دو مسئله مطرح شده در انتهاي بخش قبلي يعنياالفL(M)(حاوي هر رشته با طول پنج است. بL( M)(منظم است. تصميم پذير هستند..3فرض كنيد M1وM2 ماشينهاي تورينگ باشند.نشان دهيد كه مسئله L(M1)زيرمجموعه ي L(M2)غير تصميم پذير است..4 فرض كنيد كه Gيك گرامر نامقيد است.آيا الگوريتمي براي معين كردن اينكه آيا L(G)^Rشماره اي بازگشتي برشمردني است وجود دارد؟.5فرض كنيد كه Gهر گرامر نامقيدي باشد.آيا الگوريتمي براي معين كردن اينكه L(G)=L(G)^Rوجود دارد؟.6فرض كنيد كه G1يك گرامر نامقيد و G2يك گرامر منظم باشد,نشان دهيدكهL(G2)= Ø ∩L(G1)غير تصميم پذير است..7نشان دهيد كه سوال تمرين 6 براي يك G2ثابت تا زماني كه L(G2)خالي نباشد غير تصميم پذير است.

اسلاید 19: گروه1اسلايد فصل 12 كتاب مقدمه اي بر نظريه زبانها و ماشينها)دكتر عبدالحسين صراف زاده(سرنا يزداني شورمستي-سيده زكيه عيسي زاده-شقايق ديلمي