1 maruza: Algoritm va uning ta’riflari Asosiy savollar

O'ZINI QO'LLANISH MUAMMOSI
Tyuring mashinasining ta'rifiga ko'ra, bu uchlik T = , qaerda A - alifbo, Q - mashinaning ichki holati, Q - bir mashinani boshqasidan ajratib turadigan dastur. Umuman (barcha mashinalar uchun) dastur quyidagicha ko'rinishi mumkin:
NS: q i a a j a ® q r a a s a S t a , a = 1, 2, ..., k , qaerda S 1- R, S 2- L., S 3- C . (*)
Bunday holda, ba'zi umumiy alifbolar mavjud deb taxmin qilishimiz mumkin A 0 va Q 0 qahramonlar qaerda yozilgan a va q barcha Tyuring mashinalari uchun. Keyin belgilar q i a, a j a, q r a, a s a, S t a alifbo belgilaridir A 0 va Q 0.
Bu yondashuv barcha Tyuring mashinalarini raqamlashga imkon beradi, ya'ni har bir mashinaga faqat shu mashinaga xos bo'lgan ma'lum raqam (kod) beriladi, bu orqali uni boshqa mashinalardan farqlash mumkin bo'ladi. Bu erda biz raqamlash usullaridan birini ko'rib chiqamiz.
Tyuring mashinalarining Gödel raqamlanishi. Bo'lsin p 1, p 2, p 3 , ... - o'sish tartibidagi oddiy sonlar ketma -ketligi, masalan, 2, 3, 5, 7, 11, 13, ...
Turing mashinasi raqami (*) raqamga qo'ng'iroq qildi
n (T) = .
Misol
Funktsiyani bajaradigan mashina S(x)= x + 1 , alifbo dasturiga ega {0,  } ... Buni hisobga olgan holda ushbu dasturning soni a 0 = 0 , a 1= | raqam bo'ladi:.
n (T) = 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3.
Shubhasiz, hamma natural sonlar Tyuring mashinalari raqamlari emas. Boshqa tomondan, agar n Umumiy alifbolarda qandaydir mashinaning soni, demak, uning dasturini bu raqam bilan aniq tiklash mumkin.
Avtomobil T so'z uchun amal qiladi n(T)(ya'ni o'z raqamining kodiga), o'z-o'zini qo'llash deb ataladi .
O'z-o'zidan ishlaydigan mashinalarni ham, o'z-o'zidan ishlatilmaydigan mashinalarni ham qurish mumkin. Masalan, berilgan misoldagi mashina o'z-o'zidan ishlaydi. Avtomobil T, dasturning o'ng qismlarida (jadval tanasida) uzilish belgisi bo'lmagan, har qanday so'zga va shuning uchun so'zga mos kelmaydi. n(T).