Rekursiooni- ja keerukusteooria harjutus 3
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 .
Kas antud hulkade omadused on rekursiivselt invariantsed:
1. Sisaldab vähemalt 3 elementi
Olgu f bijektiine ja rekursiivne, kui A sisaldab vähemalt 3 elementi, siis f (A) samuti tänu bijektiivsusele
2. On tühi
samuti tänu bijektiivsusele
3. On lõputu
2 Margus Martsepp, Rekursiooni- ja keerukusteooria harjutus 3.nb
samuti tänu bijektiivsusele
4. On rekursiivselt loenduv (RL)
A on rekursiivselt loendub hulk, ta on kas tühi (siis 3.) või leidub totaalne funktsioon f , nii et A range f . Olgu g suvaline
annaabi.ee 
