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

صفحه 1:
۳ محدوده ‎Ss‏ محاسبات الكوريتمي 

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

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

صفحه 4:
i lie | با گرامر مسنقل از منتن6 زبان ‎LHC)‏ ‏است .این جمله براي بعضي ها درست و ‎orl‏ شده این جمله صحیح است یا غلط. در اينجا دامنه اي وجود دارد كه أنهم مجموعه تمامي زبانهاي مستقل از متن است. ‎«a aS wal, Ee eg eel, Ll‏ جيلات 

صفحه 5:
این مسئله انست که ماشین تورینگ 0و ورودي سداده شده آند. ‎Sigs‏ ايتست كه ايا عانثتين 10 ورزودى ستوقف مي كند؟ ‏يا به بیان ساده تر ایا (س,0)توقف مي کند یا ‏خير؟ ‏توريتكٌ و تمامي رشته هاي رراست و اكوريتمي براي ان وجود ندارد. ‏حال تعریف رسمي تر مسئله را بیان مي 

صفحه 6:
اس ویو فرض كنيد شته أي باشد كه ماشين وري الحم ‎0s‏ ۳ 0 را توصیف عي كفدو مد رشته ‎Jl esl‏ الفباي ()باشد. ‎om‏ که )و سبه صورت رشته ‎Igo 4,05) rey‏ دراه حل توق ‎Sey LL‏ به ‎ul pli‏ كه براي هر وه سبه ي زی ‎wo mil Ly‏ gO Oww ‏خم‎ an ‏و اگر 0روي «عمل کند متوقف مي شود.‎ 

صفحه 7:
ده ۲ هم چنین در حالت دیگر 0 ‏سیه‎ | we اگر 0روي سعمل کند توقف نمي کند. در اينجا ووو بوهر دو وضعيت نهايي 

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

صفحه 9:
اگر مسئله توقف تصمیم پذیر بود انوقت هر زبان بازگشتي برشمردني بازگشتي مي بو تصميم يذير بود. 

صفحه 10:
زبانهاي با زگشتي برشمردني مشخص کردیم که براي زبانهاي بازگشتي برشمردني الگوریتم عضویت وجود ندارد. زبانهاي بازگشتي بر شمردني انقدر كلي هستند که هر سوالي در مورد 

صفحه 11:
| قضيه 3-12 قعیین اینکه0<()را است يا 

صفحه 12:
مستئله عضویت براي زيانهاي بازگشتي دهیم. فرض کنید که ماشین روتینگ 0 و رشته ي 2 7 داریم.میتوان 0را به صورت زیر تغییر داد. ابتدا ‎D‏ ورودي خود را در قسمت خاصي از يوار اخيره مي كتديبعد آپی نویر سور ۲ و اکر و فقط اگر ورودي ذخيره شده سود انرا میپذیرد.اینکار را با تغییر و ایجاد يك ماشین )براي هرب به 

صفحه 13:
۱ ادامه 5 حال فرض کنیدرکه اگر الكوريتمي أي نه گیریرد | است ‎ugh as by‏ اک رگ sil ‏لعزم‎ ‎we‏ توليد مي انوقت مي ‎Bo Lee‏ زا روت هم بكداريم سكل است که براي ‎a we D2 Ss‏ ید كه ‎Gh‏ اس شین توریب و و شد ‎aoe‏ عضویت براي هر زبان و بازگشتي د ‎acu, J J‏ أست كد فيلا كركتيم.ننيجه مي يريم كه ‏مسسمئله 6-(5)).ا غیرنصمیم پذیر است. 

صفحه 14:
تورینگ باشد.انگاه اینکه ایا(0)ا منناهي است با ‎row!‏ 

صفحه 15:
مسئله ي توقف (سم,0)را در نظر بگیرید.از0 ماشین تورینگ ديگري مأنند 0*میسازیم که کار زیر را انجام مي دهد.ابتدا تمامي وضعیت هاي توقف به گونه اي تغیر داده مي شوند که اگر هريك دستيايي شود انوقت تمام ورودي تو, 0*پذیرفته مي شود.این کار را مي توان با اجازه دادن به هر پيکربندي توقف که داد.سپس ماشین آولیه به گونه اي تغییر داده مي شود که ماشین جدید 0*ابندا مر را روي نوار خود توليد مي كند و بعد 7-7 

صفحه 16:
a ‏ده‎ به عیارت ديكر حركات انجام شده توسط 0*+پس از وى نوار خودرئوشت همان ‎wilS,>‏ است "28 نجام ميدهد أكر در ييكربندي 4و شروع كند أكر توقف كند إنوقت 5*0 دريك وضعيت نهايي توقف مي بنای رین ‎(Ow)‏ نوقف کند انوقت 0*براي ‎eli‏ ‏ورود: به بك وضعیت يي مي رسد.1 ‎(Dw)‏ 2995« نکند )”هم توقف نمي و نابراین چیزی را نمیپذیرد. ‎a‏ عبارت دیگر0* یا زبان نامتناهي۶+ را میپذیرد و ‏يا تیان هتی0 را متدترد. 

