"arvutataf" - 1 õppematerjal

Rekursiooni- ja keerukusteooria harjutus 3

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 . 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)