14
hisoblanuvchi funksiyalar
sinfi ham ―
-aniqlanuvchi funksiyalar‖
xossalariga oʻxshash xossalarga ega edi.
1936-yilda A.Chyorch va S.Klini tomonidan
bu ikkita sinf bir xil
sinf ekanligi isbotlandi, ya‘ni
har qanday
-aniqlanuvchi funksiya
umumrekursiv funksiya boʻlishi va har qanday
umumrekursiv funksiya
-aniqlanuvchi funksiya ekanligi tasdiqlandi.
1936 yilda Chyorch quyidagi tezisni e‘lon qildi: har qanday intuitiv
effektiv
(samarali)
hisoblanuvchi
funksiyalar
umumrekursiv
funksiyalardir.
Bu teorema emas, balki tezisdir: tezis tarkibida
intuitiv aniqlangan
effektiv hisoblanuvchi funksiya tushunchasi, aniq matematik atamalarda
aniqlangan
umumrekursiv
funksiya
tushunchasi
bilan
aynan
tenglashtirilgan. Shuning uchun bu tezisni isbotlash mumkin emas.
Ammo Chyorch va boshqa olimlar tomonidan bu tezisni quvvatlovchi
koʻp dalillar koʻrsatildi.
