Примитивна рекурзивна функција

У теорији израчунљивости, примитивне рекурзивне функције су класе функција које су дефинисане користећи примитивну рекурзију и композицију као централне операције и представљају строги подскуп укупних µ-рекурзивних функција (µ-рекурзивне функције се такође називају и "парцијално рекурзивне"). Примитивне рекурзивне функције чине важан камен темељац на путу ка пуној формализацији израчунљивости. Ове функције су такође важне у теорији доказа.

Већина функција која се нормално проучава у теорији бројева су примитивно рекурзивне. На пример: сабирање, дељење, факторијел, експоненцијална функција и n-та основна су све примитивно рекурзивне функције. Такве су и многе апроксимације стварне вредности функција. У ствари, тешко је пронаћи рекурзивну функцију која није примитивно рекурзивна, мада неке такве функције постоје (видети одељак о ограничењима испод). Скуп примитивних рекурзивних функција је познат као ПР у рачунској теорији комплексности.

Дефиниција

Примитивне рекурзивне функције су међу функцијама теорије бројева, то су функције које сликају из природних бројева (ненегативни цели) {0, 1, 2, ...} у природне бројева. Ове функције подразумевају n аргумената за неки природан број n и називају се n-арне.

Основне примитивне рекурзивне функције  дате овим аксиома:

1. Константна функција: 0-арна константа функција 0 је примитивно рекурзивна.
2. Функција наслеђивања: 1-арна функција наслеђивања S, која враћа наследника свог аргумента (види Пеанове аксиоме), је примитивна рекурзивна. То је S(k) = k + 1
3.  Пројекција функција: За сваки n≥1 и сваки i из скупа 1≤i≤n, n-арна пројекција функција пројекције P_iⁿ, која враћа свој i-ти аргумент, је примитивно рекурзивна функција.

Сложеније примитивне рекурзивне функције се могу добити применом операција датим овим аксиомима:

1. Слагање(Композиција): Дато је f, k-арна примитивна рекурзивна функција, и k m-арних примитивно рекурзивних функција g₁,...,g_k, слагање f са g₁,...,g_k, односно m-арна функција $h(x_{1},\ldots ,x_{m})=f(g_{1}(x_{1},\ldots ,x_{m}),\ldots ,g_{k}(x_{1},\ldots ,x_{m}))\,$ је такође примитивно рекурзивна.
2. Примитивна рекурзија: Дато је f, k-арна примитивна рекурзивна функција, и g,(k+2)-арна примитивна рекурзивна функција, (k+1)-арна функција h је дефинисана као примитивна рекурзија f и g, односно функција h је примитивно рекурзивна када

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

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

Примитивне рекурзивне функције су основне функције и оне добијене од основних функција применом ових операција коначан број пута.

Улога функције пројекције

Функције пројекција се могу користити да би се избегла очигледна крутост у смислу арности функција које су дате горе; помоћу композиције са различитим функцијама пројекције, могуће је да прође подскуп аргумената једне функције на другу функцију. На пример, ако су g и h 2-арне примитивне рекурзивне функције онда

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

је такође примитивна рекурзивна. Једна формална дефиниција користећи пројекцију функција је

$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))).$

Претварање предиката у нумеричке функције

У неким срединама је природно да се размотре примитивне рекурзивне функције које узимају као улаз оне ниске које имају микс бројева са истинитосним вредностима { 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)=P₁¹(x) ,

збир(S(n),x)=S(P₂³(n, збир(n,x), x)).

Овде је S(n) "следбеник од n" (i.e., n+1), P₁¹ је функција идентитета, и P₂³ је функција пројекције узима 3 аргумента и враћа други. Функције f и g прописане су горњој дефиницији примитивне рекурзивне операције редом P₁¹ слагање од S иP₂³.

Одузимање

Зато што примитивне рекурзивне функције користе природне бројеве, уместо целих бројева, а природни бројеви се не затварају под одузимањем, функција скраћеног одузимања (која се назива "исправно одузимање") је проучавана у овом контексту. Ова ограничена функција одузимања скупа (a, b) [or b ∸ a] враћа b - a ако је ненегативна, у супротном враћа 0.

Функција претходника делује као супротно од функција наследника и рекурзивно је дефинисана правилима:

претходник(0)=0,

претходник(n+1)=n.

Ова правила могу да се конвертују у више формалне дефиниције примитивне рекурзије:

претходник(0)=0,

