1 maruza: Algoritm va uning ta’riflari Asosiy savollar

O'z-o'zini qo'llash muammosi quyidagilardan iborat: har qanday Tyuring mashinasi uchun o'zini o'zi qo'llay oladimi yoki yo'qligini aniqlaydigan algoritmni ko'rsatish.
Tyuring tezisiga ko'ra, bunday algoritmni Tyuring mashinasi ko'rinishida izlash kerak. Bu mashina barcha Tyuring mashinalari raqamlarining kodlariga qo'llanilishi kerak va sinovdan o'tgan mashinalarning kodlarini qayta ishlash natijalariga qarab, u har xil yakuniy konfiguratsiyaga ega bo'ladi.
Masalan, berilgan mashinani olaylik T kod uchun amal qiladi n(T * ) ... Agar mashina bo'lsa T * o'z-o'zidan qo'llaniladi, keyin mashinaning oxirgi konfiguratsiyasi T shaklga ega a " q 0 | B " va, agar mashina bo'lsa T * o'z-o'zidan qo'llanilmaydi, keyin mashinaning oxirgi konfiguratsiyasi T shaklga ega a " q 0 0 B. ". Bu yerda a, B, a, B- sozlar.
Teorema O'z-o'zini qo'llash muammosi algoritmik jihatdan hal qilinmaydi, ya'ni yuqoridagi ma'noda bu muammoni hal qiladigan Tyuring mashinasi yo'q.
Teoremadan kelib chiqadiki, o'z-o'zini qo'llash muammosini hal qilishning umumiy algoritmi yo'q. Muayyan holatlarda bunday algoritmlar mavjud bo'lishi mumkin.
Biz bu teorema natijalaridan foydalanib, boshlang'ich so'zni qo'llash muammosining hal qilinmasligini isbotlaymiz.
Bosh so'zni qo'llash muammosi quyidagicha: mashinaga muvofiq algoritm tuzing T va so'z X o'rnatilsa, mashina qo'llaniladi T aytmoqchi X yoki yo'q (aks holda to'xtatish muammosi).
Tyuring mashinalari nuqtai nazaridan, o'z-o'zini qo'llash muammosini shakllantirishga o'xshab, bu muammo quyidagicha ifodalanadi: shaklning barcha so'zlariga mos keladigan mashinani qurish mumkinmi? n(T) 0 X , qaerda T ixtiyoriy mashina, X - o'zboshimchalik bilan so'z va agar mashina bo'lsa T so'z uchun amal qiladi X a " q 0 | B " , va mashina bo'lsa T so'zga taalluqli emas NS , oxirgi konfiguratsiyaga olib keladi a " q 0 0 B " . Bu yerda a ", B" va a ", B"- ixtiyoriy so'zlar.
Teorema Boshlang'ich so'zga qo'llanish muammosi algoritmik jihatdan hal qilinmaydi, ya'ni yuqoridagi ma'noda bu muammoni hal qiladigan Tyuring mashinasi yo'q.
O'z-o'zini qo'llash muammosi uchun yuqorida aytib o'tilganidek, birinchi dastlabki qadam-bu raqamlash. Shuning uchun quyida bu masala algoritmlar va uning uchta asosiy algoritmik modellari uchun izchil ko'rib chiqiladi va hal qilinadi.