Primitivna rekurzivna funkcija

U teoriji izračunljivosti, primitivne rekurzivne funkcije su klase funkcija koje su definisane koristeći primitivnu rekurziju i kompoziciju kao centralne operacije i predstavljaju strogi podskup ukupnih µ-rekurzivnih funkcija (µ-rekurzivne funkcije se takođe nazivaju i "parcijalno rekurzivne"). Primitivne rekurzivne funkcije čine važan kamen temeljac na putu ka punoj formalizaciji izračunljivosti. Ove funkcije su takođe važne u teoriji dokaza.

Većina funkcija koja se normalno proučava u teoriji brojeva su primitivno rekurzivne. Na primer: sabiranje, deljenje, faktorijel, eksponencijalna funkcija i n-ta osnovna su sve primitivno rekurzivne funkcije. Takve su i mnoge aproksimacije stvarne vrednosti funkcija. U stvari, teško je pronaći rekurzivnu funkciju koja nije primitivno rekurzivna, mada neke takve funkcije postoje (videti odeljak o ograničenjima ispod). Skup primitivnih rekurzivnih funkcija je poznat kao PR u računskoj teoriji kompleksnosti.

Definicija

Primitivne rekurzivne funkcije su među funkcijama teorije brojeva, to su funkcije koje slikaju iz prirodnih brojeva (nenegativni celi) {0, 1, 2, ...} u prirodne brojeva. Ove funkcije podrazumevaju n argumenata za neki prirodan broj n i nazivaju se n-arne.

Osnovne primitivne rekurzivne funkcije  date ovim aksioma:

1. Konstantna funkcija: 0-arna konstanta funkcija 0 je primitivno rekurzivna.
2. Funkcija nasleđivanja: 1-arna funkcija nasleđivanja S, koja vraća naslednika svog argumenta (vidi Peanove aksiome), je primitivna rekurzivna. To je S(k) = k + 1
3.  Projekcija funkcija: Za svaki n≥1 i svaki i iz skupa 1≤i≤n, n-arna projekcija funkcija projekcije P_iⁿ, koja vraća svoj i-ti argument, je primitivno rekurzivna funkcija.

Složenije primitivne rekurzivne funkcije se mogu dobiti primenom operacija datim ovim aksiomima:

1. Slaganje(Kompozicija): Dato je f, k-arna primitivna rekurzivna funkcija, i k m-arnih primitivno rekurzivnih funkcija g₁,...,g_k, slaganje f sa g₁,...,g_k, odnosno m-arna funkcija $h(x_{1},\ldots ,x_{m})=f(g_{1}(x_{1},\ldots ,x_{m}),\ldots ,g_{k}(x_{1},\ldots ,x_{m}))\,$ je takođe primitivno rekurzivna.
2. Primitivna rekurzija: Dato je f, k-arna primitivna rekurzivna funkcija, i g,(k+2)-arna primitivna rekurzivna funkcija, (k+1)-arna funkcija h je definisana kao primitivna rekurzija f i g, odnosno funkcija h je primitivno rekurzivna kada

   $h(0,x_{1},\ldots ,x_{k})=f(x_{1},\ldots ,x_{k})\,$ i

   $h(S(y),x_{1},\ldots ,x_{k})=g(y,h(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})\,.$

Primitivne rekurzivne funkcije su osnovne funkcije i one dobijene od osnovnih funkcija primenom ovih operacija konačan broj puta.

Uloga funkcije projekcije

Funkcije projekcija se mogu koristiti da bi se izbegla očigledna krutost u smislu arnosti funkcija koje su date gore; pomoću kompozicije sa različitim funkcijama projekcije, moguće je da prođe podskup argumenata jedne funkcije na drugu funkciju. Na primer, ako su g i h 2-arne primitivne rekurzivne funkcije onda

$f(a,b,c)=g(h(c,a),h(a,b))\!$

je takođe primitivna rekurzivna. Jedna formalna definicija koristeći projekciju funkcija je

$f(a,b,c)=g(h(P_{3}^{3}(a,b,c),P_{1}^{3}(a,b,c)),h(P_{1}^{3}(a,b,c),P_{2}^{3}(a,b,c))).$

Pretvaranje predikata u numeričke funkcije

