У теорији израчунљивости, примитивне рекурзивне функције су класе функција које су дефинисане користећи примитивну рекурзију и композицију као централне операције и представљају строги подскуп укупних µ-рекурзивних функција (µ-рекурзивне функције се такође називају и "парцијално рекурзивне"). Примитивне рекурзивне функције чине важан камен темељац на путу ка пуној формализацији израчунљивости. Ове функције су такође важне у теорији доказа.
Већина функција која се нормално проучава у теорији бројева су примитивно рекурзивне. На пример: сабирање, дељење, факторијел, експоненцијална функција и n-та основна су све примитивно рекурзивне функције. Такве су и многе апроксимације стварне вредности функција. У ствари, тешко је пронаћи рекурзивну функцију која није примитивно рекурзивна, мада неке такве функције постоје (видети одељак о ограничењима испод). Скуп примитивних рекурзивних функција је познат као ПР у рачунској теорији комплексности.
Дефиниција Примитивне рекурзивне функције су међу функцијама теорије бројева, то су функције које сликају из природних бројева (ненегативни цели) {0, 1, 2, ...} у природне бројева. Ове функције подразумевају n аргумената за неки природан број n и називају се n-арне.
Основне примитивне рекурзивне функције дате овим аксиома: Константна функција: 0-арна константа функција 0 је примитивно рекурзивна. Функција наслеђивања: 1-арна функција наслеђивања S, која враћа наследника свог аргумента (види Пеанове аксиоме), је примитивна рекурзивна. То је S(k) = k + 1 Пројекција функција: За сваки n≥1 и сваки i из скупа 1≤i≤n, n-арна пројекција функција пројекције Pin, која враћа свој i-ти аргумент, је примитивно рекурзивна функција. Сложеније примитивне рекурзивне функције се могу добити применом операција датим овим аксиомима: Слагање(Композиција): Дато је f, k-арна примитивна рекурзивна функција, и k m-арних примитивно рекурзивних функција g1,...,gk, слагање f са g1,...,gk, односно m-арна функција је такође примитивно рекурзивна. Примитивна рекурзија: Дато је f, k-арна примитивна рекурзивна функција, и g,(k+2)-арна примитивна рекурзивна функција, (k+1)-арна функција h је дефинисана као примитивна рекурзија f и g, односно функција h је примитивно рекурзивна када и
Примитивне рекурзивне функције су основне функције и оне добијене од основних функција применом ових операција коначан број пута.
Улога функције пројекције Функције пројекција се могу користити да би се избегла очигледна крутост у смислу арности функција које су дате горе; помоћу композиције са различитим функцијама пројекције, могуће је да прође подскуп аргумената једне функције на другу функцију. На пример, ако су g и h 2-арне примитивне рекурзивне функције онда
је такође примитивна рекурзивна. Једна формална дефиниција користећи пројекцију функција је
Претварање предиката у нумеричке функције У неким срединама је природно да се размотре примитивне рекурзивне функције које узимају као улаз оне ниске које имају микс бројева са истинитосним вредностима { t= тачно, f= нетачно}, или да се производе тачне вредности као излази. Ово се може постићи кроз идентификовање истинитосних вредности са бројевима на било који фиксни начин. На пример, уобичајено је да се идентификују истинитосне вредности t са бројем 1 и истинитосне вредности f са бројем 0. Када је та идентификација направљен, карактеристична функција скупа А, што буквално враћа 1 или 0, може бити посматрана као предикат који говори да ли је број у предвиђеном скупу А. Таква идентификација предиката са нумеричким функцијама ће се претпоставити до краја овог чланка.
Дефиниција програмског језика Пример примитивног рекурзивног програмском језика је онај који садржи основне аритметичке операторе (нпр. + и −, или САБИРАЊЕ и ОДУЗИМАЊЕ), условљење и поређење (IF-THEN, EQUALS, LESS-THAN), и for петље, као што је основно за петље, где постоји позната или израчуната горња граница за све петље (FOR и FROM 1 до n, без i без n модификованог од стране тела петље). Нема контролне структуре веће општости, као што су while петљe или АКО-ОНДА плус ГОТО, које се примају у примитивном рекурзивном језику. Петља Дагласа Хофстатера је таква и код Гедела, Есхера, Баха. Додавање необавезне петље (WHILE, GOTO) чини језик делимично рекурзивним, или Тјуринг-комплетним; Петље су као и сви програмски језици који раде у реалном времену.
Произвољни компјутерски програми, или Тјурингове машине, не могу уопште да се анализирају да виде да ли се зауставља или не (на обуставу проблема). Међутим, све примитивне рекурзивне функције се заустављају. Ово није контрадикција; примитивни рекурзивни програми нису произвољна подгрупа свих могућих програма, конструисаних тако да су специфични за анализирање.
Примери Већина бројевних-теоријских функција које се дефинишу помоћу рекурзије на једној променљивој су примитивно рекурзивне. Основни примери укључују сабирање и скраћено одузимање функције.
Сабирање Интуитивно, сабирање се може рекурзивно дефинисати са правилима: збир(0,x)=x, збир(n+1,x)=збир(n,x)+1. Да бисте уклопили ово у строгу примитивну рекурзивну дефиницију, дефинише се: збир(0,x)=P11(x) , збир(S(n),x)=S(P23(n, збир(n,x), x)). Овде је S(n) "следбеник од n" (i.e., n+1), P11 је функција идентитета, и P23 је функција пројекције узима 3 аргумента и враћа други. Функције f и g прописане су горњој дефиницији примитивне рекурзивне операције редом P11 слагање од S иP23.
Одузимање Зато што примитивне рекурзивне функције користе природне бројеве, уместо целих бројева, а природни бројеви се не затварају под одузимањем, функција скраћеног одузимања (која се назива "исправно одузимање") је проучавана у овом контексту. Ова ограничена функција одузимања скупа (a, b) [or b ∸ a] враћа b - a ако је ненегативна, у супротном враћа 0.
Функција претходника делује као супротно од функција наследника и рекурзивно је дефинисана правилима: претходник(0)=0, претходник(n+1)=n. Ова правила могу да се конвертују у више формалне дефиниције примитивне рекурзије: претходник(0)=0, претходник(S(n))=P12(n, претходник(n)). Ограничена функција одузимања дефинисана од претходника функционише на начин аналоган начину сабирања дефинисаног од наследника: збир(0,x)=P11(x), збир(S(n),x)=претходник(P23(n, збир(n,x), x)). Имамо скуп(a, b) коме одговара b ∸ a; ради једноставности, редослед аргумената је узет из "стандардне" дефиниције да задовољава захтеве из примитивне рекурзије. То се лако може исправити коришћењем композиције са одговарајућим пројекцијама.
Друге операције са природним бројевима Степеновање и просто тестирање су примитивно рекурзивне. С обзиром на примитивне рекурзивне функције e, f, g, и h, функција која враћа вредност g када e≤f или у супротном вредност h је примитивна рекурзивна.
Операције над целим и рационалним бројевима Коришћењем Геделових бројева, примитивне рекурзивне функције могу се продужити за операцију на другим предметима, као што су цели и рационални бројеви. Ако су цели бројеви кодирани од стране Геделових бројева у стандардном начину, аритметичке операције, укључујући сабирање, одузимање и множење су примитивно рекурзивне. Слично томе, ако су рационалним представљени Геделови бројеви онда операције на терену су све примитивно рекурзивне.
Однос према рекурзивним функцијама Шира класа парцијалних рекурзивних функција је дефинисана увођењем неограниченог оператера претраживања. Употреба овог оператера може да доведе до делимичне функције, то јест, однос са највише једном вредности за сваки аргумент, али не мора имати никакву вредност за било који аргумент (видети Домен). Једна еквивалентна дефиниција каже да је делимична рекурзивна функција она која може да се израчуна на Тјуринговој машини. Укупна рекурзивна функција је парцијална рекурзивна функција која је дефинисана за сваки унос.
Свака примитивна рекурзивна функција је целокупно рекурзивна, али нису све целокупне рекурзивне функције примитивно рекурзивне. Акерманова функција А (м, н) је добро познати пример целокупне рекурзивне функције која није примитивно рекурзивна. Постоји карактеризација примитивних рекурзивних функција као подскуп укупних рекурзивних функција које користе Акерманову функцију. Ова карактеризација наводи да је функција примитивно рекурзивна ако и само ако постоји природан број м такав да се функција може израчунати помоћу Тјурингове машине која се увек зауставља са A(m,n) или са мање корака, где је н збир аргумената примитивне рекурзивне функције.This follows from the facts that the functions of this form are the most quickly growing primitive recursive functions, and that a function is primitive recursive if and only if its time complexity is bounded by a primitive recursive function.
Важна особина примитивних рекурзивних функција је да су оне рекурзивно бројиви подскуп скупа свих укупних рекурзивних функција (која није сама по себи рекурзивно бројива). То значи да постоји једно израчунавање функције f(e,n) тако да: За сваку примитивно рекурзивну функцију g, постоји неко e тако да је g(n) = f(e,n) за свако n, и За свако e, функција h(n) = f(e,n) је примитивно рекурзивна.
Међутим, примитивно рекурзивне функције нису највећи рекурзивно бројиви скуп потпуних израчунљивих функција.
Ограничења Примитивно рекурзивне функције имају тенденцију да одговарају веома блиско нашој интуицији о томе израчунљива функција мора бити. Свакако су почетне функције интуитивно израчунљиве (у њиховој самој једноставности), и две операције којима се може створити нова примитивно рекурзивна функција је такође веома једноставна. Међутим скуп примитивних рекурзивних функција не укључује сваку могућу израчунљиву функцију - то може да се види са варијантом Канторовог дијагоналног аргумента. Овај аргумент даје целокупну израчунљиву функцију која није примитивно рекурзивна. Следи скица доказа: Примитивно рекурзивна функција једног аргумента (тј. унарне функције) може бити рачунски набројана. Ово набрајање користи дефиниције примитивних рекурзивних функција (које су у суштини само изрази са операцијама слагања и примитивне рекурзије као операције и основних примитивних рекурзивних функције као атома), а може се претпоставити да садржи сваку дефиницију једном, иако ће се иста функција десити много пута на листи (јер многе дефиниције дефинишу исту функцију; једноставно компонује се по функцији идентитета која генерише бесконачно много дефиниција једне примитивне рекурзивне функције). То значи да се n-та дефиниција примитивне рекурзивне функције у овом набрајању може ефикасно одредити из n. Заиста, ако неко користи неке Годелове бројеве за кодирање дефиниције као бројева, онда је ово n-та дефиниција на листи обрачуната примитивном рекурзивном функцијом н. Нека fn означава унарну примитивну рекурзивну функцију која је дата овом дефиницијом.
Сада треба дефинисати "оцењивача функције" ev са два аргумента ev(i,j) fi(j). Јасно ev је укупно и за израчунавање, јер једно може ефикасно одредити дефиницију fi, и може бити примитивна рекурзивна функција fi сама укупна и за израчунавање, па fi(j) је увек дефинисано и ефикасно израчуњиво. Међутим дијагонала аргумента ће показати да функција ev два аргумента није примитивно рекурзивна.
Претпоставимо да је ev примитивно рекурзивно, онда унарна функција g која је дефинисана као g(i) S(ev(i,i)) би такође била примитивно рекурзивна, као што је дефинисано у саставу функције слагања и ev. Али онда се g јавља у набрајању, тако да постоји неки број n тако да је g fn. Али g(n) S(ev(n,n)) S(fn(n)) S(g(n)) даје контрадикцију. Овај аргумент се може применити на било коју класу израчунљиве (потпуне) функције које се могу набројати на овај начин, као што је објашњено у чланку машина које се увек заустављају. Имајте на уму, међутим, да парцијалне израчунљиве функције (оне које не морају бити дефинисана за све аргументе) могу изричито бити набројане, на пример пописивање кодирања Тјурингове машине.
Други примери укупних рекурзивних али не примитивних рекурзивних функција су познати: