Rekursiooni- ja keerukusteooria harjutus 3
Millised neljast omadusest:
on rekursiivne
on rekursiivselt loenduv
omab rekursiivst täiendit
omab rekursiivselt loenduvat täiendit
on antud hulkade põhjal
1. A = {x | x on paarisarv}
2. B = {x | x on väiksem kui 100}
3. C = {x | x on algarv}
4. D = {x | Wx on tühi}
5. E = {x | Wx sisaldab vähemalt 3 elementi}
Lahendus
Alusteooria
Hulk on rekursiivselt invariantne, kui iga bijektiivse ja rekursiivse junktsiooni f korral, kui hulgal A on omadus P, siis ka hulgal
f (a) on omadus P.
1 , kui x A
Hulk A on rekursiivne, kui tal leidub karakteristlik funktsioon Xa x .
0 , kui x A
Hulk A on rekursiivselt loenduv, kui A või leidub totaalne arvutataf funktsioon f , nii et A range f .
annaabi.ee 
