(Ingelesez)Funtzio konputagarriak konputagarritasunaren teoriaren aztergai nagusiak dira. Algoritmoen ideia intuitiboaren formalizazioa dira, hau da, funtzio bat konputagarria da funtzioaren zeregina betetzen duen algoritmoa existitzen bada. Konputagarritasunari buruz eztabaidatzeko erabiltzen dira, Turing makinak bezalako konputazio-eredu zehatzik aipatu gabe. Hala ere, edozein definiziok konputazio-eredu jakin bati egin behar dio erreferentzia.
Funtzio konputagarriaren definizio zehatza eman aurretik, matematikariek "benetan kalkulagarri" (ingelesez, effectively calculable) termino informala erabiltzen zuten. Funtzio horiek "benetan konputagarri" direla esateak ez du esan nahi modu eraginkorrean konputagarriak direnik, hau da, denbora-tarte egokian konputagarriak. Izan ere, forga daiteke "benetan konputagarri" diren funtzio batzuetarako algoritmoak ez direla batere eraginkorrak, funtzioen sarrera-datuak haztearekin batera algoritmoen exekuzio-denbora modu esponentzialean (edo superesponentzialean) hazten delako. Konplexutasun konputazionalaren teoriak modu eraginkorrean exekuta daitezkeen funtzioak aztertzen ditu.
Church-Turing tesiaren arabera, funtzio konputagarriak kalkulu mekanikorako gailu bat erabiliz kalkula daitezkeen funtzioak dira, denbora eta biltegiratze-espazioa kopuru mugagabean izanik. Beste modu batean esanda, tesi horrek dio funtzio bat konputagarria dela baldin eta soilik baldin algoritmo bat existitzen bada. Algoritmoa esaten denean, zera esan nahi da: denbora, arkatzak eta papera kopuru mugagabean izanez gero, pertsona batek segitzeko moduko urrats-segida.
Funtzio konputagarrien multzoan konplexutasun konputazionalaren teoria abstraktu bat definitzeko Blum-en axiomak erabil daitezke. Konplexutasun konputazionalaren teorian, funtzio konputagarri baten konplexutasuna zehaztearen problema funtzio-problema (ingelesez, function problem) gisa ezagutzen da.
Funtzio baten konputagarritasuna nozio informala da. Hori deskribatzeko modu bat honakoa da: funtzio bat konputagarria da haren balioa prozedura baten bidez lor badaiteke. Zehaztasun handiagoz, funtzio bat konputagarria da, baldin eta soilik baldin zenbaki arrunten k-kotea emanda balioa itzuliko duen prozedura existitzen bada. Definizio horrekin bat etorriz, artikulu honetan ontzat ematen da funtzio konputagarriek zenbaki arrunten kopuru finitua har dezaketela parametro moduan eta zenbaki arrunt bakarra itzuli emaitza moduan.[1][2][3]
Deskribapen informal horretaz gain, hainbat definizio matematiko formal existitzen dira, haien artean baliokideak direnak. Hona hemen konputazio-eredu horietako batzuk:
Eredu horiek funtzioak, sarrera datuak eta irteera modu desberdinean adierazten badituzte ere, haietako edozein biren arteko itzulpena egin daiteke, eta, beraz, eredu guztiek funtsean funtzio-klase bera deskribatzen dute. Funtzio horiei "errekurtsibo" esan ohi zaie, "konputagarri" termino informaletik bereizteko[4]; bereizketa hori Kleene eta Gödelen artean 1934an izandako eztabaida batean sortu zen.[5]
Adibidez, funtzio konputagarriak funtzio errekurtsibo orokor moduan formaliza daitezke, hau da, sarrera moduan zenbaki arrunten n-koteak hartu eta emaitza moduan zenbaki arrunta itzultzen duten funtzio partzial gisa (goian bezala). Funtzio partzialen klaserik txikiena da eta bertan daude funtzio konstantea, ondorengoa eta proiekzio-funtzioak. Konposizioarekiko, funtzio errekurtsibo primitiboarekiko eta μ eragilearekiko itxia da.
Baina, funtzio konputagarriak beste modu honetan ere formaliza daitezke: Turingen makina baten edo erregistro-makina baten moduko konputazio-agente baten bidez kalkula daitezkeen funtzioak dira. Formalki, funtzio partzial bat kalkula daiteke, propietate hauek dituen programa informatiko bat existitzen bada:
Funtzio konputagarrien oinarrizko ezaugarria honakoa da: funtzioa nola kalkulatu behar den adierazten duen prozedura finitu bat (algoritmo bat) existitu behar du. Arestian aipatutako konputazio-ereduak prozeduraren interpretazio desberdinak dira, hau da, prozedura bat zer den eta nola erabiltzen den azaltzeko modu desberdinak, baina propietate komun asko dituzte.
Endertonek 1977an honako ezaugarriak aipatu zituen (Turing-ek 1936an eta Rogers-ek 1967an zerrendatu zituztenen antzekoak):
Endertonek, hiru ezaugarri horiek horrela argitu zituen:
Laburbilduz, funtzio bat konputagarria da, baldin:
Konplexutasun konputazionalaren teoriak exekuzioa arrakastatsua izan dadin denbora edo espazioa mugatuta duten funtzioak aztertzen ditu.
Zenbaki arrunten A multzoa konputagarria dela esaten da (sinonimoak: errekurtsiboa, erabakigarria) f funtzio konputagarri eta osoa existitzen bada, non n zenbaki arrunt ororentzat zera betetzen den: A multzoan badago orduan f(n) = 1 da, eta A-n ez badago, orduan f(n) = 0.
Zenbaki arrunten multzo bat modu konputagarrian zenbakigarria dela esaten da (sinonimoak: modu errekurtsiboan zenbakigarria, erdierabakigarria) baldin f funtzio konputagarri bat existitzen bada, non zera betetzen den: n zenbaki ororentzat f(n) definituta dago baldin eta soilik baldin n multzoko elementua bada. Beraz, multzo bat modu konputagarrian zenbakigarria da baldin eta soilik baldin funtzio konputagarriren baten definizio-eremuan badago. Zenbakigarri terminoa erabiltzen da, honakoak baliokideak direlako zenbaki osoen B azpimultzo ez-huts baterako:
B multzoa f funtzioaren helburu-multzoa bada, orduan funtzioa B-ren zerrendatze baten moduan ikus daiteke, f(0), f(1), ... zerrendan B-ren elementu guztiak agertuko baitira.
Zenbaki arrunten gaineko matematika-erlazio oro zenbaki arrunten sekuentzia finituen multzo batekin identifika daitekeenez, erlazio konputagarriaren eta modu konputagarrian zenbakigarria den erlazioaren nozioak multzoetarako ere defini daitezke.
Informatikan, konputagarritasunaren teorian, lengoaia formalak erabiltzea ohikoa da. Alfabetoa multzo bat da. Alfabetoko hitz bat alfabetoko sinboloen sekuentzia finitu bat da; sinbolo bera behin baino gehiagotan erabil daiteke. Adibidez, karaktere-kate (string) bitarrak, {0, 1} alfabetoan osatutako hitzak dira. Lengoaia bat alfabeto jakin batekin osa daitezkeen hitz guztien multzoaren azpimultzoa da. Adibidez, zehazki hiru 1eko dituzten karaktere-kate bitar guztien multzoa lengoaia bat da alfabeto bitarrean.
Hitz jakin bat lengoaian dagoen erabakitzeak duen zailtasun-maila lengoaia formalen funtsezko propietatea da. Lengoaia bat konputagarria dela esaten da (sinonimoak: errekurtsiboa, erabakigarria) baldin f funtzio konputagarri bat existitzen bada, non alfabetoko w hitz ororentzat honakoa betetzen den: hitza lengoaian badago orduan f(w) = 1 da eta ez badago f(w) = 0 da. Hala, lengoaia bat konputagarria dela esaten da, edozein hitz emanda lengoaiakoa den ala ez zuzen erabakitzeko gai den prozedura bat existitzen bada.
Lengoaia bat modu konputagarrian zenbakigarria da (sinonimoak: modu errekurtsiboan zenbakigarria, erdierabakigarria) baldin f funtzio konputagarria existitzen bada non honakoa betetzen den: f(w) definituta dago baldin eta soilik baldin w hitza lengoaian badago. Zenbakigarri terminoak modu konputagarrian zenbakigarriak diren zenbaki arrunten multzoetan erabiltzen den terminoaren jatorri bera du.
Funtzio hauek konputagarriak dira:
f eta g konputagarriak badira, f + g, f * g, funtzioak eta baita max(f,g), min(f,g), arg max{y<=f(x)} etab. konputagarriak dira.