|
La teoria de la computació comença pròpiament a principis del {{segle|XX}}, poc abans que les computadores electròniques fossin inventades. En aquesta època diversos matemàtics es preguntaven si existia un mètode universal per resoldre tots els problemes matemàtics. Per a això havien de desenvolupar la noció precisa de mètode per resoldre problemes, és a dir, la definició formal d'[[algorisme]].
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.es/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>
|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.
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 cèlebre calculadora grega d'[[Antikythera]], utilitzada segons els experts per assistir en càlculs astronòmics, i considerada per molts com la primera [[ordinador]]. 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. ▼
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 cèlebre calculadora grega d'[[Antikythera]], utilitzada segons els experts per assistir en càlculs astronòmics, i considerada per molts com la primera [[ordinador]]. 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.
<!--
No obstant això, la teoria de la computació com a ciència comença pròpiament a principis del {{segle|XX}}, poc abans que les computadores electròniques fossin inventades.
En aquest època diversos matemàtics es preguntaven quina mena de problemes de la matemàtica, podien resoldre per "mètodes simples" i quines no. I per això havien en principi desenvolupar una definició de "mètode per resoldre problemes", és a dir, necessitaven el desenvolupament d'una noció formal (matemàtica) del que és un càlcul/algorisme i l'aritmètica lògica.
Durant el {{segle|XIX}} i XX diversos corrents filosòfiques van aplanar el camí de la [[computació]] a partir de les definicions de [[sistema formal|sistemes formals]]. Destacant [[Kurt Gödel]] i [[Bertrand Russell]] entre d'altres.
Diverses definicions i models formals del que és un càlcul van ser proposats per precursors del domini com [[Alan Turing]] i [[Alonzo Church]], entre aquests models hi ha la [[màquina de Turing]], les [[funció recursiva|funcions recursives]], i el [[càlcul Lambda]]. Tots els quals s'ha demostrat posteriorment que són equivalents en expressivitat computacional, és a dir, tots poden representar la mateixa classe de còmputs o algorismes, encara que ho facin de maneres diferents.
S'assumeix normalment que les computadores electròniques són també equivalents en capacitat de còmput a qualsevol d'aquests tres models esmentats anteriorment, però no hi ha una prova formal d'això, per aquesta raó a aquest presumpció raonable es coneix com la [[Tesi de Church - Turing|conjectura de Church-Turing]].
D'aquí la rellevància de l'estudi de les màquines de Turing, ja que gràcies a aquest conjectura àmpliament acceptada com a veritable, tot problema de còmput que sigui [[Teoria de la computabilitat|resoluble]] en una [[màquina de Turing]], es considera que també ho serà en un ordinador, i viceversa.
És meritori el fet que gràcies a l'equivalència de màquines de Turing i ordinadors, s'hagi determinat que hi ha càlculs que no poden ser resolts en un temps raonable en cap ordinador imaginable, o fins i tot, que no poden resoldre's en l'absolut, per exemple el [[problema de correspondència de Post]] o el problema de predir si una màquina de Turing qualsevol va a arribar a un estat final (conegut com el problema de l'Haltingen en anglès, o problema de la parada '').
Altres temes d'interès de la teoria de la computació, són la quantitat de temps o la quantitat de memòria necessària per realitzar un càlcul donat. S'ha determinat que existeixen còmputs sismes, però que necessiten quantitats irreals de temps o memòria per poder efectuar-se. És summament important per als especialistes del domini conèixer la [[complexitat computacional]] d'un algorisme, ja que aquesta determinarà l'aplicabilitat del mateix.
Un altre interès d'aquesta ciència, són els models reduïts de còmput, que són en realitat casos particulars d'una màquina de Turing. Com ho són les [[màquines d'estat finit]] esbossades primer per [[Warren McCulloch]] i [[Walter Pitts]] a [[1943]], i els [[autòmat amb pila|autòmats amb pila]].-->
== Referències ==
| 