Funtzio konputagarri

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

Sarrera

Alan Turing

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, $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ funtzio bat konputagarria da, baldin eta soilik baldin zenbaki arrunten $\mathbf {x}$ k-kotea emanda $f(\mathbf {x} )$ 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:

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^[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, $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ funtzio partzial bat kalkula daiteke, propietate hauek dituen programa informatiko bat existitzen bada:

$f(\mathbf {x} )$ funtzioa definituta badago, orduan programari sarrera moduan $\mathbf {x}$ emanez gero, exekuzioa amaitu eta ordenagailuaren memorian $f(\mathbf {x} )$ balioa gordeko da.
$f(\mathbf {x} )$ funtzioa ez badago definituta, orduan programari sarrera moduan $\mathbf {x}$ 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:

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 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) $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$ funtzio konputagarri baten definizio-eremua da.
$B$ funtzio konputagarri oso baten helburu-multzoa da. $B$ infinitua bada, orduan funtzioa injektiboa dela suposa daiteke.

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

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, ${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.

Adibideak

Funtzio hauek konputagarriak dira:

Definizio-eremu finitua duten funtzioak; adibidez, zenbaki arrunten edozein sekuentzia finitu.
f funtzio konstanteak, f : N^k → N, f(n₁,...n_k) := n.
Batuketa: f : N² → N, f(n₁,n₂) := n₁ + n₂
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, $\color {Blue}f\circ g$ funtzioak eta baita max(f,g), min(f,g), arg max{y<=f(x)} etab. konputagarriak dira.

Erreferentziak

↑ J. Ibáñez, A. Irastorza, A. Sánchez. (2000). Konputaezintasun Frogapen Batzuk Diagonalizazio Teknika Erabiliz. UPV/EHU.
↑ Arantza Irastorza, Ana Sánchez, Jesús Ibáñez. (2017). Konputagarritasunerako Oinarrizko Teknikak. UPV/EHU.
↑ Jesús Ibáñez Martínez-Conde, María Aránzazu Irastorza Goñi, Ana Sánchez Ortega. (1998). While programak: konputagarritasun teoria oinarritzeko tresna. UPV/EHU.
↑ «Computable Structures and the Hyperarithmetical Hierarchy, Volume 144 - 1st Edition» www.elsevier.com (Noiz kontsultatua: 2022-12-22).
↑ (Ingelesez) Soare, Robert I.. (1995). Computability and Recursion. .

Bibliografia

(Ingelesez) Ash C. J. , J. Knight, Computable Structures and the Hyperarithmetical Hierarchy (Studies in Logic and the Foundation of Mathematics, 2000), p
(Ingelesez) Cutland, Nigel. Computability. Cambridge University Press, 1980.
(Ingelesez) Cooper, S. B. , 2004. Computability Theory, Chapman & Hall/CRC. ISBN 1-58488-237-9
(Ingelesez) 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
(Ingelesez) Davis, M., Computability and Unsolvability, ISBN 978-0486614717
(Ingelesez) Enderton, H.B. Elements of recursion theory. Handbook of Mathematical Logic (North-Holland 1977) orr. 527–566.
(Ingelesez) Enderton, Herbert (2002). A Mathematical Introduction to Logic. USA: Elsevier. p. 209. ISBN 0-12-238452-0.
(Gaztelaniaz) 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.
(Ingelesez) Jack Copeland, B., Carl J. Posy, Oron Shagrir, 2015, Computability: Turing, Gödel, Church, and Beyond , The Mit Press, ISBN 9780262527484
(Ingelesez) Rogers, H. Theory of recursive functions and effective computation (McGraw–Hill 1967).
(Gaztelaniaz) 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
(Gaztelaniaz) Soare R., Computabilidad y recursión (1995).
(Ingelesez) 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.
(Ingelesez) 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

Kanpo estekak

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

Datuak: Q1148456

[1] J. Ibáñez, A. Irastorza, A. Sánchez. (2000). Konputaezintasun Frogapen Batzuk Diagonalizazio Teknika Erabiliz. UPV/EHU.

[2] Arantza Irastorza, Ana Sánchez, Jesús Ibáñez. (2017). Konputagarritasunerako Oinarrizko Teknikak. UPV/EHU.

[3] Jesús Ibáñez Martínez-Conde, María Aránzazu Irastorza Goñi, Ana Sánchez Ortega. (1998). While programak: konputagarritasun teoria oinarritzeko tresna. UPV/EHU.

[4] «Computable Structures and the Hyperarithmetical Hierarchy, Volume 144 - 1st Edition» www.elsevier.com (Noiz kontsultatua: 2022-12-22).

[5] (Ingelesez) Soare, Robert I.. (1995). Computability and Recursion. .

[1]

[2]

[3]

[4]

[5]