Tyuring mashinasining ishlashi

O'Z-O'ZI QO'LLANISH MUAMMOSI
Turing mashinasining ta'rifiga ko'ra, bu uchlikdir T= , unda A- alifbo, Q- mashinaning ichki holati, Q- bir mashinani boshqasidan ajratib turuvchi dastur. Umumiy holatda (barcha mashinalar uchun) dastur quyidagicha ko'rinishi mumkin:
P: q i a aj a ® q r a a s a S t a , a = 1, 2, …, k , qayerda S1-R, S2-L, S3- C . (*)
Bunday holda, biz bir nechta umumiy alifbolar mavjudligini taxmin qilishimiz mumkin A0 va Q0, qaysi belgilarda yozilgan a va q barcha Turing mashinalari uchun. Keyin belgilar q i a, aj a , q r a, a s a, S t a alifbo belgilaridir A0 va Q0.
Bunday yondashuv barcha Tyuring mashinalarini raqamlash imkonini beradi, ya'ni har bir mashinaga ushbu mashinaga xos bo'lgan ma'lum bir raqamni (kodni) belgilashga imkon beradi, bu orqali uni boshqa mashinalardan ajratib olish mumkin edi. Bu erda raqamlash usullaridan birini ko'rib chiqamiz.
Tyuring mashinalarining Gödel raqamlanishi. Bo'lsin p1, p2, p3 , … - o'sish tartibida joylashtirilgan tub sonlar ketma-ketligi, masalan, 2, 3, 5, 7, 11, 13, ...
Dastur bilan Tyuring mashinasi raqami (*) raqam chaqirdi
n(T) = .
Misol
Funktsiyani amalga oshiradigan mashina S(x)= x + 1 , alifboda dasturga ega {0, } . Buni hisobga olgan holda ushbu dasturning soni a 0 = 0 , a 1= | soni 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 mashinasi raqamlari emas. Boshqa tomondan, agar n ba'zi bir mashinaning soni, umumiy alifbolarda, keyin uning dasturi bu raqamdan noyob tarzda tiklanishi mumkin.
Mashina T so'zga nisbatan qo'llaniladi n(T)(ya'ni o'z raqamingizning kodiga), o'z-o'zidan qo'llaniladigan deb ataladi .
O'z-o'zidan qo'llaniladigan mashinalarni ham, o'z-o'zidan qo'llanilmaydigan mashinalarni ham qurish mumkin. Misol uchun, berilgan misoldagi mashina o'z-o'zidan qo'llaniladi. Mashina T, dasturning to'g'ri qismlarida (jadvalning tanasida) uzilish belgisi bo'lmagan, hech qanday so'z uchun qo'llanilmaydi va shuning uchun so'zga n(T).