Teoria de la computació: diferència entre les revisions
Contingut suprimit Contingut afegit
m Afegida Categoria:Informàtica usant HotCat |
Canvis menors, neteja, replaced: de o → d'o AWB |
||
Línia 9:
=== Teoria d'autòmats ===
{{AP|Teoria d'autòmats}}
Aquesta teoria proveeix models matemàtics que formalitzen el concepte
Els tres principals models són els [[Autòmat finit|autòmats finits]] , [[Autòmat amb pila|autòmats amb pila]] i [[Màquina de Turing|màquines de Turing]] , cadascun amb les seves variants [[Algorisme determinista|deterministes]] i no deterministes. Els autòmats finits són bons models d'ordinadors que tenen una quantitat limitada de memòria, els autòmats amb pila modelen els que tenen gran quantitat de memòria però que només poden manipular a manera d'[[Pila (informàtica)|pila]] (l'última dada emmagatzemat és el següent llegit), i les màquines de Turing modelen les computadores que tenen una gran quantitat de memòria emmagatzemada en una cinta. Aquests autòmats estan estretament relacionats amb la teoria de [[Llenguatge formal|llenguatges formals]], cada autòmat és equivalent a una [[gramàtica formal]], el que permet reinterpretar la [[jerarquia de Chomsky]] en termes d'autòmats.
Línia 43:
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]]). 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 [[
|autor = Nachum Dershowitz & Yuri Gurevich
|títol = A natural axiomatization of computability and proof of Church's Thesis
Línia 82:
== Referències ==
{{Referències}}
{{ORDENA:Teoria De La Computacio}}
[[Categoria:Informàtica]]
| |||