Konputagarritasunaren teoria

Konputagarritasunaren teoria problema erabakigarriak aztertzen dituen konputazioko atala da, 1930ean aztertzen hasi zena. Orokorrean, algoritmo baten bidez edo Turing makina baten bidez (baliokidea dena) ebatzi daitezkeen problemak aztertzen ditu, hain zuzen.

Sarrera aldatu

Orokorrean, konputagarritasuna hainbat galdera erantzuten saiatzen da, hala nola:

Zer problema ebatz dezake Turing makina batek?
Zein beste metodo dira Turing-en makinaren baliokideak?
Zer problemak ebatz ditzakete makina ahaltsuek?
Zer problemak ebatz ditzakete makina ahulagoek?

Hara ere, konputagarritasun teoriak egiten dituen oinarrizko galderak honako hauek dira: zer esan nahi du funtzio bat konputagarria izatea? eta nola klasifikatu ditzakegu hierarkikoki funtzio ez-konputagarriak bere ez-konputagarritasun mailaren arabera? Galdera hauen erantzunari bilatu nahian, teoria zabal bat sortu da, gaur egun ere, oraindik, aztertzen ari dena^[1]^[2]^[3]

Bestalde, problema guztiak ez dira konputagarriak: problema ez-erabakigarriak algoritmo baten bidez ebatzi ezin daitezkeenak dira, nahiz eta denbora eta espazioa mugagabeak izan. Adibidez:

Entscheidungsproblem: lehen ordenako predikatuen kalkuluko esaldi bat emanda, hau teorema bat den erabakitzean datza. Alonzo Church eta Alan Turing matematikariek, bakoitzak bere aldetik, problema hau erabakiezina dela frogatu zuten.

Gelditze problema: programa bat eta sarrerako parametroak emanda, sarrerako parametro horientzako programa bukatuko den edo ez erabakitzea. Turing-ek frogatu zuen honako hau ere problema erabakiezina dela.

Zenbaki konputagarri bat, hautazko zehaztasun mailako algoritmo baten bidez hurbildu daitekeen zenbaki erreala da. Turing-ek zenbaki gehienak ez-konputagarriak direla frogatu zuen. Adibidez, Chaitin konstantea ez da konputagarria, ondo definitua egon arren. Chaitin konstantea, ausaz hautatutako programa batek Turing makina determinatu batean gelditzeko probabilitatea adierazten du.

Aurretikoak aldatu

Algoritmoen lehendabiziko adibidea Euklides proposatutako bat izan zen, bi zenbakien arteko Zatitzaile komun handiena (ZKH) kalkulatzeko helburua zuena. Funtsean, kalkulua instrukzio-sekuentzia finitu batekin egin ahal izatea da helburua. Bestalde, nabaria denez, prozedura hauek mekanikoki makina batek exekutatzearen ideia aurrerago garatu zen, hasierako ideia soilik kalkuluak egiteko edo problema bat ebazteko prozedura mekanikoak ezartzea baitzen.

Bestalde, Gottfried Wilhelm Leibniz beste mota bateko problema proposatu zuen XVII. mendean: adierazpen logikoak egiazkoak ala faltsuak diren erabakitzen duen makina bat sortzea. Helburu honek abiapuntu bat ezarri zuen urte askotarako, eta konputagarritasunari buruzko lan gehienak gai honetan oinarritu ziren.

XX. mendearen hasieran David Hilbert soluziorik gabeko 23 problema aurkeztu zituen, eta 28 urte geroago, Hilbert bera Entscheidungsproblem problema proposatu zuen, Leibniz-en ideiarekin erlazio zuzena duena: sistema matematiko formal bat sortzea, trinkoa eta osoa, baieztapen guztiak frogatzea ahalbidetuko duena, ondoren algoritmo baten bidez ondo eratutako edozein adierazpen egiazkoa edo faltsua den iragartzeko gai zena.

1931. urtean, ordea, Kurt Gödel matematikariak Osatugabetasunaren teoremak proposatu zituen, Hilbert-en ideiari muga garrantzitsuak jarriz:

Lehendabiziko teoremaren arabera baieztatu daiteke ez dagoela teoria matematiko formalik zenbaki naturalen aritmetika deskribatzen duena eta aldi berean trinkoa eta osoa dena. Hortaz, teoria baten axiomak trinkoak badira, (hau da, ez badaude kontraesanik beraien artean), existituko dira frogatu edo errefutatu egin daitezkeen adierazpenak.

Bigarren teoremaren arabera, bestalde, baieztatu daiteke teoria formal trinko batean frogatu ez daitekeen adierazpenetariko bat zehazki teoria horren trinkotasuna dela.

Osatugabetasunaren teoremak oso ondorio garrantzitsuak ezarri zituen konputagarritasunaren teorian, sistema formalen gaitasunen muga garrantzitsuak finkatu zituelako.

Hamarkada berdinean, Princetongo Unibertsitatean Alan Turing, Alonzo Church, J. B. Rosser, Stephen Kleene eta beste matematikari ospetsuak konputagarritasunaren definizio aberats bat bilatzen hasi ziren. Azkenik, 1936. urtean Alan Turing bere “Turing makina”ren definizioa sortu egin zuen, eta Church-Turing tesia argitaratu zen. Tesi honekin funtzio konputagarrien eta Turing makinaren arteko baliokidetasuna formulatu zen era hipotetikoan, hau da, edozein algoritmo Turing makinaren berdina dela.

