بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
مقدمه
ديديم كه ماشينهاي تورينگ چه كارهايي را مي توانند انجام دهند حال ببينيم كه چه كارهايي را نمي توانند انجام دهند
براي اينكه بهتر مسئله روشن شود مي توان گفت كه براي زبانه هاي غير بازگشتي هيچ الگوريتمي وجود ندارد
البته زبانهاي غير بازگشتي كاربرد علمي بسيار كمي دارند اما مسئله به همين جا ختم نمي شود
براي مثال هيچ الگوريتمي براي تعيين اينكه يك گرامر مستقل از متن غير گنگ است وجود ندارد قطعا اين مسئله در مطالعه زبانهاي برنامه سازي مهم است.
اسلاید 2 :
مسائلي كه توسط ماشين تورينك قابل حل نيست
اينكه قدرت محاسبه مكانيكي محدود است مسئله پذيرفته شده ايست و مسائلي وجود دارد كه از قدرت يك كامپيوتر خارج است.
اانچه براي ما جالب است اينست كه مسائلي هستند كه به روشني و سادگي بيان ميشوند و به نظر مي رسند كه ممكن است راه حل الگوريتمي براي انها باشد اما غير قابل حل توسط كامپيوتر هستند.
اسلاید 3 :
مثال
با گرامر مستقل از متنG زبان L(G)گنگ است.اين جمله براي بعضي Gها درست و براي بعضي غلط است.
مسئله اينست كه تصميم بگيريم كه براي Gداده شده اين جمله صحيح است يا غلط.
در اينجا دامنه اي وجود دارد كه انهم مجموعه تمامي زبانهاي مستقل از متن است.
گفتيم كه مسئله اي تصميم پذير است كه يك ماشين تورينگ باشد كه به جملات مرتبط با دامنه ي مسئله پاسخ صحيح است.
اسلاید 4 :
مسئله ي توقف در ماشين تورينگ
اين مسئله انست كه ماشين تورينگ Mو ورودي wداده شده اند.
سوال اينست كه ايا ماشين Mبا ورودي wتوقف مي كند؟
يا به بيان ساده تر ايا (M,w)توقف مي كند يا خير؟
در اينجا دامنه ي مسئله تمام ماشين هاي تورينگ و تمامي رشته هاي wاست و اگوريتمي براي ان وجود ندارد.
حال تعريف رسمي تر مسئله را بيان مي كنيم.
اسلاید 5 :
تعريف 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عمل كند متوقف مي شود.
اسلاید 6 :
ادامه
هم چنين در حالت ديگر
q 0 Wm w ├ * y1 qn y2
اگر Mروي wعمل كند توقف نمي كند.
در اينجا qnو qyهر دو وضعيت نهايي Hهستند.
اسلاید 7 :
قضيه 12-1
ماشين تورينگH كه مانند تعريف 12-1 عمل كند وجود ندارد و بنا براين مسئله غير تصميم پذير است.
اسلاید 8 :
اگر مسئله توقف تصميم پذير بود انوقت هر زبان بازگشتي برشمردني بازگشتي مي بود.
نتيجتا مسئله ي توقف غير تصميم پذير بود.
اسلاید 9 :
مسائل غير تصميم پذير براي زبانهاي بازگشتي برشمردني
مشخص كرديم كه براي زبانهاي بازگشتي برشمردني الگوريتم عضويت وجود ندارد.
زبانهاي بازگشتي بر شمردني انقدر كلي هستند كه هر سوالي در مورد انهاغير تصميم پذير است.
اسلاید 10 :
قضيه 12-3
ِفرض كنيد كه Gيك گرامر نامقيد باشد انوقت مسئله تعيين اينكهL(G)=Ø است يا خير،غير تصميم پذير است.
