funktsioonidest operaatori abil saadud funktsioonid on samuti (*)-arvutatavad. Anname ka sellise teoreemi tõestamise idee, mis ütleb, et iga osaliselt rekursiivne funktsioon on Turingi mõttes arvutatav ehk antud juhul (*)-arvutatav. 1. Osaliselt rekursiivsed funktsioonid. Operaatori µ abil saadud funktsioonide (*)-arvutatavus. Enne põhiosa juurde asumist toome sisse mõned vajalikud definitsioonid. Definitsioon 1.1. ([1], 9) Algfunktsioonideks nimetatakse järgmisi naturaalarvulisi funktsioone: Funktsioone nimetatakse valikufunktsioonideks. Definitsioon 1.2. ([1], 10) Funktsioon on avaldatud funktsioonide ja kaudu asendusskeemi abil, kui . Definitsioon 1.3. ([1], 10) Funktsioon on avaldatud funktsioonide ja (konstandi ja funktsiooni ) kaudu lihtrekursiooniskeemi abil, kui juhul või Definitsioon 1.4. ([1], 22) Olgu funktsioon määratud hulga mingil alamhulgal ja olgu . Kirjutame
1. Kompleksarvu mõiste imaginaarosad on vastavalt võrdsed: a + ib = c + id a = c ja b = d . Võrrandite lahendamine on sundinud matemaatikuid võtma kasutusele uusi arvuhulki. Näiteks võrrandil 8 + x = 3 ei ole naturaalarvulisi lahendeid. Sellel võrrandil on aga Näide 1. Kontrollime, kas arvude 4 - 5i, -3i + 2, -6i + 4 ja 2 - 3i seas on võrdseid. Esimese ja kolmanda arvu reaalosa 4 (seega võrdsed), kuid nende arvude olemas lahend täisarvude hulgas Ä. Täisarvude hulgas ei ole lahendeid näiteks
.,xn} f: A A on ühskohaline kõikjal määrat' naturaalarvuline f.-n. f on Nn tükki. Kõigi ühekohaliste naturaalarvuliste f.-nide arv aga on |N| |N| - kontiinumi võimsus. Kõigil arvutatavatel f.-nidel on Gödeli numbrid need aga on naturaalarvud seega ei saa kõik f.-nid olla lahenduvad. · Turingi masina peatumine (kas A(x) = lõpmatus?) · Hiberti kümnes probleem kas täisarvuliste kordajatega polünoomi P(x1,..,xn) korral on võrrandil P(x1,..,xn) = 0 naturaalarvulisi lahendeid? · Posti vastavuse probleem Posti vastavuse probleem: korteezhid tähestikus : = (1,..,n) = (1,..,n) Kas leidub indeksite jada i1,..,ik nii, et 1i1i2..ik = 1i2..in See ei ole lahenduv. Kui see oleks lahenduv, leiduks predikaat 1, kui leidub P(,) = 0, kui ei leidu Teatud juhul on lahenduv. = {a,b} = {aa,bb,abb} = {aab,ba,b} Ning indeksid <2;1;3> aabbabb = aabbab Osade korral aga eksisteerib.
tusega. Kui suurus a on kas + v~ oi - v~oi (st, et suuruse absoluutv¨a¨artus on +), siis k~oneldakse l~ opmatust piirv¨ a¨ artusest. 41 Jada piirv¨a¨ artuse m~ oiste on erijuht funktsiooni piirv¨a¨artuse m~oistest (kui valida x0 = + ja kasutada l¨ ahenemiseks vaid argumendi naturaalarvulisi v¨a¨artusi). L~oplike suuruste a ja x0 korral kehtib j¨ argnev v¨aide. Lause 1. Arv a on funktsiooni f (x) piirv¨a¨artuseks kohal x0 parajasti siis, kui suvalise arvu > 0 korral leidub selline arv = (), et 0 < |x - x0 | < |f (x) - a| < . T~ oestus. Lause t~ oesus j¨ areldub Definitsioonist 1 ja arvu a -¨
annaabi.ee 