Church-Turing tesia aldatu

1930. hamarkadan, Hilbert-ek proposatutako Entscheidungsproblem problema, matematikariek gehien aztertutako problema zen. 1936-an Church eta Turing-ek frogatu zuten, bakoitzak bere aldetik eta modu desberdinetan (Lambda kalkulua eta Turing makina erabiliz, hurrenez hurren), problema horren konputaezintasuna. Ondoren, makina horren hasierako kontzeptua zabaldu egin zen.

Church-Turing tesia, funtzio konputagarriaren eta Turing makinaren baliokidetasuna formulatzen du, hau da, algoritmo oro Turing makina baten baliokidea dela dio. Dionez, ezin da ezer kalkulatu edo erabaki Turing Makina (edo honen baliokidea den formalismo) baten bitartez kalkulatu ezin bada. Gainera, konputagarritasunaren ideia hoberen definitzen duen formalismoa kontsideratzen da Turing Makina.

Hipotesi hau, nahiz eta formalki frogaezina izan, gaur egun onespen ia unibertsala du, eta konputagarritasunari buruzko limiteak finkatu egin zituen, ez baita espero Turing makinen edo bere baliokideak diren ereduen ahalmen konputazional gehiago duen eredu bat sortzea.

Turing Makinaren Baliokideak aldatu

Turing Makina baino ahaltsuagorik aurkituak izan ez diren arren, badaude honen baliokideak direnak. Adibidez, while-programak, funtzio μ-errekurtsiboak eta Turing Makinak baliokideak dira, hau da, funtzio mota berdinak konputatzeko gai dira.

Praktikoki, hiru formalismo hauek ezaugarri desberdinak dituzte. Alde batetik, Turing Makinak makina konputagarrien deskribapenaren oinarria dira eta hauen abantaila intuizioa da. Bestetik, funtzio μ-errekurtsiboak, Lambda kalkuluarekin batera, programazio funtzionalaren eta semantika denotazionalaren oinarria dira eta kasu honetan, abantaila, argitasuna da. Azkenik, while-programak, semantika operazionalaren oinarria dira eta abantaila trebantzia da.

Hauez gain, beste formalismo baliokide ugari daude, konputazioaren ideia bera deskribatzen dutenak. μ-errekurtsiboekin batera aipatutako Lambda kalkulua (Church eta Kleene-k garatutakoa eta Church-ek Entscheidungsproblem-a konputazina zela frogatzeko erabili zuena), funtzioak definitzeko era bat da. Adibidez:

λx, y.z , sarrerako datuak x eta y izanda, z bueltatuko duen funtzioa da
Batuketa: λn1, n2.n1 + n2
λx1, x2, x3.x2, hiru argumentu izanda beti bigarrena bueltatzen duena.

Beraz, Lambda kalkuluaren bitartez ere, Turing Makinaren bitartez konputatu daitezkeen funtzioak konputatu ahal izango dira. Lambda kalkulua programazio lengoai unibertsalik txikiena bezala kontsidera daiteke, azken finean, aldagaien ordezkapen batean eta funtzioak definitzeko era sinple batean oinarritzen baita. Lambda kalkuluak, lengoaia funtzionalen gainean eragin handia dauka ere, hala nola, Haskell lengoaian.

Gaur egungo programazio lengoaiak ere Turing Makinaren baliokideak dira. Turing Makinaren baliokideen artean honako hauek ditugu:

Turing Makinak hainbat zintekin
Turing Makinak zinta bidimentsionalekin
Turing Makinak egoera kopuru mugatuekin
Turing Makinak bakarrik bi egoerekin
Bi pilako automata finituak
Bi kontagailuko automata finituak
Gramatika formalak
Post Makina
Lambda kalkulua
Funtzio errekurtsibo partzialak
Gaur egungo programazio lengoai gehienak (memoria mugagabea izango balute)
Automata zelularrak
John Conway-en "Bizitzaren jokoa"
Turing Makina indeterminatuak
Turing Makina probabilistikoak
Konputagailu kuantikoa

Ikus, gainera aldatu

Bibliografia aldatu

S. B. Cooper, 2004. Computability Theory, Chapman & Hall/CRC. ISBN 1-58488-237-9
M. Davis, 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
M. Davis, Computability and Unsolvability, ISBN 978-0486614717
B. Jack Copeland, Carl J. Posy, Oron Shagrir, 2015, Computability: Turing, Gödel, Church, and Beyond , The Mit Press, ISBN 9780262527484
Ricardo Rosenfeld, Jerónimo Irazábal, Computabilidad, complejidad computacional y verificación de programas, : Universidad Nacional de La Plata, 2013. ISBN 978-950-34-0970-1
Damiano Zanardini, 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

Erreferentziak aldatu

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

Kanpo estekak aldatu

Datuak: Q818930
Multimedia: Computer science / Q818930

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

[1]

[2]

[3]