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

صفحه 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‏ شور ” لمعب