U nekim sredinama je prirodno da se razmotre primitivne rekurzivne funkcije koje uzimaju kao ulaz one niske koje imaju miks brojeva sa istinitosnim vrednostima { t= tačno, f= netačno}, ili da se proizvode tačne vrednosti kao izlazi.. Ovo se može postići kroz identifikovanje istinitosnih vrednosti sa brojevima na bilo koji fiksni način. Na primer, uobičajeno je da se identifikuju istinitosne vrednosti  t sa brojem 1 i istinitosne vrednosti f sa brojem 0. Kada je ta identifikacija napravljen, karakteristična funkcija skupa A, što bukvalno vraća 1 ili 0, može biti posmatrana kao predikat koji govori da li je broj u predviđenom skupu A. Takva identifikacija predikata sa numeričkim funkcijama će se pretpostaviti do kraja ovog članka.

Definicija programskog jezika

Primer primitivnog rekurzivnog programskom jezika je onaj koji sadrži osnovne aritmetičke operatore (npr. + i −, ili SABIRANjE i ODUZIMANjE), uslovljenje i poređenje (IF-THEN, EQUALS, LESS-THAN), i  for petlje, kao što je osnovno za petlje, gde postoji poznata ili izračunata gornja granica za sve petlje (FOR i FROM 1 do n, bez i bez n modifikovanog od strane tela petlje). Nema kontrolne strukture veće opštosti, kao što su while petlje ili AKO-ONDA plus GOTO, koje se primaju u primitivnom rekurzivnom jeziku. Petlja Daglasa Hofstatera je takva i kod Gedela, Eshera, Baha. Dodavanje neobavezne petlje (WHILE, GOTO) čini jezik delimično rekurzivnim, ili Tjuring-kompletnim; Petlje su kao i svi programski jezici koji rade u realnom vremenu.

Proizvoljni kompjuterski programi, ili Tjuringove mašine, ne mogu uopšte da se analiziraju da vide da li se zaustavlja ili ne (na obustavu problema). Međutim, sve primitivne rekurzivne funkcije se zaustavljaju. Ovo nije kontradikcija; primitivni rekurzivni programi nisu proizvoljna podgrupa svih mogućih programa, konstruisanih tako da su specifični za analiziranje.

Primeri

Većina brojevnih-teorijskih funkcija koje se definišu pomoću rekurzije na jednoj promenljivoj su primitivno rekurzivne. Osnovni primeri uključuju sabiranje i skraćeno oduzimanje funkcije.

Sabiranje

Intuitivno, sabiranje se može rekurzivno definisati  sa pravilima:

zbir(0,x)=x,

zbir(n+1,x)=zbir(n,x)+1.

Da biste uklopili ovo u strogu primitivnu rekurzivnu definiciju, definiše se:

zbir(0,x)=P₁¹(x) ,

zbir(S(n),x)=S(P₂³(n, zbir(n,x), x)).

Ovde je S(n) "sledbenik od n" (i.e., n+1), P₁¹ je funkcija identiteta, i P₂³ je funkcija projekcije uzima 3 argumenta i vraća drugi. Funkcije f i g propisane su gornjoj definiciji primitivne rekurzivne operacije redom P₁¹ slaganje od S iP₂³.

Oduzimanje

Zato što primitivne rekurzivne funkcije koriste prirodne brojeve, umesto celih brojeva, a prirodni brojevi se ne zatvaraju pod oduzimanjem, funkcija skraćenog oduzimanja (koja se naziva "ispravno oduzimanje") je proučavana u ovom kontekstu. Ova ograničena funkcija oduzimanja skupa (a, b) [or b ∸ a] vraća b - a ako je nenegativna, u suprotnom vraća 0.

Funkcija prethodnika deluje kao suprotno od funkcija naslednika i rekurzivno je definisana pravilima:

prethodnik(0)=0,

prethodnik(n+1)=n.

Ova pravila mogu da se konvertuju u više formalne definicije primitivne rekurzije:

prethodnik(0)=0,

prethodnik(S(n))=P₁²(n, prethodnik(n)).

Ograničena funkcija oduzimanja definisana od prethodnika funkcioniše na način analogan načinu sabiranja definisanog od naslednika:

zbir(0,x)=P₁¹(x),

zbir(S(n),x)=prethodnik(P₂³(n, zbir(n,x), x)).

Imamo skup(a, b) kome odgovara b ∸ a; radi jednostavnosti, redosled argumenata je uzet iz "standardne" definicije da zadovoljava zahteve iz primitivne rekurzije. To se lako može ispraviti korišćenjem kompozicije sa odgovarajućim projekcijama.

