1. Rekursiv, rekursiv sanaluvchi to‘plam tushunchalari. Rekursiv va rekursiv sanaluvchi to‘plamlar xossalari. Post teoremasi

Muammoli masala va topshiriqlar

1. 
   tub sonlar kvadratlari to‘plami effektiv rekursiv sanaluvchi to‘plam bo‘lish yoki bo‘lmasligini aniqlang.
   
2. 
   Algoritm tushunchasi ta’rifini ishlab chiqish jarayonida qanday qiyinchiliklar yuzaga kelishini o‘ylab ro‘ring.
   
3. 
   Gilbertning «Koeffitsiyentlari butun sonlardan iborat bo‘lgan har qanday algebraik tenglamaning butun sonli yechimi mavjudmi?» kabi ifodalanuvchi 10- muammosini yechish algoritmi mavjud yoki mavjud emasligini o‘rganing.
   

Mustaqil ishlash uchun savollar

1. 
   Algoritm tushunchasi ta’rifini ishlab chiqish jarayonida qanday qiyinchiliklar yuzaga kelishi mumkin?
   
2. 
   Yechuvchi protsedura nima?
   
3. 
   Yechilish muammosi deganda nimani tushunasiz?
   
4. 
   Algoritmning intuitiv ta’rifini bilasizmi?
   
5. 
   Algoritmning qanday xarakterli xususiyatlari bor?
   
6. 
   Algoritmning diskretligi, determinatsiyalanuvchanligi, qadamlarining elementarligi va natijaviyligi deganda nimani tushunasiz?
   
7. 
   Rekursiv va rekursiv sanaluvchi to‘plamlar nima?
   
8. 
   Rekursiv to‘plam bilan effektiv rekursiv sanaluvchi to‘plamlar o‘rtasida qanday munosabatlar bor?
   
9. 
   Algoritm tushunchasiga aniqlik kiritishning uch asosiy yo‘nalishini ta’riflay olasizmi?
   
10. 
    Effektiv hisoblanuvchi funksiya deganda nimani tushunasiz?
    
11. 
    -aniqlanuvchi funksiya va hisoblanuvchi funksiya bir-biridan qanday farqlanadi?
    
12. 
    Umumrekursiv funksiya nima?
    
13. 
    A.Chyorch va S.Klini erishgan natijalarni bilasizmi?
    
14. 
    Chyorch tezisini ifodalay olasizmi?
    
15. 
    K.Gyodel natijalarini bilasizmi?
    
16. 
    Tyuring tezisi nima?
    
17. 
    Qanday funksiya Tyuring bo‘yicha hisoblanuvchi funksiya deb ataladi?
    
18. 
    Tyuring mashinalari deganda nimani tushunasiz?
    
19. 
    E.Post qanday natijalar olgan?
    
20. 
    Normal algoritmlar nima?
    
21. 
    Yu.V.Matiyasevich va G.V.Chudnovskiylar Gilbertning 10- muammosini qanday hal qilishgan?
    
22. 
    Nega Chyorch bilan Tyuring tezislari ekvivalent?