Viquipèdia

Teoria de la computació: diferència entre les revisions

Exploració interactiva de l'historial
← Edició anteriorEdició següent →
Contingut suprimit Contingut afegit
VisualWikitext
Robot estandarditza i catalanitza referències, catalanitza dates i fa altres canvis menors
m Enllaços a Google Llibres en català
Línia 9:
Des d'èpoques antigues, els còmputs han existit i s'han efectuat de manera mental o assistida per rudiments com comptes, llapis i paper, o taules. Els antecedents de la computació mecànica, poden traçar fins a èpoques antigues, amb el desenvolupament d'artefactes per assistir el procés dels càlculs matemàtics mentals, per exemple el [[àbac]], el [[regle de càlcul]] o el [[quipu]]. Encara que potser és més propícia com a exemple precursor, la [[Mecanisme d'Anticitera|cèlebre calculadora]] grega d'[[Anticitera]], utilitzada segons els experts per assistir en càlculs astronòmics, i considerada per molts com la primera [[ordinador]].<ref>{{ref-web |url=http://www.nytimes.com/2008/07/31/science/31computer.html?_r=1&th&emc=th&oref=slogin |títol=Discovering How Greeks Computed in 100 B.C. |editor=NY Times |data=2008-07-31}}</ref> Un altre exemple precursor són les màquines sumador de [[Blaise Pascal]]. Aparells que demostren una notable perícia dels seus creadors en el coneixement sobre la forma d'elaborar els càlculs desitjats, al grau de poder representar en la forma de mecanismes més o menys elaborats.
 
Alguns d'aquests models formals van ser proposats per precursors com [[Alonzo Church]] ([[càlcul lambda]]), [[Kurt Gödel]] ([[funció recursiva|funcions recursives]]) i [[Alan Turing]] ([[màquina de Turing]]).<ref>{{ref-llibre |títol=Máquinas moleculares basadas en ADN |pàgines=1 |editorial=Universidad de Sevilla |any=2003 |isbn=8447207773 |url=https://books.google.escat/books?id=O4RehPJl2CkC&pg=PA1&dq=Teoria+de+la+computaci%C3%B3&hl=ca&sa=X&ved=2ahUKEwi7ytnd0czzAhU8SfEDHbvyBMIQ6AF6BAgHEAI#v=onepage&q=Teoria%20de%20la%20computaci%C3%B3&f=false |nom=Mario de J. |cognom=Pérez Jiménez |nom2=Fernando |cognom2=Sancho Caparrini |llengua=castellà}}</ref> Aquests models són equivalents en el sentit que poden simular els mateixos algorismes, encara que ho facin de maneres diferents. Entre els models de còmput més recents hi ha els [[Llenguatge de programació|llenguatges de programació]], que també han resultat ser equivalents als models anteriors, això és una forta evidència de la [[Tesi de Church-Turing|conjectura de Church-Turing]], que tot algorisme hagut i per haver es pot simular en una màquina de Turing, o equivalent, usant funcions recursives. El 2007 Nachum Dershowitz i Yuri Gurevich van publicar una demostració d'aquesta conjectura basant-se en certa [[axioma]]tització d'algorismes.<ref name="Dershowitz">{{citar ref |autor=Nachum Dershowitz & Yuri Gurevich |títol=A natural axiomatization of computability and proof of Church's Thesis |data= 2008 |col·lecció= Bulletin of Symbolic Logic |volum=14 |exemplar=3 |issn= 10798986, 299-350|url=http://research.microsoft.com/en-us/um/people/gurevich/Opera/188.pdf}}</ref>
 
Un dels primers resultats d'aquesta teoria va ser l'existència de problemes impossibles de resoldre algorítmicament, i el [[problema de la parada]] el més famós d'ells. Per a aquests problemes no existeix ni existirà cap algorisme que els pugui resoldre, no important la quantitat de temps o memòria es disposi en un ordinador. Així mateix, amb l'arribada de les computadores modernes es va constatar que alguns problemes resolubles en teoria eren impossibles en la pràctica, ja que aquestes solucions necessitaven quantitats irrealistes de temps o memòria per poder-se trobar.
Obtingut de «https://ca.wikipedia.org/wiki/Teoria_de_la_computació»