Druge operacije sa prirodnim brojevima

Stepenovanje i prosto testiranje su primitivno rekurzivne. S obzirom na primitivne rekurzivne funkcije e, f, g, i h, funkcija koja vraća vrednost g kada e≤f ili u suprotnom vrednost h je primitivna rekurzivna.

Operacije nad celim i racionalnim brojevima

Korišćenjem Gedelovih brojeva, primitivne rekurzivne funkcije mogu se produžiti za operaciju na drugim predmetima, kao što su celi i racionalni brojevi. Ako su celi brojevi kodirani od strane Gedelovih brojeva u standardnom načinu, aritmetičke operacije, uključujući sabiranje, oduzimanje i množenje  su primitivno rekurzivne. Slično tome, ako su racionalnim predstavljeni Gedelovi brojevi onda operacije na terenu su sve primitivno rekurzivne.

Odnos prema rekurzivnim funkcijama

Šira klasa parcijalnih rekurzivnih funkcija je definisana uvođenjem neograničenog operatera pretraživanja. Upotreba ovog operatera može da dovede do delimične funkcije, to jest, odnos sa najviše jednom vrednosti za svaki argument, ali ne mora imati nikakvu vrednost za bilo koji argument (videti Domen). Jedna ekvivalentna definicija kaže da je delimična rekurzivna funkcija ona koja može da se izračuna na Tjuringovoj mašini. Ukupna rekurzivna funkcija je parcijalna rekurzivna funkcija koja je definisana za svaki unos.

Svaka primitivna rekurzivna funkcija je celokupno rekurzivna, ali nisu sve celokupne rekurzivne funkcije primitivno rekurzivne. Akermanova funkcija A (m, n) je dobro poznati primer celokupne rekurzivne funkcije koja nije primitivno rekurzivna. Postoji karakterizacija primitivnih rekurzivnih funkcija kao podskup ukupnih rekurzivnih funkcija koje koriste Akermanovu funkciju. Ova karakterizacija navodi da je funkcija primitivno rekurzivna ako i samo ako postoji prirodan broj m takav da se funkcija može izračunati pomoću Tjuringove mašine koja se uvek zaustavlja sa A(m,n) ili sa manje koraka, gde je n zbir argumenata primitivne rekurzivne funkcije.

Važna osobina primitivnih rekurzivnih funkcija je da su one rekurzivno brojivi  podskup skupa svih ukupnih rekurzivnih funkcija (koja nije sama po sebi rekurzivno brojiva). To znači da postoji jedno izračunavanje funkcije f(e,n) tako da:

• Za svaku primitivno rekurzivnu funkciju g, postoji neko e tako da je g(n) = f(e,n) za svako n, i
• Za svako e, funkcija h(n) = f(e,n) je primitivno rekurzivna.

Međutim, primitivno rekurzivne funkcije nisu najveći rekurzivno brojivi skup potpunih izračunljivih funkcija.

Ograničenja

Primitivno rekurzivne funkcije imaju tendenciju da odgovaraju veoma blisko našoj intuiciji o tome izračunljiva funkcija mora biti. Svakako su početne funkcije intuitivno izračunljive (u njihovoj samoj jednostavnosti), i dve operacije kojima se može stvoriti nova primitivno rekurzivna funkcija je takođe veoma jednostavna. Međutim skup primitivnih rekurzivnih funkcija ne uključuje svaku moguću izračunljivu funkciju - to može da se vidi sa varijantom Kantorovog dijagonalnog argumenta. Ovaj argument daje celokupnu izračunljivu funkciju koja nije primitivno rekurzivna. Sledi skica dokaza:

Primitivno rekurzivna funkcija jednog argumenta (tj. unarne funkcije) može biti računski nabrojana. Ovo nabrajanje koristi definicije primitivnih rekurzivnih funkcija (koje su u suštini samo izrazi sa operacijama slaganja i primitivne rekurzije kao operacije i osnovnih primitivnih rekurzivnih funkcije kao atoma), a može se pretpostaviti da sadrži svaku definiciju jednom, iako će se ista funkcija desiti mnogo puta na listi (jer mnoge definicije definišu istu funkciju; jednostavno komponuje se po funkciji identiteta koja generiše beskonačno mnogo definicija jedne primitivne rekurzivne funkcije). To znači da se n-ta definicija primitivne rekurzivne funkcije u ovom nabrajanju može efikasno odrediti iz n. Zaista, ako neko koristi neke Godelove brojeve za kodiranje definicije kao brojeva, onda je ovo n-ta definicija na listi obračunata primitivnom rekurzivnom funkcijom n. Neka fn označava unarnu primitivnu rekurzivnu funkciju koja je data ovom definicijom.

