"lihtrekursiooniskeemi" - 1 õppematerjal

Operaatori μx(n 1) abil (*)-arvutatavatest funktsioonidest 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: Arvutame järjestikku , , ................................................ Kui saame mingi arvu korral, , siis lõpetame ja väljastame . Definitsioon 1.5