Teoria de la computació: diferència entre les revisions
Contingut suprimit Contingut afegit
m estandarditzant codi encapçalaments i llistes |
m Plantilla |
||
Línia 41:
== Història ==
{{VT|Entscheidungsproblem|Tesi de Church-Turing}}
La teoria de la computació comença pròpiament a principis del {{segle
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]]). 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
Línia 62:
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
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.
| |||