претходник(S(n))=P₁²(n, претходник(n)).

Ограничена функција одузимања дефинисана од претходника функционише на начин аналоган начину сабирања дефинисаног од наследника:

збир(0,x)=P₁¹(x),

збир(S(n),x)=претходник(P₂³(n, збир(n,x), x)).

Имамо скуп(a, b) коме одговара b ∸ a; ради једноставности, редослед аргумената је узет из "стандардне" дефиниције да задовољава захтеве из примитивне рекурзије. То се лако може исправити коришћењем композиције са одговарајућим пројекцијама.

Друге операције са природним бројевима

Степеновање и просто тестирање су примитивно рекурзивне. С обзиром на примитивне рекурзивне функције e, f, g, и h, функција која враћа вредност g када e≤f или у супротном вредност h је примитивна рекурзивна.

Операције над целим и рационалним бројевима

Коришћењем Геделових бројева, примитивне рекурзивне функције могу се продужити за операцију на другим предметима, као што су цели и рационални бројеви. Ако су цели бројеви кодирани од стране Геделових бројева у стандардном начину, аритметичке операције, укључујући сабирање, одузимање и множење  су примитивно рекурзивне. Слично томе, ако су рационалним представљени Геделови бројеви онда операције на терену су све примитивно рекурзивне.

Однос према рекурзивним функцијама

Шира класа парцијалних рекурзивних функција је дефинисана увођењем неограниченог оператера претраживања. Употреба овог оператера може да доведе до делимичне функције, то јест, однос са највише једном вредности за сваки аргумент, али не мора имати никакву вредност за било који аргумент (видети Домен). Једна еквивалентна дефиниција каже да је делимична рекурзивна функција она која може да се израчуна на Тјуринговој машини. Укупна рекурзивна функција је парцијална рекурзивна функција која је дефинисана за сваки унос.

Свака примитивна рекурзивна функција је целокупно рекурзивна, али нису све целокупне рекурзивне функције примитивно рекурзивне. Акерманова функција А (м, н) је добро познати пример целокупне рекурзивне функције која није примитивно рекурзивна. Постоји карактеризација примитивних рекурзивних функција као подскуп укупних рекурзивних функција које користе Акерманову функцију. Ова карактеризација наводи да је функција примитивно рекурзивна ако и само ако постоји природан број м такав да се функција може израчунати помоћу Тјурингове машине која се увек зауставља са A(m,n) или са мање корака, где је н збир аргумената примитивне рекурзивне функције.

Важна особина примитивних рекурзивних функција је да су оне рекурзивно бројиви  подскуп скупа свих укупних рекурзивних функција (која није сама по себи рекурзивно бројива). То значи да постоји једно израчунавање функције 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) = f_i(j). Јасно ev је укупно и за израчунавање, јер једно може ефикасно одредити дефиницију f_i, и може бити примитивна рекурзивна функција f_i сама укупна и за израчунавање, па f_i(j) је увек дефинисано и ефикасно израчуњиво. Међутим дијагонала аргумента ће показати да функција ev два аргумента није примитивно рекурзивна.

Претпоставимо да је ev примитивно рекурзивно, онда унарна функција g која је дефинисана као g(i) = S(ev(i,i)) би такође била примитивно рекурзивна, као што је дефинисано у саставу функције слагања и ev. Али онда се g јавља у набрајању, тако да постоји неки број n тако да је g = f_n. Али g(n) = S(ev(n,n)) = S(f_n(n)) = S(g(n)) даје контрадикцију.

Овај аргумент се може применити на било коју класу израчунљиве (потпуне) функције које се могу набројати на овај начин, као што је објашњено у чланку машина које се увек заустављају. Имајте на уму, међутим, да парцијалне израчунљиве функције (оне које не морају бити дефинисана за све аргументе) могу изричито бити набројане, на пример пописивање кодирања Тјурингове машине.

Други примери укупних рекурзивних али не примитивних рекурзивних функција су познати:

• Функција која има м у Акермановој (m,m) је укупна унарна рекурзивна функција која није примитивно рекурзивна.
• Парис-Харингтонова теорема подразумева потпуну рекурзивну функцију која није примитивно рекурзивна. Пошто је ова функција мотивисана Ремзијевом теоријом, она се понекад сматра више "природном" од Акерманове функције.
• Функција Судан
• Гудстајнова функција

Неке уобичајене примитивне рекурзивне функције

