Funtzio konputagarri-en iturria ikusi


{{En}}'''Funtzio konputagarriak''' [[Konputagarritasunaren teoria|konputagarritasunaren teoriaren]] aztergai nagusiak dira. [[Algoritmo|Algoritmoen]] ideia intuitiboaren formalizazioa dira, hau da, funtzio bat konputagarria da funtzioaren zeregina betetzen duen algoritmoa existitzen bada. Konputagarritasunari buruz eztabaidatzeko erabiltzen dira, [[Turingen makina|Turing makinak]] bezalako konputazio-eredu zehatzik aipatu gabe. Hala ere, edozein definiziok konputazio-eredu jakin bati egin behar dio erreferentzia.

== Sarrera ==
[[Fitxategi:Alan_Turing_cropped.jpg|thumb|Alan Turing]]
Funtzio konputagarriaren definizio zehatza eman aurretik, [[Matematikari|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 [[Hazkunde esponentzial|esponentzialean]] (edo superesponentzialean) hazten delako. [[Konplexutasun konputazionalaren teoria|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, <math>f:\mathbb N^k\rightarrow\mathbb N</math> funtzio bat konputagarria da, baldin eta soilik baldin zenbaki arrunten <math>\mathbf x</math>  [[N-kote|k-kotea]] emanda <math>f(\mathbf x)</math>  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.<ref>{{erreferentzia|abizena=J. Ibáñez, A. Irastorza, A. Sánchez|urtea=2000|izenburua=Konputaezintasun Frogapen Batzuk Diagonalizazio Teknika Erabiliz|argitaletxea=UPV/EHU|hizkuntza=eu|url=https://addi.ehu.es/bitstream/handle/10810/18292/PDF%20%20TR11-2000%20-%20Iban%CC%83ezIrastorzaSanchez-Diagonalizazioa-teknikak.pdf?sequence=1&isAllowed=y}}</ref><ref>{{erreferentzia|abizena=Arantza Irastorza, Ana Sánchez, Jesús Ibáñez|urtea=2017|izenburua=Konputagarritasunerako Oinarrizko Teknikak|argitaletxea=UPV/EHU|hizkuntza=eu|url=https://addi.ehu.es/bitstream/handle/10810/22770/TR%2001-2017.pdf?sequence=1}}</ref><ref>{{erreferentzia|abizena=Jesús Ibáñez Martínez-Conde, María Aránzazu Irastorza Goñi, Ana Sánchez Ortega|urtea=1998|izenburua=While programak: konputagarritasun teoria oinarritzeko tresna|argitaletxea=UPV/EHU|hizkuntza=eu|url=https://addi.ehu.es/bitstream/handle/10810/18290/PDF%20%20TR3-1998%20-WhileProgramak.pdf?sequence=1&isAllowed=y}}</ref>

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

* [[Turingen makina|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<ref>{{Erreferentzia|izenburua=Computable Structures and the Hyperarithmetical Hierarchy, Volume 144 - 1st Edition|url=https://www.elsevier.com/books/computable-structures-and-the-hyperarithmetical-hierarchy/ash/978-0-444-50072-4|aldizkaria=www.elsevier.com|sartze-data=2022-12-22}}</ref>; bereizketa hori Kleene eta Gödelen artean 1934an izandako eztabaida batean sortu zen.<ref>{{erreferentzia|izena=Robert I.|abizena=Soare|urtea=1995|izenburua=Computability and Recursion|hizkuntza=en|url=http://www.people.cs.uchicago.edu/~soare/History/compute.pdf}}</ref>

Adibidez, funtzio konputagarriak funtzio errekurtsibo orokor moduan formaliza daitezke, hau da, sarrera moduan zenbaki arrunten [[N-kote|n-koteak]] hartu eta emaitza moduan [[Zenbaki arrunt|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, <math>f:\mathbb N^k\rightarrow\mathbb N</math> funtzio partzial bat kalkula daiteke, propietate hauek dituen programa informatiko bat existitzen bada:

# <math>f(\mathbf x)</math> funtzioa definituta badago, orduan programari sarrera moduan <math>\mathbf x</math> emanez gero, exekuzioa amaitu eta ordenagailuaren memorian <math>f(\mathbf x)</math> balioa gordeko da.
# <math>f(\mathbf x)</math> funtzioa ez badago definituta, orduan programari sarrera moduan <math>\mathbf x</math> 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 ([[Alan Turing|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:{{Zerrenda ordenatua|bere definizio-eremuko sarrera bat emanda eta biltegiratze-espazioa mugagabea dela suposatuz, dagokion irteera eman dezake prozedura bati jarraituz (programa, algoritmoa). Prozedura hori anbiguotasunik gabeko agindu kopuru finitua da;|irteera hori itzultzen du (amaitzen du) urrats kopuru finitu batean; eta|bere definizio-eremukoa ez den sarrera ematen bazaio, zera gertatuko da: edo inoiz ez da gelditzen edo trabatzen da.}}[[Konplexutasun konputazionalaren teoria|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''') {{Math|''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 {{Math|''f''}} funtzio konputagarri bat existitzen bada, non zera betetzen den: n zenbaki ororentzat f(n) definituta dago [[Inplikazio bikoitza|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:

* {{Math|<var>B</var>}} funtzio konputagarri baten definizio-eremua da.
* {{Math|<var>B</var>}} funtzio konputagarri oso baten helburu-multzoa da. {{Math|<var>B</var>}} infinitua bada, orduan [[Funtzio injektibo|funtzioa injektiboa]] dela suposa daiteke.

{{Math|<var>B</var>}} multzoa {{Math|''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.

== Lengoaia formalak ==
Informatikan, [[Konputagarritasunaren teoria|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, {{math|{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 {{Math|''f''}} funtzio konputagarri bat existitzen bada, non alfabetoko {{Math|<var>w</var>}} 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: {{Math|''f''(<var>w</var>)}} 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 konstante|funtzio konstanteak]], ''f'' : '''N'''<sup>''k''</sup> → '''N''',  ''f''(''n''<sub>1</sub>,...''n<sub>k</sub>'') := ''n''.
* [[Batuketa]]: ''f'' : '''N'''<sup>2</sup> → '''N''', ''f''(''n''<sub>1</sub>,''n<sub>2</sub>'') := ''n''<sub>1</sub> + ''n''<sub>2</sub>
* Bi zenbakiren [[zatitzaile komun handiena]]
* Bi zenbakiren [[Bézouten identitate|Bézout koefizientea]]
* Zenbaki baten faktore den [[zenbaki lehen]] txikiena

''f'' eta ''g'' konputagarriak badira, ''f'' + ''g'', ''f'' * ''g, [[Funtzioen konposaketa|<math>\color{Blue} f \circ g</math>]]'' funtzioak eta baita max(f,g), min(f,g), arg max{y<=f(x)} etab. konputagarriak dira.

== Erreferentziak ==
{{erreferentzia zerrenda|30em}}

== Bibliografia ==

* {{En}} Ash C. J. , J. Knight, ''Computable Structures and the Hyperarithmetical Hierarchy'' (Studies in Logic and the Foundation of Mathematics, 2000), p
* {{En}} Cutland, Nigel. ''Computability''. Cambridge University Press, 1980.
* {{En}} [[S. Barry Cooper|Cooper, S. B.]] , 2004. ''Computability Theory'', Chapman & Hall/CRC. {{ISBN|1-58488-237-9}}
* {{En}} [[Martin Davis|Davis, M.]], ed., 1965. ''The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions'', Raven, New York. Reprint, Dover, 2004. {{ISBN|0-486-43228-9}}
* {{En}} Davis, M., ''Computability and Unsolvability'', {{ISBN|978-0486614717}}
* {{En}} Enderton, H.B. Elements of recursion theory.  ''Handbook of Mathematical Logic'' (North-Holland 1977) orr. 527–566.
* {{En}} Enderton, Herbert (2002). ''A Mathematical Introduction to Logic''. USA: Elsevier. p. 209. <small><nowiki>ISBN 0-12-238452-0</nowiki></small>.
* {{Es}} Enderton, Herbert (2002). ''Una introducción matemática a la lógica'' (Second edición). USA: Elsevier. p. 208,262. <small><nowiki>ISBN 0-12-238452-0</nowiki></small>.
* {{En}} Jack Copeland, B., Carl J. Posy, Oron Shagrir, 2015, ''Computability: Turing, Gödel, Church, and Beyond'' , The Mit Press, {{ISBN|9780262527484}}
* {{En}} Rogers, H.  ''Theory of recursive functions and effective computation'' (McGraw–Hill 1967).
* {{Es}} Rosenfeld, Ricardo, Jerónimo Irazábal, ''Computabilidad, complejidad computacional y verificación de programas'', : Universidad Nacional de La Plata, 2013. {{ISBN|978-950-34-0970-1}}
* {{Es}} Soare R., [https://web.archive.org/web/20220331221004/http://www.people.cs.uchicago.edu/~soare/History/compute.pdf Computabilidad y recursión] (1995).
* {{En}} Turing, A. (1937), [https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-42.1.230 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.
* {{En}} 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''. {{ISBN|978-84-941071-7-7}}

== Ikus, gainera ==
* [[Konputazioaren teoria]]
* [[Konputagarritasunaren teoria]]
* [[Errekurtsio|Algoritmo errekurtsibo]]
* [[Kalkulu (matematikaren adarra)|Kalkulua]]

== Kanpo estekak ==

* {{En}}  [http://people.irisa.fr/Francois.Schwarzentruber/recursive_functions_to_turing_machines/ Funtzio errekurtsibo baten baliokidea Turing-makina moduan lortzeko programa konpilatzailea. / A compiler for transforming a recursive function into an equivalent Turing machine]

{{Autoritate kontrola}}

[[Kategoria:Konputazioaren teoria]]
[[Kategoria:Konputagarritasuna]]
[[Kategoria:Informatika teorikoa]]