1. Ieskats rekursīvajās funkcijās
Rekursīvās funkcijas (no vēlās lat.val. recursio – atgriešanās), nosaukums, kas iestiprinājies zem viena no visvairāk izplatītākajiem variantiem, vispārēju saprotot ar to aritmētisku algoritmu, t.i., tādu algoritmu, kura gala dotie ir naturālo skaitļu sistēmas, bet iespējamie izmantošanas rezultāti ir naturālie skaitļi. Rekursīvās funkcijas ievadīja S.K. Klinī 20.gs. 30.-tajos gados, kas, savukārt, balstījās uz Ž.Erbrana, K. Gedeļa u.c. matemātiķu pētījumiem.
Katra rekursīvā funkcija tiek noteikta pēc gala sistēmas vienādojumiem, tās nozīme tiek noteikta ar šo vienādojumu sistēmu palīdzību pēc noteikti formulētiem likumiem, turklāt tādā veidā, ka gala rezultātā dotās rekursīvās funkcijas noteikšanai rodas noteikta tipa algoritms.
Aritmētiskās funkcijas, kuru nozīmes noteikšanai ir kaut kādi algoritmi, ir pieņemts saukt par izskaitļojamām. Izskaitļojamām funkcijām matemātikā ir ļoti liela nozīme. Līdz ar to, ja algoritma izpratnei netiks dota noteikta jēga, izskaitļojamās funkcijas izpratne kļūs neskaidra. Rekursīvās funkcijas jau pēc sava rakstura ir izskaitļojamās funkcijas. Zināmā mērā patiess ir arī pretējs: ir nopietni iemesli, lai domātu, ka matemātiskā rekursivitātes izpratne pēc sava rakstura ir tiešs ekvivalents uz nedaudz neskaidras izskaitļojamības izpratnes fona. Piedāvājums uzskatīt izskaitļojamības izpratni, pēc apjoma sakrītošu ar rekursivitātes izpratni, rekursīvās funkcijas teorijā ir Čērča tēze, kura tiek piedēvēta amerikāņu matemātiķim A.Čērčam, pirmoreiz (20.gs. 30.tajos gados), kas it kā noformulēja un izvirzīja šo priekšlikumu. Čērča tēzes pieņemšana ļauj piedēvēt izskaitļojamās aritmētiskās funkcijas izpratnei tiešu matemātisku jēgu un nodot so izpratni izpētei ar tiešo metožu palīdzību.
Rekursīvās funkcijas ir daļējas funkcijas, t.i., funkcijas, kuras ne vienmēr ir noteiktas. Lai pasvītrotu šo apstākli, bieži vien kā sinonīmu lieto terminu „daļēji rekursīvās funkcijas”. Rekursīvās funkcijas, kas ir nosakāmas, pateicoties jebkuriem argumentiem, sauc par vispārīgi rekursīvām funkcijām.
Rekursīvo funkciju noteikšanai var būt sekojoša forma. Tiek fiksēts neliels ārkārtēji vienkāršu izejfunkciju skaits, kuras tiek izskaitļotas augstākminētajā intuitīvā izpratnē (funkcija, kas vienāda ar nulli, vienību pieskaitoša funkcija, funkcijas, kas izslēdz no naturālo skaitļu sistēmas locekli ar doto numuru); tiek fiksēts neliels operāciju skaits virs funkcijām, kas pārved izskaitļojamās funkcijas atkal izskaitļojamās funkcijās (primitīvās rekursijas un minimizācijas operatori). Tad rekursīvās funkcijas nosaka kā funkcijas, kuras iespējams dabūt no dotām beigu skaitļa rezultātā, izmantojot augstāk minētās operācijas.
Operators saskaņo funkcijas f no n ar mainīgāmfunkcijām g1, . . ., gn no m ar izmainītu funkciju f no m mainīgu ar tādu, kas jebkuriem naturāliem skaitļiem x1,.., xm.
h(x1,.., xm) @ f (g1(x1,.., xm), …, gm(x1,.., xm))
(te un turpmāk noteikta vienādība @ nozīmē, ka abas izteiksmes, kas saistītas ar to, ir apdomātas vienlaicīgi un apdomāšanas gadījumā tam ir viena un tā pati nozīme).
Primitīvās rekursijas operators saskaņo funkcijas f no n mainīgas un g no n+2 izmainītām funkciju h no n+1 izmainītu ar tādu, kas jebkuriem naturāliem skaitļiem x1,.., xn, y.
h(x1,.., xn,0) @ f(x1,.., xn),
h(x1,.., xn, y + 1) @ g(x1,.., xn, y, h(x1,.., xn, y )).
Minimizācijas operatorssaskaņo funkcijas f no n mainīgasfunkciju h no n mainīgas, tādas, kas jebkuriem naturāliem skaitļiem x1,.., xn
h(x1,.., xn) @ f(x1,.., xn-1, y)
kur y ir tāds, ka f(x1,.., xn-1, y-1) noteikti un atšķirti no xn, а f(x1,.., xn, y) noteikta un vienāda xn turpretim, ja y ar norādītajām īpašībām neeksistē, tad h(x1,.., xn) ir uzskatāms par nenoteiktu.
Nozīmīga loma rekursīvo funkciju teorijā ir primitīvi rekursīvajai funkcijai – rekursīvajai funkcijai, kas rodas no sākumfunkcijām beigu skaitļa rezultātā, izmantojot tikai primitīvās rekursijas operatorus. Tie veidu pašu klases vispārrekursīvu funkciju daļu. Pēc Klini teorēmas par normālu rekursīvās funkcijas formuvar tikt norādītas konkrētas primitīvi rekursīvās funkcijas U ar vienu izmaiņu un Tn no n + 2 mainīgām, kas jebkurai rekursīvajai funkcijai j no n mainīgām un jebkuriem naturāliem skaitļiem x1, . . ., xn, kam ir vienādojums j(x1, …, xn) @ U(y), kur y ir mazākais no z skaitļiem, kas Tn(j, x1, …, xn,z) = 0
2. Operācijas ar funkcijām
1. Superpozīcija (kompozīcija)
Divu viena argumenta funkciju kompozīcijas piemērs.
Dotas funkcijas
,
konstruēsim jaunu funkciju
2. Primitīvā rekursija
Vienkāršas rekursijas – faktoriāla funkcijas, piemērs.
Dotas funkcijas , konstruēsim jaunu funkciju pēc šādas shēmas:
Speciālgadījums n=0:
3. Primitīvi rekursīvie operatori
DEFINĪCIJA Funkciju pārveidojumu (operāciju ar funkcijām) sauc par primitīvi rekursīvu operatoru, jas šis pārveidojums jebkuru primitīvi rekursīvu funkciju pārveido par primitīvi rekursīvu (saglabā funkciju primitīvo rekursivitāti).
PIEMĒRI un ir primitīvi rekursīvi pēc definīcijas.
Vai ir vēl kādi interesanti primitīvi rekursīvi operatori? Ir!
1) nosacītās pārejas operators:
dotas divas funkcijas , un predikāts , tad nosacītā pāreja ir funkcija f:
vai
acīmredzami ir primitīvi rekursīva funkcija, ja un ir primitīvi rekursīvas.
2) summas operators:
dota funkcija , definēsim jaunu funkciju g:
Var redzēt, ka
tātad funkcija ir primitīvi rekursīva.
3) reizinājuma operators:
dota funkcija , definēsim jaunu funkciju g:
Var redzēt, ka
tātad funkcija G ir primitīvi rekursīva.
4) ierobežotais minimizācijas operators
( ierobežotais -operators)
No predikāta ar šī operatora palīdzību iegūstam jaunu funkciju f.
PIEMĒRI , tad
Ierobežotais – operators ir primitīvi rekursīvs –
neierobežotais minimizācijas operators( – operators) (nav primitīvi rekursīvs operators)
sauc arī par inversijas operatoru, jo, piemēram, funkcija
ir inversā funkcija attiecībā uz f(x).
PIEMĒRI Dalīšana
5) vienlaicīgās rekursijas operators
Vai visas funkcijas ir primitīvi rekursīvas? Nē, tāpēc, ka funkciju ir nesanumurējami daudz, bet, primitīvi rekursīvu funkciju kopas ir sanumurējama.
Vai visas aprēķināmās (ar algoritma palīdzību) funkcijas ir primitīvi rekursīvas? Nē, kontrpiemērs – Akermana funkcija (izlasīt kaut kur patstāvīgi).
Secinājums – ir jāpaplašina primitīvi rekursīvo funkciju kopa, lai tā būtu precīzi vienāda ar visu aprēķināmo funkciju (to funkciju, kam atbilst algoritmi) kopu.
DEFINĪCIJA Funkciju sauc par daļēji rekursīvu, ja to var iegūt no bāzes funkcijām izmantojot galīgu skaitu superpozīciju, primitīvo rekursiju un – operatoru.
Daļēji rekursīva funkcija var nebūt visur definēta (Tjūringa mašīnas apciklošanās (neapstāšanās) analogs)
-operatora vispārīgā forma:
PIEMĒRS inversā funkcija nav visur definēta.
Ja -operators nav definēts, tad funkcijas aprēķināšana it kā turpinās bezgalīgi.
DEFINĪCIJA Daļēji rekursīvu funkciju sauc par vispārēji rekursīvu, ja tā ir visur definēta.
Čērča tēze Ja funkcija ir aprēķināma ar algoritma palīdzību, tad tā ir daļēji rekursīva.
TEORĒMA Katra daļēji rekursīva funkcija ir aprēķināma pēc Tjūringa
PIERĀDĪJUMS Ir jāpierāda, ka visas bāzes funkcijas un visi primitīvi rekursīvie operatori ir realizējami ar Tjūringa mašīnām.
TEORĒMA Katra funkcija, kas ir aprēķināma pēc Tjūringa ir daļēji rekursīva
PIERĀDĪJUMS Ir jāpierāda, ka katru Tjūringa mašīnam elementāro soli par interpretēt kā dalēji rekursīvu funkciju. Tā kā Tjūringa mašīnas darbība ir elementāro soļu secība, tad rezultāts būs daļēji rekursīvu funkciju kompozīcija, tātad daļēji rekursīva funkcija.