Tyuring mashinasining ishlashi

O'z-o'zini qo'llash muammosi quyidagilardan iborat: har qanday Tyuring mashinasi berilganda, uning o'z-o'zidan qo'llanilishi yoki yo'qligini aniqlaydigan algoritmni ko'rsatish.
Tyuring tezisiga ko'ra, bunday algoritmni Tyuring mashinasi ko'rinishida izlash kerak. Ushbu mashina barcha Tyuring mashinalarining raqam kodlariga tegishli bo'lishi kerak va sinovdan o'tgan mashinalar kodlarini qayta ishlash natijasiga qarab, u turli xil yakuniy konfiguratsiyalarga ega bo'lishi kerak.
Masalan, bu mashinani olaylik T kodga qo'llaniladi n(T * ) . Agar mashina T * o'z-o'zidan qo'llaniladi, keyin mashinaning yakuniy konfiguratsiyasi T shaklga ega a" q0 | B", va agar mashina T * o'z-o'zidan qo'llanilmaydi, keyin mashinaning oxirgi konfiguratsiyasi T shaklga ega a" q0 0B ". Bu yerda a, B, a, B- sozlar.
Teorema O'z-o'zidan qo'llanilishi muammosi algoritm jihatdan yechilmaydi, ya'ni bu masalani yuqoridagi ma'noda hal qiladigan Tyuring mashinasi yo'q.
Teoremadan kelib chiqadiki, o'z-o'zini qo'llash masalasini hal qilishning umumiy algoritmi yo'q. Muayyan holatlarda bunday algoritmlar mavjud bo'lishi mumkin.
Keling, ushbu teorema natijalaridan boshlang'ich so'z uchun qo'llanilishi mumkin bo'lgan muammoning hal qilinmasligini isbotlash uchun foydalanamiz.
Boshlang'ich so'zga qo'llanilishi muammosi quyidagilardan iborat: mashina yordamida algoritm yaratish T va so'z X o'rnatish bo'lardi, tegishli mashina T aytmoqchi X yoki yo'q (aks holda to'xtatish muammosi).
Tyuring mashinalari nuqtai nazaridan, o'z-o'zidan qo'llanilishi muammosini shakllantirishga o'xshab, bu muammo quyidagicha tuzilgan: shaklning barcha so'zlariga mos keladigan mashinani qurish mumkinmi? n(T) 0 X , qayerda T tasodifiy mashina, X ixtiyoriy so'z bo'lib, agar mashina T so'z uchun amal qiladi X a" q0 |B" , va agar mashina T so'zga taalluqli emas X , yakuniy konfiguratsiyaga olib keladi a" q0 0B" . Bu yerda a" , B" va a", B"- ixtiyoriy so'zlar.
Teorema Boshlang'ich so'zga qo'llanilishi muammosi algoritmik jihatdan yechilmaydi, ya'ni bu masalani yuqoridagi ma'noda hal qiladigan Tyuring mashinasi yo'q.
O'z-o'zini qo'llash muammosi uchun yuqorida aytib o'tilganidek, birinchi dastlabki qadam raqamlashdir. Shuning uchun quyida ushbu masala algoritmlar va uning uchta asosiy algoritmik modellari uchun izchil ko'rib chiqiladi va hal qilinadi.