Sada treba definisati "ocenjivača funkcije" ev sa dva argumenta ev(i,j) = f_i(j). Jasno ev je ukupno i za izračunavanje, jer jedno može efikasno odrediti definiciju f_i, i može biti primitivna rekurzivna funkcija f_i sama ukupna i za izračunavanje, pa f_i(j) je uvek definisano i efikasno izračunjivo. Međutim dijagonala argumenta će pokazati da funkcija ev dva argumenta nije primitivno rekurzivna.

Pretpostavimo da je ev primitivno rekurzivno, onda unarna funkcija g koja je definisana kao g(i) = S(ev(i,i)) bi takođe bila primitivno rekurzivna, kao što je definisano u sastavu funkcije slaganja i ev. Ali onda se g javlja u nabrajanju, tako da postoji neki broj n tako da je g = f_n. Ali g(n) = S(ev(n,n)) = S(f_n(n)) = S(g(n)) daje kontradikciju.

Ovaj argument se može primeniti na bilo koju klasu izračunljive (potpune) funkcije koje se mogu nabrojati na ovaj način, kao što je objašnjeno u članku mašina koje se uvek zaustavljaju. Imajte na umu, međutim, da parcijalne izračunljive funkcije (one koje ne moraju biti definisana za sve argumente) mogu izričito biti nabrojane, na primer popisivanje kodiranja Tjuringove mašine.

Drugi primeri ukupnih rekurzivnih ali ne primitivnih rekurzivnih funkcija su poznati:

• Funkcija koja ima m u Akermanovoj (m,m) je ukupna unarna rekurzivna funkcija koja nije primitivno rekurzivna.
• Paris-Haringtonova teorema podrazumeva potpunu rekurzivnu funkciju koja nije primitivno rekurzivna. Pošto je ova funkcija motivisana Remzijevom teorijom, ona se ponekad smatra više "prirodnom" od Akermanove funkcije.
• Funkcija Sudan
• Gudstajnova funkcija

Neke uobičajene primitivne rekurzivne funkcije

Sledeći primeri i definicije iz Klinija  (1952). str. 223—231 - mnogi se pojavljuju sa dokazima. Većina se takođe pojavljuje sa sličnim imenima, bilo kao dokaz, ili kao primer, u Bulos-Burges-Džefri 2002 pp. 63-70; dodaju #22 logaritam lo(x, y) ili lg(x, y) u zavisnosti od tačnog izvođenja.

U nastavku smo primetili da primitivne rekurzivne funkcije imaju četiri tipa:

1. Funkcije za kratko: "brojevno-teorijske funkcije" od {0, 1, 2, ...} do {0, 1, 2, ...},
2. predikati: od {0, 1, 2, ...} u vrednosti istinitosti { t= tačno, f= netačno},
3. iskazni veznici: od istinitosnih vrednosti {t,m} do istinitosnih vrednosti {t,f},
4. predstavljanje funkcije: od istinitosnih vrednosti {t,f} do {0, 1, 2, ...}. Mnogo puta predikat zahteva dapredstavlja funkciju za konvertovanje predikatskog izlaza{t,f} do {0, 1} (obratiti pažnju na redosled "t" na "0" i "f" na "1" poklapanje sa ~ SG () definisana ispod). Po definiciji funkcija φ (x) "predstavljanje funkcije" predikata P(x) φ ako uzima samo vrednosti 0 i 1 i proizvodi 0 kada je P tačno ".

U sledećim oznakama " ' ", npr A ', je primitivna oznaka i znači "naslednik", obično misli kao "+1", na primer, a +1 =_def a'. Funkcije 16-20 i #G su od posebnog interesa u vezi sa konverzijom primitivnnog rekurzivnnog predikata, i vađenje njih iz njihovog "aritmetičkog" oblika izraženog preko Godelovih brojeva.