Следећи примери и дефиниције из Клинија  (1952). стр. 223—231 - многи се појављују са доказима. Већина се такође појављује са сличним именима, било као доказ, или као пример, у Булос-Бургес-Џефри 2002 pp. 63-70; додају #22 логаритам lo(x, y) или lg(x, y) у зависности од тачног извођења.

У наставку смо приметили да примитивне рекурзивне функције имају четири типа:

1. Функције за кратко: "бројевно-теоријске функције" од {0, 1, 2, ...} до {0, 1, 2, ...},
2. предикати: од {0, 1, 2, ...} у вредности истинитости { t= тачно, f= нетачно},
3. исказни везници: од истинитосних вредности {t,m} до истинитосних вредности {t,f},
4. представљање функције: од истинитосних вредности {t,f} до {0, 1, 2, ...}. Много пута предикат захтева дапредставља функцију за конвертовање предикатског излаза{t,f} до {0, 1} (обратити пажњу на редослед "t" на "0" и "f" на "1" поклапање са ~ СГ () дефинисана испод). По дефиницији функција φ (x) "представљање функције" предиката P(x) φ ако узима само вредности 0 и 1 и производи 0 када је P тачно ".

У следећим ознакама " ' ", нпр А ', је примитивна ознака и значи "наследник", обично мисли као "+1", на пример, a +1 =_def a'. Функције 16-20 и #G су од посебног интереса у вези са конверзијом примитивнног рекурзивнног предиката, и вађење њих из њиховог "аритметичког" облика израженог преко Годелових бројева.

