Domáca úloha #3 z IB107
(3 body)
Z nasledujúcich množín si vyberte dve a dokážde o nich že sú rekurzívně spočetné (Teda nájdite vyčísliteľnú funkciu f i takú, že dom(fi) = Ai alebo range(fi) = Ai).
Ai = {i G N | 3n G N : 2n G dom(ifi) A 2n + 1 G dom(ipi)} A2 = {i G N j 3n G N : </?j(n) = 1 V *fii(n) ^ n} - Teda </?j nie je identita A3 = {i G N j 3a, b G N : a G range((fi) A 6 G range((fi) A a = 62} A4 = {i G N j a G range(ip2i) pre pevne dané a}
Pokiaľ budete písať nejaké while programy, môžete používať všetky makrá definované na prednáške a cvičeniach.
Bonus
(1 bod)
Rozhodnite a dokážte, či existuje množina F, ktorá nie je rekurzívně spočetná ale má aspoň dve dizjunktné rekurzívně spočetné podmnožiny Fi, F2 ktoré nie sú rekurzívně a aspoň jednu nekonečnú rekurzívnu podmnožinu F% ktorá má neprázdny prienik s F± a F2. (Teda F\ n F2 = 0, F$ D F\ 7^ 0 a F3nF2^ 0)