"asendusskeemi" - 1 õppematerjal

Operaatori μx(n 1) abil (*)-arvutatavatest funktsioonidest saadud funktsioonide (*)-arvutatavus

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 ja ütleme, et funktsioon on avaldatud funktsiooni kaudu, rakendades argumendile -operaatorit, kui Funktsiooni võib arvutada järgmise algoritmi järgi: