Mavzu: rekursiv va rekursiv sanaluvchi to‘plamlar. Bajardi: Ro`ziyeva M

funksiya bo'lmasa, u holda bu tezisni rad etish mumkin. Lekin, bunday holning mavjudligini hozirgacha hech kim ko'rsata olmagan. Teorema. g ( y |, j ’2,.. . , j t ) prim Bu tezisni isbotlash mumkin emasligi yuqorida aniqlangan edi. Chunki u intuitiv hisoblanuvchi funksiya noqat’iy matematik tushunchasini qat’iy aniqlangan qismiy rekursiv funksiya matematik tushunchasi bilan bog'laydi. Ammo, agar shunday intuitiv hisoblanuvchi funsiya tuzish mumkin bo'lsaki, u o'z navbatida qismiy rekursiv itiv rekursiv (qismiy rekursiv) funksiya va x,,x 2 x n har xil o ‘zgaruvchilar bo'lsin. Agar har bir I (1 < г < к) uchun z t o'zgaruvchi x l , x 2,—, x n о ‘zgaruvchilarning biri bo'lsa, и holda / (x ,, x 2,...,xn) = g ( z l, z 2,...,zk) funksiya ham primitiv rekursiv (qismiy rekursiv) funksiya bo ‘ladi. I s b о t i . z i = xJj (1 < j i < n) bo‘lsin. U holda z; =/"(x i,x2,...,x„) va y/ ( x l , x 2,. ..,х л) = ф (/''(х ,,х 2, . . . , х „ Г ‘к(х], х 2,...,хп)) bo‘ladi. Shunday qilib, у/ funksiyani ф , I" ,...,I” funksiyalardan superpozitsiya amali orqali hosil qilish mumkin, ya’ni Ц/ primitiv rekursiv (rekursiv) funksiya bo‘ladi

funksiya bo'lmasa, u holda bu tezisni rad etish mumkin. Lekin, bunday holning mavjudligini hozirgacha hech kim ko'rsata olmagan. Teorema. g ( y |, j ’2,.. . , j t ) prim Bu tezisni isbotlash mumkin emasligi yuqorida aniqlangan edi. Chunki u intuitiv hisoblanuvchi funksiya noqat’iy matematik tushunchasini qat’iy aniqlangan qismiy rekursiv funksiya matematik tushunchasi bilan bog'laydi. Ammo, agar shunday intuitiv hisoblanuvchi funsiya tuzish mumkin bo'lsaki, u o'z navbatida qismiy rekursiv itiv rekursiv (qismiy rekursiv) funksiya va x,,x 2 x n har xil o ‘zgaruvchilar bo'lsin. Agar har bir I (1 < г < к) uchun z t o'zgaruvchi x l , x 2,—, x n о ‘zgaruvchilarning biri bo'lsa, и holda / (x ,, x 2,...,xn) = g ( z l, z 2,...,zk) funksiya ham primitiv rekursiv (qismiy rekursiv) funksiya bo ‘ladi. I s b о t i . z i = xJj (1 < j i < n) bo‘lsin. U holda z; =/"(x i,x2,...,x„) va y/ ( x l , x 2,. ..,х л) = ф (/''(х ,,х 2, . . . , х „ Г ‘к(х], х 2,...,хп)) bo‘ladi. Shunday qilib, у/ funksiyani ф , I" ,...,I” funksiyalardan superpozitsiya amali orqali hosil qilish mumkin, ya’ni Ц/ primitiv rekursiv (rekursiv) funksiya bo‘ladi