1. Сабирање: a+b
2. Множење: a×b
3. Степеновање: a^b
4. Факторијал a! : 0! = 1, a'! = a!×a'
5. Претходни(a): (Претходник или опадање): ако је a > 0 онда је a-1 или 0
6. Правилно одузимање a ∸ b: Ако a ≥ b онда a-b или 0
7. Минимум(a₁, ... a_n)
8. Максимум(a₁, ... a_n)
9. Апсолутна разлика: | a-b | =_def (a ∸ b) + (b ∸ a)
10. ~sg(a): НИЈЕ [signum(a)]: Ако је a=0 онда 1 или 0
11. sg(a): signum(a): Ако је a=0 онда је 0 или 1
12. a | b: (a дели b): Ако је b=k×a за неко k онда 0 или 1
13. Остатак (a, b): остатак ако б није једнако дељиво. Такође се назива MOD(a, b)
14. a = b: sg | a - b | (Клинијева конвенција представљала је тачно са 0 и нетачно са 1; тренутно, посебно у рачунарима, најчешћа конвенција је супротно, односно да представља тачно  са 1 и нетачно са 0, што износи промени sg у ~sg овде и у наредном тачке)
15. a < b: sg( a' ∸ b )
16. Pr(a): a је основни број Pr(a) =_def a>1 & НЕ(постоји c)_1<c<a [ c|a ]
17. p_i:  i+1 основни број

1. (a)_i: експонент од p_i у a: јединствено x такво да је p_i^x|a & НИЈЕ(p_i^x'|a)
2. lh(a): "дужина" или број ненестајања експонента у a
3. lo(a, b): логаритам од a за основу b

У даљем тексту, скраћеница x =_def x₁, ... x_n; индекс се може применнити ако значење захтева.

• #A: Функција φ дефинисана експлицитно од функција Ψ и константи q₁, ... q_n је примитвно рекурзивна у Ψ.
• #B: Сума Σ_y<z ψ(x, y) и производ Π_y<zψ(x, y) су примитивно рекурзивни у ψ.
• #C: Предикат P добијен заменом функција χ₁,..., χ_m за дотичне променљиве предиката Q је примитивно рекурзивна у χ₁,..., χ_m, Q.
• #D: Следећи предикати су примитивно рекурзивни у Q и R:

• НИЈЕ_Q(x) .
• Q ИЛИ R: Q(x) V R(x),
• Q И R: Q(x) & R(x),
• Q СЛЕДИ R: Q(x) → R(x)
• Q је еквивалентно са R: Q(x) ≡ R(x)

• #E: Следећи предикати су примитивно рекурзивни у предикату R:

• (Ey)_y<z R(x, y) где (Ey)_y<z означава "постоји бар један y која је мања од z таква да"
• (y)_y<z R(x, y) где (y)_y<z означава "за свако y мање од z је тачно"
• μy_y<z R(x, y). Операција μy_y<z R(x, y) је целовита облик такозване минимизиране - или ми-операције: дефинисане као "најмања вредност од y мања од z тако да је Р (к, и) тачно; или z ако не постоји таква вредност."

• #F: Дефиниција случајева: Функција дефинисана тако, где Q1, ..., Qm међусобно искључују предикате (или "ψ(x) које имају вредност која је дата првом тачком на коју се односи), је примитивна рекурзивна у φ₁, ..., Q₁, ... Q_m:

φ(x) =

• φ₁(x) ако Q₁(x) је тачно,
• . . . . . . . . . . . . . . . . . . .
• φ_m(x) ако Q_m(x) је тачно

• φ_m+1(x) у супротном

• #G: Ако φ задовољава једнакост:

φ(y,x) = χ(y, НИЈЕ-φ(y; x₂, ... x_n ), x₂, ... x_n онда је φ примитивно рекурзивна у χ. "Дакле, у смислу знања вредности НИЈЕ-φ(y; x_{2 to n} ) тока-оф-вредности функција је еквивалентан знања секвенце вредности  φ(0,x_{2 to n}), ..., φ(y-1,x_{2 to n}) оригиналне функције."

Додатни примитивни рекурзивни облици

Неки додатни облици рекурзије такође дефинише функције које су, у ствари, примитивно рекурзивне. Дефиниције у тим облицима могу бити лакше пронађене и природније за читање или писање. Курс-вредности рекурзије дефинише примитивне рекурзивне функције. Неки облици међусобне рекурзије такође дефинишу примитивне рекурзивне функције.

Функције које се могу програмирати у петљи програмског језика су потпуно примитивно рекурзивне функције. Ово даје другачију карактеризацију моћи ових функција. Главно ограничење петље језика, у поређењу са Тјуринг-комплетним језиком, јесте да у петљи језика број пута да се свака петља покрене наведен је пре него што се петља покрене.

Финитизам и доследност резултата

Примитивне рекурзивне функције су блиско повезане са математичким финитизмом, и користе се у контекстима у математичкој логици у којој се жели посебно конструктиван систем. Примитивни рекурзивна аритметика (ПРА), формални аксиом система за природне бројеве и примитивне рекурзивне функције на њих, често се користи у ту сврху.

ПРА је много слабији него Пеанове аритметике, која није финитистички систем. Ипак, многи резултати у теорији бројева и у теорији доказа може се доказати у ПРА. На пример, Годелова  теорема непотпуности може бити формализована у ПРА, дајући следеће теореме:

Ако је Т теорија аритметике задовољиве одређене хипотезе, са Годеловом реченицом G_T, онда ПРА доказује импликацију Con(T)→G_T.

Слично томе, многи од синтаксних резултата у теорији доказа може се доказати у ПРА, што подразумева да постоје примитивни рекурзивне функције које обављају одговарајуће синтаксичке трансформације доказа.

У теорији доказа и теорији скупова, постоји интересовање за финитистичку доследност доказима, то јест, доследност доказује да и сами финитистицалли прихватљиво. Такав доказ утврди да конзистентност теорије Т подразумева доследност теорије С производњом примитивни рекурзивну функцију која може да трансформише било доказ о неусклађености са С у доказ о недоследности из Т. Оне довољан услов за доследности доказ да буде финитистиц је способност да се формализује у ПРА. На пример, многи доследност резултата у теорији скупова који су добијени присиљавају може преобликована као синтаксних доказе који могу бити формализовани у ПРА.

Историја

Рекурзивне дефиниције су се мање више формално користиле у математици и раније, али изградња примитивне рекурзије се пратит уназад до теореме 126 Ричарда Дедекинда од његовог Was sind und was sollen die Zahlen? (1888) (1888). Овај рад је био први дати доказ да одређена рекурзивна конструкција дефинише јединствену функцију.

Примитивна рекурзивна аритметика је прво предложена од Торалфа Сколема 1923.

Садашњу терминологију је сковао Роза Петер (1934), након што је Акерман показао 1928. године да функција која данас носи име по њему није била примитивно рекурзивна, догађај који је навео потребу да се преименује оно што су до тада назвали рекурзивном функцијом.

Види још

• Курс вредности рекурзија
• Grzegorczyk хијерархија
• Машина која увек стаје
• Рекурзија (компјутерске науке)
• Примитивно рекурзивно функцијоналан
• Дупла рекурзија
• Примитивно рекурзивни скуп функција
• Примитивно рекурзивна редна функција

Литература

• 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.