Funtzio konputagarri

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.

Sarrera 

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.

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

Deskribapen informal horretaz gain, hainbat definizio matematiko  formal existitzen dira, haien artean baliokideak direnak. Hona hemen konputazio-eredu horietako batzuk:

 Turing makinak
 Funtzio errekurtsibo orokorrak (μ-errekurtsiboak)
 Lambda kalkulua (λ kalkulua)
 Post-en makinak (Post-en Turing makinak eta etiketa-makinak).
 Erregistro-makinak

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; bereizketa hori Kleene eta Gödelen artean 1934an izandako eztabaida batean sortu zen.

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:

  funtzioa definituta badago, orduan programari sarrera moduan  emanez gero, exekuzioa amaitu eta ordenagailuaren memorian  balioa gordeko da.
  funtzioa ez badago definituta, orduan programari sarrera moduan  emanez gero, haren exekuzioa ez da inoiz amaituko.

Funtzio konputagarrien ezaugarriak 
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):

 "Prozedurak agindu zehatzak izan behar ditu (i.e. programa bat), luzera finitua izango duena." Hala, funtzio konputagarri orok programa finitu bat izan behar du, funtzioa nola kalkulatu behar den argi azaltzen duena.  Funtzioa kalkulatzea posiblea izango da aginduak exekutatuz; ez da ezer asmatu behar edo ezagutza berezirik izan behar.
 "f funtzioaren definizio-eremuko x k-kote bat emanez gero, urrats diskretuen kopuru finitu baten ondoren, prozedurak amaitu eta f(x) sortu behar du." Horrela, prozedurak aurrera egiten du urratsez urrats, kalkuluen urrats bakoitzean zer egin behar den argi zehazten duten erregelen arabera.  Urrats kopuru finitu baten ondoren funtzioak balioa itzuliko du.
 "Prozedurari f funtzioaren definizio-eremuan ez dagoen x k-kotea ematen bazaio, orduan prozedurak amaierarik gabe eta betiko exekuzioan jarrai lezake, eta inoiz ez gelditu.  Edo urratsen batean trabatuta gera liteke (i.e., aginduren bat ezin da exekutatu), baina ez du saiatu behar x horretarako emaitza bat itzultzen." Hala, x sarrerarako f(x) emaitza aurkitzekotan, balio zuzena izan behar du. Konputazio-agentearentzat ez da beharrezkoa emaitza zuzenak eta okerrak bereiztea. Definizioz, prozedura zuzena izango da baldin eta soilik baldin emaitza bat sortzen badu.

Endertonek, hiru ezaugarri horiek horrela argitu zituen: 

 Prozedurak, teorikoki, nahi adina handiak diren sarrera parametroetarako funtzionatu behar du. Ezin da suposatu sarrerako parametroak tamaina edo kopuru jakin bat baino txikiagoak izango direnik.
 Urrats kopuru finitu bat exekutatu ondoren, prozedurak exekuzioa amaitu behar du emaitza sortzeko, baina gelditu aurretik nahi adina altua den urrats kopurua exekutatzeko prest egonbehar du. Ezin da suposatu denbora jakin bat baino lehen amaituko duenik.
 Prozedura exekutatzen ari den bitartean biltegiratze-espazio kopuru finitua besterik erabiliko ez badu ere, erabiliko duen espazioa ezin zaio mugatu. Suposatzen da prozedura exekutatzen ari den bitartean behar duen biltegiratze-espazio guztia eskura izango duela.

Laburbilduz, funtzio bat konputagarria da, baldin:Konplexutasun konputazionalaren teoriak exekuzioa arrakastatsua izan dadin denbora edo espazioa mugatuta duten funtzioak aztertzen ditu.

Multzoa eta erlazio konputagarriak 
Zenbaki arrunten A multzoa konputagarria dela esaten da (sinonimoak: errekurtsiboa, erabakigarria)  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  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:

  funtzio konputagarri baten definizio-eremua da.
  funtzio konputagarri oso baten helburu-multzoa da.  infinitua bada, orduan funtzioa injektiboa dela suposa daiteke.

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

Lengoaia formalak 
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, } 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  funtzio konputagarri bat existitzen bada, non alfabetoko  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:  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.

Adibideak 
Funtzio hauek konputagarriak dira:

 Definizio-eremu finitua duten funtzioak; adibidez, zenbaki arrunten edozein sekuentzia finitu.
 f funtzio konstanteak, f : Nk → N,  f(n1,...nk) := n.
 Batuketa: f : N2 → N, f(n1,n2) := n1 + n2
 Bi zenbakiren zatitzaile komun handiena
 Bi zenbakiren Bézout koefizientea
 Zenbaki baten faktore den zenbaki lehen txikiena

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.

Erreferentziak

Bibliografia 

  Ash C. J. , J. Knight, Computable Structures and the Hyperarithmetical Hierarchy (Studies in Logic and the Foundation of Mathematics, 2000), p
  Cutland, Nigel. Computability. Cambridge University Press, 1980.
  Cooper, S. B. , 2004. Computability Theory, Chapman & Hall/CRC. 
  Davis, M., ed., 1965. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, New York. Reprint, Dover, 2004. 
  Davis, M., Computability and Unsolvability, 
  Enderton, H.B. Elements of recursion theory.  Handbook of Mathematical Logic (North-Holland 1977) orr. 527–566.
  Enderton, Herbert (2002). A Mathematical Introduction to Logic. USA: Elsevier. p. 209. ISBN 0-12-238452-0.
  Enderton, Herbert (2002). Una introducción matemática a la lógica (Second edición). USA: Elsevier. p. 208,262. ISBN 0-12-238452-0.
  Jack Copeland, B., Carl J. Posy, Oron Shagrir, 2015, Computability: Turing, Gödel, Church, and Beyond , The Mit Press, 
  Rogers, H.  Theory of recursive functions and effective computation (McGraw–Hill 1967).
  Rosenfeld, Ricardo, Jerónimo Irazábal, Computabilidad, complejidad computacional y verificación de programas, : Universidad Nacional de La Plata, 2013. 
  Soare R., Computabilidad y recursión (1995).
  Turing, A. (1937), On Computable Numbers, With an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, Volume 42 (1937), p.230–265. Reprinted in M. Davis (ed.), The Undecidable, Raven Press, Hewlett, NY, 1965.
  Wolper, Pierre. , Introduction à la calculabilité, Chapitres 5 et 6, 3ème édition.
 Zanardini,, Damiano 2015, Teoría de la Computabilidad - De los resultados clásicos al día a día de la Informática.

Ikus, gainera 
 Konputazioaren teoria
 Konputagarritasunaren teoria
 Algoritmo errekurtsibo
 Kalkulua

Kanpo estekak 

   Funtzio errekurtsibo baten baliokidea Turing-makina moduan lortzeko programa konpilatzailea. / A compiler for transforming a recursive function into an equivalent Turing machine

Konputazioaren teoria
Konputagarritasuna
Informatika teorikoa