Ü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. 1 , kui x A Hulk A on rekursiivne, kui tal leidub karakteristlik funktsioon Xa x . ...
Juba aastatel 1915-1919, s.t enne Churchi teesi ja lahenduvuse täpse mõiste sissetoomist tõestasid Löwenheim ja Skolem, et kui lubada predikaatarvutuses ainult objektide omaduste, mitte aga nendevaheliste suhete kirjeldamist, s.o kasutada ainult ühekohalisi predikaate, siis selline loogikasüsteem on lahenduv. Mis puutub loogika ja arvutiteaduse suhetesse, siis see on märksa laiem, kui algoritmi- ja rekursiooniteooria problemaatika. Viimane pakub peamist huvi loogikasiseselt ja filosoofilisest vaatepunktist, praktilise arvutiteaduse seisukohalt on lahendamatuse eri astmeid ja lahendamatuse struktuuri uurivad algoritmiteooria sfäärid suhteliselt vähem huvitavad. Iga konkreetse probleemiklassi lahendatavuse/mittelahendatavuse probleem ise on arvutiteaduse jaoks siiski väga oluline, sest lahendatavuse tõestamine annab "kõrvalproduktina" enamasti kaasa lahendusalgoritmi enda. 2.5
annaabi.ee 
