Rekursiooni- ja keerukusteooria harjutus 3 (1)

Ü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õ
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 .
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 bijektiivne rekursiivne funtsioon B g(a), B range (g f ), kus g f on totaalne arvutatav funktsioon ja annab täpselt B ele- menti. x f (x) annab A elementi, g on totaalne. g saab sisendiks ainult A elemente, seega tulemuseks ainust B elemendid.< Tegemist on rekursiivse funktsiooniga, sest eksisteerib karakteristlik funktsioon 1 , kui x mod 2 0 Xa x . 0 , kui x mod 2 0 Iga rekursiivne funktsioon on ka rekursiivselt loenduv ja tal leidub rekursiivne tä Tegemist on rekursiivse funktsiooniga, sest eksisteerib karakteristlik funktsioon 1 , kui x 100 Xb x . 0 , kui x 100 Iga rekursiivne funktsioon on ka rekursiivselt loenduv ja tal leidub rekursiivne tä Tegemist on rekursiivse funktsiooniga, sest eksisteerib karakteristlik funktsioon 1 , kui y 2, ..., x , nõnda et x mod y 0 Xc x . 0 , muidu Iga rekursiivne funktsioon on ka rekursiivselt loenduv ja tal leidub rekursiivne tä Tegemist on rekursiivselt loenduvat täiendi funktsiooniga. Xd x x Wx pole tühi . D pole rekursiivselt loenduv, millest järeldub et ta pole rekursiivne ega rekursiivne tä Tegemist on rekursiivselt loenduva funktsiooniga. Xe x saame anda vastuse 1 . E pole rekursiivselt loenduv, millest järeldub et ta pole rekursiivne ega rekursiivne täiend funktsioon.