صفحه 17:
۱ ادامه [_ مسائل غیر تصمیم پذيري براي زبانهاي مستقل از متن وجود دارند. براي نمونه الگورينمي براي تصمیم گيري در مورد اينكه'يك كرام ر مسقل از مقن كل است وجود ندارندو هم جنين در زبانهاي مستقل از متن الكوريتمي براي تصميم كيري در مورد اينكه 9(<۵ظ),ا!/(0)بايراي هر و69 مستقل از متن وجود ندارد 

صفحه 18:
.1همرلة با جرعبات نمتان دهید که دانلنین ۹0 در قخیه 4212 جک ود اخته مي شود .2 نشان دهيد كه دو مسئله مطرح شده در انتهاي بخش قبلي يعني االف(0)را(حاوي هر رشته با طول پنج است بل( )را(منظم است. تصمیم پذیر هستند. :3فرض كنيد 00و09 ماشينواي تورینگ باشندزنشان دهید که مستله مر ‎vag‏ ‎no fs wand | LC‏ اي کردن اینکه آبا 60(۸۵)راشماره ای با زگشتي برشمردتی است وجود دار :5فرض کنید که ۵ه ررگرامر نامقيدي باشد .یا الگورينمي براي معین کردن اینکه 0(۲) رک( آوجود دار رض كنيد كه 0©يك كرامر نامقيد و ©©يك كرامر منظم اشدرنشان دهيدكه ‎W@e)= 2 0۵۷۵0‏ غير تصميم پذیر است, تشان دهد که سوال تمرين © براي يك ©©ثابت تا زماني که (90) اي نباشد خر تصمیم پذیر است. 

صفحه 19:
۳ tos, اسلاید فصل 12 کتاب مقدمه اي بر مويه زبانها و ماشينها)دكتر ن صراف زاده( مستی- سیده زكيه ‎ee “Lipa‏ شور ” لمعب 

فصل 12 محدوده ي محاسبات الگوريتمي مقدمه ديديم كه ماشينهاي تورينگ چه كارهايي را مي توانند انجام دهند حال ببينيم كه چه كارهايي را نمي توانند انجام دهند براي اينكه بهتر مسئله روشن شود مي توان گفت كه براي زبانه هاي غير بازگشتي هيچ الگوريتمي وجود ندارد البته زبانهاي غير بازگشتي كاربرد علمي بسيار كمي دارند اما مسئله به همين جا ختم نمي شود براي مثال هيچ ال*گوريتمي برا*ي تعيين اينكه يك گرامر مستقل از متن غير گنگ است وجود ندارد قطعا اين مسئله در مطالعه زبانهاي برنامه سازي مهم است. مسائلي كه توسط ماشين تورينك قابل حل نيست اينكه قدرت محاسبه مكانيكي محدود است مسئله پذيرفته شده ايست و مسائلي وجود دارد كه از قدرت يك كامپيوتر خارج است. اانچه براي ما جالب است اينست كه مسائلي هستند كه به روشني و سادگي بيان ميشوند و به نظر مي رسند كه ممكن است راه حل الگوريتمي براي انها باشد اما غير قابل حل توسط كامپيوتر هستند. مثال با گرامر مستقل از متن Gزبان )L(Gگنگ است.اين جمله براي بعضي Gها درست و براي بعضي غلط است. مسئله اينست كه تصميم بگيريم كه براي ‏Gداده شده اين جمله صحيح است يا غلط. در اينجا دامنه اي وجود دارد كه انهم مجموعه تمامي زبانهاي مستقل از متن است. گفتيم كه مسئله اي تصميم پذير است كه مسئله ي توقف در ماشين تورينگ اين مسئله انست كه ماشين تورينگ Mو ورودي wداده شده اند. سوال اينست كه ايا ماشين Mبا ورودي ‏wتوقف مي كند؟ يا به بيان ساده تر ايا ()M,wتوقف مي كند يا خير؟ در اينجا دامنه ي مسئله تمام ماشين هاي تورينگ و تمامي رشته هاي wاست و اگوريتمي براي ان وجود ندارد. حال تعريف رسمي تر مسئله را بيان مي تعريف 1-12 فرض كنيد كه Wmرشته اي باشد كه ماشين تورينگ ) M=(Q,Σ,Γ,δ,q0,□,Fرا توصيف مي كندو wرشته اي از الفباي Mباشد. فرض مي كنيم كه Wmو wبه صورت رشته ايي از 0و 1باشند.راه حل مسئله توقف يك ماشين تورينگ به نام Hاست كه براي هر Wmوwمحاسبه ي زير را انجام مي دهد: ‏q 0 Wm w ├* x1 qy x2 و اگر Mروي wعمل كند متوقف مي شود. ادامه هم چنين در حالت ديگر ‏q 0 Wm w ├ * y1 qn y2 اگر Mروي wعمل كند توقف نمي كند. در اينجا qnو qyهر دو وضعيت نهايي ‏Hهستند. قضيه 1-12 ماشين تورينگ Hكه مانند تعريف 1-12عمل كند وجود ندارد و بنا براين مسئله غير تصميم پذير است. قضيه 2-12 اگر مسئله توقف تصميم پذير بود انوقت هر زبان بازگشتي برشمردني بازگشتي مي بود. نتيجتا مسئله ي توقف غير تصميم پذير بود. مسائل غير تصميم پذير براي زبانهاي بازگشتي برشمردني مشخص كرديم كه براي زبانهاي بازگشتي برشمردني الگوريتم عضويت وجود ندارد. زبانهاي[ بازگشتي بر شمردني انقدر كلي هستند كه هر سوالي در مورد انهاغير تصميم پذير است. قضيه 3-12 ِفرض كنيد كه Gيك گرامر نامقيد باشد انوقت مسئله تعيين اينكه L(G)=Øاست يا خير،غير تصميم پذير است. اثبات قضيه 3-12 مسئله عضويت براي زبانهاي بازگشتي برشمردني را به اين مسئله كاهش مي دهيم. فرض كنيد كه ماشين روتينگ Mو رشته ي w را داريم.ميتوان Mرا به صورت زير تغيير داد. ابتدا Mورودي خود را در قسمت خاصي از نوار ذخيره مي كند.بعد هرگاه اماده ي ورود به يك وضعيت نهائي شد نگاه ميكند و اگر و فقط اگر ورودي ذخيره شده ‏wبود انرا ميپذيرد.اينكار را با تغيير δو ايجاد يك ماشين Mwبراي هر wبه ادامه حال فرض كنيد كه اگر الگوريتمي مانندA براي تصميم گيري در مورد اينكهL(G)=Ø است يا نه داريم .اگر Tالگوريتمي باشد كه با ان Gwرا توليد مي كنيم انوقت مي توانيم Tو Aرا روي هم بگذاريم.شكل 1-12تورينگي است كه براي هر Mو wبه ماميگويد كه wدر) L(Mاست يا خير.اگر چنين ماشين تورينگي وجود داشته ياشد الگوريتم عضويت براي هر زبان بازگشتي برشمردني داريم كه مغادير بانتيجه اي است كه قبال گرفتيم.نتيجه مي گيريم كه مسئله L(G)=Øغيرتصميم پذير است. قضيه 4-12 فرض كنيد كه Mيك ماشين تورينگ باشد.انگاه اينكه ايا) L(Mمتناهي است يا خير ،غيرتصميم پذير است. اثبات قضيه 4-12 مسئله ي توقف ()M,wرا در نظر بگيريد.ازM ماشين تورينگ ديگري مانند *Mميسازيم كه كار زير را انجام مي دهد.ابتدا تمامي وضعيت هاي توقف Mبه گونه اي تغير داده مي شوند كه اگر هريك دستيابي شود انوقت تمام ورودي توسط *Mپذيرفته مي شود.اين كار را مي توان با اجازه دادن به هر پيكربندي توقف كه به يك وضعيت نهايي برود انجام داد.سپس ماشين اوليه به گونه اي تغيير داده مي شود كه ماشين جديد *Mابتدا w را روي نوار خود توليد مي كند و بعد ادامه به عبارت ديگر حركات انجام شده توسط *Mپس از اينكه wرا روي نوار خود نوشت همان حركاتي است كه Mانجام ميدهد اگر در پيكربنديq0w شروع كند.اگر توقف كند انوقت *Mدريك وضعيت نهايي توقف مي كند. بنابراين اگر( )M,wتوقف كند انوقت *Mبراي تمام ورودي ها به يك وضعيت نهايي مي رسد.اگر( )M,wتوقف نكند *Mهم توقف نمي كند و بنابرا[ين چيزي را نميپذيرد. به عبارت ديگر *Mيا زبان نامتناهي +Σرا ميپذيرد و يا زبان متناهي Øرا ميپذيرد. ادامه مسائل غير تصميم پذيري براي زبانهاي مستقل از متن وجود دارند. براي نمونه الگوريتمي براي تصميم گيري در مورد اينكه يك گرامر مستقل از متن گنگ است وجود ندارندو هم چنين در زبانهاي مستقل از متن الگوريتمي براي تصميم گيري در مورد اينكه ‏L(G1)∩L(G2)=Øبراي هرG1و G2مستقل از متن وجود ندارد فصل تمرينات12 1.همراه با جزئيات نشان دهيد كه ماشين *Mدر قضيه 4-12چگونه ساخته مي شود. 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خالي نباشد غير تصميم پذير است. گروه1 اساليد فصل 12كتاب مقدمه اي بر نظريه زبانها و ماشينها)دكتر عبدالحسين صراف زاده( سرنا يزداني شورمستي-سيده زكيه عيسي زاده-شقايق ديلمي