Rekursiooni- ja keerukusteooria harjutus 3
Ülessanne
Kas antud hulkade omadused on rekursiivselt invariantsed:
1. Sisaldab vähemalt 3 elementi
2. On tühi
3. On lõputu
4. On rekursiivselt loenduv (RL)
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.
annaabi.ee 