1. Sabiranje: a+b
2. Množenje: a×b
3. Stepenovanje: a^b
4. Faktorijal a! : 0! = 1, a'! = a!×a'
5. Prethodni(a): (Prethodnik ili opadanje): ako je a > 0 onda je a-1 ili 0
6. Pravilno oduzimanje a ∸ b: Ako a ≥ b onda a-b ili 0
7. Minimum(a₁, ... a_n)
8. Maksimum(a₁, ... a_n)
9. Apsolutna razlika: | a-b | =_def (a ∸ b) + (b ∸ a)
10. ~sg(a): NIJE [signum(a)]: Ako je a=0 onda 1 ili 0
11. sg(a): signum(a): Ako je a=0 onda je 0 ili 1
12. a | b: (a deli b): Ako je b=k×a za neko k onda 0 ili 1
13. Ostatak (a, b): ostatak ako b nije jednako deljivo. Takođe se naziva MOD(a, b)
14. a = b: sg | a - b | (Klinijeva konvencija predstavljala je tačno sa 0 i netačno sa 1; trenutno, posebno u računarima, najčešća konvencija je suprotno, odnosno da predstavlja tačno  sa 1 i netačno sa 0, što iznosi promeni sg u ~sg ovde i u narednom tačke)
15. a < b: sg( a' ∸ b )
16. Pr(a): a je osnovni broj Pr(a) =_def a>1 & NE(postoji c)_1<c<a [ c|a ]
17. p_i:  i+1 osnovni broj

1. (a)_i: eksponent od p_i u a: jedinstveno x takvo da je p_i^x|a & NIJE(p_i^x'|a)
2. lh(a): "dužina" ili broj nenestajanja eksponenta u a
3. lo(a, b): logaritam od a za osnovu b

U daljem tekstu, skraćenica x =_def x₁, ... x_n; indeks se može primenniti ako značenje zahteva.

• #A: Funkcija φ definisana eksplicitno od funkcija Ψ i konstanti q₁, ... q_n je primitvno rekurzivna u Ψ.
• #B: Suma Σ_y<z ψ(x, y) i proizvod Π_y<zψ(x, y) su primitivno rekurzivni u ψ.
• #C: Predikat P dobijen zamenom funkcija χ₁,..., χ_m za dotične promenljive predikata Q je primitivno rekurzivna u χ₁,..., χ_m, Q.
• #D: Sledeći predikati su primitivno rekurzivni u Q i R:

• NIJE_Q(x) .
• Q ILI R: Q(x) V R(x),
• Q I R: Q(x) & R(x),
• Q SLEDI R: Q(x) → R(x)
• Q je ekvivalentno sa R: Q(x) ≡ R(x)

• #E: Sledeći predikati su primitivno rekurzivni u predikatu R:

• (Ey)_y<z R(x, y) gde (Ey)_y<z označava "postoji bar jedan y koja je manja od z takva da"
• (y)_y<z R(x, y) gde (y)_y<z označava "za svako y manje od z je tačno"
• μy_y<z R(x, y). Operacija μy_y<z R(x, y) je celovita oblik takozvane minimizirane - ili mi-operacije: definisane kao "najmanja vrednost od y manja od z tako da je R (k, i) tačno; ili z ako ne postoji takva vrednost."

• #F: Definicija slučajeva: Funkcija definisana tako, gde Q1, ..., Qm međusobno isključuju predikate (ili "ψ(x) koje imaju vrednost koja je data prvom tačkom na koju se odnosi), je primitivna rekurzivna u φ₁, ..., Q₁, ... Q_m:

φ(x) =

• φ₁(x) ako Q₁(x) je tačno,
• . . . . . . . . . . . . . . . . . . .
• φ_m(x) ako Q_m(x) je tačno

• φ_m+1(x) u suprotnom

• #G: Ako φ zadovoljava jednakost:

φ(y,x) = χ(y, NIJE-φ(y; x₂, ... x_n ), x₂, ... x_n onda je φ primitivno rekurzivna u χ. "Dakle, u smislu znanja vrednosti NIJE-φ(y; x_{2 to n} ) toka-of-vrednosti funkcija je ekvivalentan znanja sekvence vrednosti  φ(0,x_{2 to n}), ..., φ(y-1,x_{2 to n}) originalne funkcije."

Dodatni primitivni rekurzivni oblici

Neki dodatni oblici rekurzije takođe definiše funkcije koje su, u stvari, primitivno rekurzivne. Definicije u tim oblicima mogu biti lakše pronađene i prirodnije za čitanje ili pisanje. Kurs-vrednosti rekurzije definiše primitivne rekurzivne funkcije. Neki oblici međusobne rekurzije takođe definišu primitivne rekurzivne funkcije.

Funkcije koje se mogu programirati u petlji programskog jezika su potpuno primitivno rekurzivne funkcije. Ovo daje drugačiju karakterizaciju moći ovih funkcija. Glavno ograničenje petlje jezika, u poređenju sa Tjuring-kompletnim jezikom, jeste da u petlji jezika broj puta da se svaka petlja pokrene naveden je pre nego što se petlja pokrene.

Finitizam i doslednost rezultata

Primitivne rekurzivne funkcije su blisko povezane sa matematičkim finitizmom, i koriste se u kontekstima u matematičkoj logici u kojoj se želi posebno konstruktivan sistem. Primitivni rekurzivna aritmetika (PRA), formalni aksiom sistema za prirodne brojeve i primitivne rekurzivne funkcije na njih, često se koristi u tu svrhu.

PRA je mnogo slabiji nego Peanove aritmetike, koja nije finitistički sistem. Ipak, mnogi rezultati u teoriji brojeva i u teoriji dokaza može se dokazati u PRA. Na primer, Godelova  teorema nepotpunosti može biti formalizovana u PRA, dajući sledeće teoreme:

Ako je T teorija aritmetike zadovoljive određene hipoteze, sa Godelovom rečenicom G_T, onda PRA dokazuje implikaciju Con(T)→G_T.

Slično tome, mnogi od sintaksnih rezultata u teoriji dokaza može se dokazati u PRA, što podrazumeva da postoje primitivni rekurzivne funkcije koje obavljaju odgovarajuće sintaksičke transformacije dokaza.

U teoriji dokaza i teoriji skupova, postoji interesovanje za finitističku doslednost dokazima, to jest, doslednost dokazuje da i sami finitisticalli prihvatljivo. Takav dokaz utvrdi da konzistentnost teorije T podrazumeva doslednost teorije S proizvodnjom primitivni rekurzivnu funkciju koja može da transformiše bilo dokaz o neusklađenosti sa S u dokaz o nedoslednosti iz T. One dovoljan uslov za doslednosti dokaz da bude finitistic je sposobnost da se formalizuje u PRA. Na primer, mnogi doslednost rezultata u teoriji skupova koji su dobijeni prisiljavaju može preoblikovana kao sintaksnih dokaze koji mogu biti formalizovani u PRA.

Istorija

Rekurzivne definicije su se manje više formalno koristile u matematici i ranije, ali izgradnja primitivne rekurzije se pratit unazad do teoreme 126 Ričarda Dedekinda od njegovog Was sind und was sollen die Zahlen? (1888) (1888). Ovaj rad je bio prvi dati dokaz da određena rekurzivna konstrukcija definiše jedinstvenu funkciju.

Primitivna rekurzivna aritmetika je prvo predložena od Toralfa Skolema 1923.

Sadašnju terminologiju je skovao Roza Peter (1934), nakon što je Akerman pokazao 1928. godine da funkcija koja danas nosi ime po njemu nije bila primitivno rekurzivna, događaj koji je naveo potrebu da se preimenuje ono što su do tada nazvali rekurzivnom funkcijom.

Vidi još

• Kurs vrednosti rekurzija
• Grzegorczyk hijerarhija
• Mašina koja uvek staje
• Rekurzija (kompjuterske nauke)
• Primitivno rekurzivno funkcijonalan
• Dupla rekurzija
• Primitivno rekurzivni skup funkcija
• Primitivno rekurzivna redna funkcija

Literatura

• Brainerd, W.S.; Landweber, L.H. (1974). Theory of Computation. Wiley. ISBN 978-0-471-09585-9. 
• Soare, Robert I. (1987). Recursively Enumerable Sets and Degrees. Springer-Verlag. ISBN 978-0-387-15299-8. 
• Stephen Kleene (1952) Introduction to Metamathematics, North-Holland Publishing Company, New York, 11th reprint 1971: (2nd edition notes added on 6th reprint). In Chapter XI. General Recursive Functions §57
• George Boolos, John Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, UK. Cf pp. 70–71.
• Robert I. Soare 1995 Computability and Recursion http://www.people.cs.uchicago.edu/~soare/History/compute.pdf
• Daniel Severin 2008, Unary primitive recursive functions, J. Symbolic Logic Volume 73, Issue 4. стр. 1122–1138 arXiv projecteuclid
• Dragoš M. Cvetković, Slobodan K. Simić (2012). Odabrana poglavlja iz Diskretne Matematike. Beograd: Akademska Misao. ISBN 978-86-7466-059-1.