Ver la fonte de Teoría de la computación

{{wikificar|t=20140430224915}}

La '''teoría de la computación''' ye un conxuntu de conocencies racionales, sistematizados y funcionales que se centren nel estudiu de l'[[astracción (informática)|astracción]] de los procesos qu'asoceden na realidá col fin de reproducilos con ayuda de [[sistema formal|sistemes formales]], esto ye, al traviés de códigos de calteres y [[instrucción informática|instrucciones]] lóxiques, reconocibles pol ser humanu, con capacidá de ser [[modeláu de procesos modelaes]] nes llimitaciones de dispositivos que procesen información y qu'efectúen cálculos como, por casu, l'[[ordenador]]. Pa ello, sofitar na [[teoría d'autómates]], con cuenta d'asemeyar y estandarizar dichos procesos, según pa formalizar los problemes y da-yos solución.{{ensin referencies}}

== Principales subramas ==
=== Teoría d'autómates ===
{{ap|Teoría d'autómates}}
Esta teoría aprove modelos matemáticos que formalicen el conceutu de ''ordenador'' o ''algoritmu'' de manera abondo simplificada y xeneral por que puedan analizase les sos capacidaes y llimitaciones. Dalgunos d'estos modelos xueguen un papel central en delles aplicaciones de les ciencies de la computación, incluyendo procesamientu de testu, [[compilador]]es, diseñu de hardware y [[intelixencia artificial]].

Esisten munchos otros tipos d'autómates como les [[Máquina d'accesu aleatoriu|máquines d'accesu aleatoriu]], [[Autómata celular|autómates celulares]], [[Máquina ábaco|máquines ábaco]] y les [[Máquina d'estáu astractu|máquines d'estáu astractu]]; sicasí en tolos casos amosóse qu'estos modelos nun son más xenerales que la máquina de Turing, pos la máquina de Turing tien la capacidá d'asemeyar cada unu d'estos autómates. Esto da llugar a que se piense na máquina de Turing como'l modelu universal d'ordenador.

=== Teoría de la computabilidad ===
{{ap|Teoría de la computabilidad}}
{{vt|Indecidibilidad}}
Esta teoría esplora les llendes de la posibilidá de solucionar problemes por aciu algoritmos. Gran parte de les ciencies computacionales tán dedicaes a resolver problemes de forma algorítmica, de manera que'l descubrimientu de problemes ''imposibles'' ye una gran sorpresa. La teoría de la computabilidad ye útil pa nun tratar de resolver algorítmicamente estos problemes, aforrando asina tiempu y esfuerciu.

Los problemes clasificar nesta teoría d'alcuerdu al so grau de ''imposibilidá'':
* Los '''computables''' son aquellos pa los cualos sí esiste un algoritmu que siempres los resuelve cuando hai una solución y amás ye capaz d'estremar los casos que nun la tienen. Tamién se-yos conoz como ''decidibles'', ''resolubles'' o ''recursivos''.
* Los '''semicomputables''' son aquellos pa los cualos hai un algoritmu que ye capaz atopar una solución si ye qu'esiste, pero nengún algoritmu que determine cuando la solución nun esiste (y nesi casu l'algoritmu p'atopar la solución entraría a un [[bucle infinitu]]). L'exemplu clásicu por excelencia ye'l [[problema de la parada]]. A estos problemes tamién se-yos conoz como ''listables'', ''recursivamente enumerables'' o ''reconocibles'', porque si se enlistan tolos casos posibles del problema, ye posible ''reconocer'' a aquellos que sí tienen solución.
* Los '''incomputables''' son aquellos pa los cualos nun hai nengún algoritmu que pueda resolver, nun importando que tengan o non solución. L'exemplu clásicu por excelencia ye'l [[Entscheidungsproblem|problema de la implicación lóxica]], que consiste en determinar cuándo una proposición lóxica ye un [[teorema]]; pa esti problema nun hai nengún algoritmu qu'en tolos casos pueda estremar si una proposición o la so negación ye un teorema.

Hai una versión más xeneral d'esta clasificación, onde los problemes incomputables subdivídense de la mesma en problemes más difíciles qu'otros. La ferramienta principal pa llograr estes clasificaciones ye'l conceutu de '''reducibilidad''': Un problema <math>A</math> amenorgar al problema <math>B</math> si sol camientu de que sabe resolvese el problema <math>B</math> ye posible resolver al problema <math>A</math>; esto se denota por <math>A\le_t B</math>, y informalmente significa que'l problema <math>A</math> ''nun ye más malo de resolver'' que'l problema <math>B</math>. Por casu, sol camientu de qu'una persona sabe sumar, ye bien fácil enseña-y a multiplicar faciendo sumas repitíes, de manera que multiplicar amenorgar a sumar.

=== Teoría de la complexidá computacional ===
{{ap|Complexidá computacional}}
{{vt|Clase de complexidá}}
Entá cuando un problema sía computable, pue que nun sía posible resolvelo na práutica si ríquese muncha memoria o [[tiempu d'execución]]. La teoría de la complexidá computacional estudia les necesidaes de memoria, tiempu y otros recursos computacionales pa resolver problemes; d'esta manera ye posible esplicar por qué unos problemes son más difíciles de resolver qu'otros. Unu de los mayores llogros d'esta caña ye la clasificación de problemes, similar a la tabla periódica, d'alcuerdu a la so dificultá. Nesta clasificación los problemes dixebrar por [[Clase de complejidad|clases de complexidá]].

Esta teoría tien aplicación en casi toles árees de conocencia onde se deseye resolver un problema computacionalmente, porque los investigadores non solo deseyen utilizar un métodu pa resolver un problema, sinón utilizar el más rápidu. La teoría de la complexidá computacional tamién tien aplicaciones n'árees como la [[criptografía]], onde s'espera que descifrar un códigu secretu sía un problema bien difícil nun siendo que se tenga la contraseña, y nesi casu el problema vuélvese fácil.

== Otres subramas ==
* '''Modelos de cómputu''' Estudia astracciones de ''faer un cómputu''. Equí inclúyense los clásicos modelos de la teoría d'autómates amás d'otros modelos como [[Recursión primitiva|funciones recursivas]], [[cálculo lambda]] y inclusive [[Llinguaxe de programación|llinguaxes de programación]].
* '''[[Teoría algorítmica de la información]]''' Centra la so atención na complexidá pa describir algorítmicamente una secuencia de datos ([[Cadena de carácter|cadena]]); equí la complexidá ta midida pol llargor de la so descripción más pequeña.
* '''Especificación y verificación formal''' Busca metodoloxíes pa garantizar qu'un problema tea correutamente modeláu y [[Sistema formal|sistemes formales]] pa validar la [[Correctitud|correición]] de la solución algorítmica.
* La '''Teoría del aprendizaxe computacional''' busca algoritmos que faigan que los ordenadores modifiquen los sos comportamientos de manera autónoma con base en datos empíricos, y concretamente n'exemplos y contraejemplos. A esti tipu d'aprendizaxe llámase-y [[Clasificadores (matemáticu)#Aprendizaxe supervisáu|'''aprendizaxe supervisáu''']]. De forma análoga a la teoría de la complexidá computacional, nesta teoría les funciones clasificar pol so grau de dificultá de ser aprendíes.
* '''[[Tipu de datu astractu|Teoría de tipos]]''' Busca la clasificación d'enunciaos d'alcuerdu a los tipos de valores que calculen utilizando ferramientes de teoría de [[Llinguaxe formal|llinguaxes formales]].

== Historia ==
{{vt|Entscheidungsproblem|Tesis de Church-Turing}}
La teoría de la computación empieza puramente a principios del sieglu XX, poco primero que los ordenadores electrónicos fueren inventaes. Nesta dómina dellos matemáticos preguntaben si esistía un métodu universal pa resolver tolos problemes matemáticos. Pa ello teníen de desenvolver la noción precisa de ''métodu pa resolver problemes'', esto ye, la definición formal de ''[[algoritmu]]''.

Dalgunos d'estos modelos formales fueron propuestos por precursores como [[Alonzo Church]] ([[cálculo Lambda]]), [[Kurt Gödel]] ([[función recursiva|funciones recursivas]]) y [[Alan Turing]] ([[máquina de Turing]]). Amosóse qu'estos modelos son equivalentes nel sentíu de que pueden asemeyar los mesmos algoritmos, anque lo faigan de maneres distintes. Ente los modelos de cómputu más recién atópense los [[Llinguaxe de programación|llinguaxes de programación]], que tamién amosaron ser equivalentes a los modelos anteriores; esto ye una fuerte evidencia de la [[Tesis de Church-Turing|conxetura de Church-Turing]], de que tou algoritmu habíu y por haber puede asemeyase nuna máquina de Turing, o equivalentemente, usando funciones recursivas. En 2007 Nachom Dershowitz y Yuri Gurevich publicaron una demostración d'esta conxetura basándose en cierta [[Axoma|axiomatización]] d'algoritmos.<ref name = "Dershowitz">{{Cita publicación
| autor = Nachom Dershowitz & Yuri Gurevich
| títulu = A natural axiomatization of computability and proof of Church's Thesis
| añu = 2008
| revista = Bulletin of Symbolic Logic
| volume = 14
| númberu = 3
| issn = 1079-8986
| páxines = 299-350
| url = http://research.microsoft.com/en-us/um/people/gurevich/Opera/188.pdf
}}</ref>

Unu de les primeres resultancies d'esta teoría foi la esistencia de problemes imposibles de resolver algorítmicamente, siendo'l ''[[problema de la parada]]'' el más famosu d'ellos. Pa estos problemes nun esiste nin va esistir nengún algoritmu que pueda resolver, nun importando la cantidá de tiempu o memoria disponer nun ordenador. Coles mesmes, cola llegada de los ordenadores modernos constatóse que dellos problemes resolubles en teoría yeren imposibles na práutica, yá que diches soluciones precisaben cantidaes irrealistas de tiempu o memoria pa podese atopar.

== Referencies ==
{{llistaref}}

==Bibliografía==

* {{cita web
|url = http://www.ams.org/mathscinet/msc/pdfs/classifications2010.pdf
|autor = American Mathematical Society
|títulu =2010 Mathematics Subject Classification
|fechaaccesu = 7 de marzu de 2010

}}
* {{cita llibru | 
autor = Boolos, George; Burgess, John; & Jefrey, Richard
| editorial = Cambridge
| títulu = Computability and Logic
| añu = 2007
| isbn = 978-0-521-70146-4
}}
* {{cita llibru | 
autor = Cooper, S. Barry 
| editorial = Chapman & Hall/CRC
| títulu = Computability Theory
| añu = 2004
| isbn = 1-58488-237-9
}}
* {{cita llibru | 
autor = [http://krypton.mnsu.edu/~kelled/ Kelley, Dean]
| editorial = Prentice Hall
| títulu = Teoría d'autómates y llinguaxes formales
| añu = 1995
| isbn = 978-0-691-13382-9
}}
* {{cita llibru | 
autor = [http://www-math.mit.edu/~sipser/ Sipser, Michael]
| editorial = Course Technology
| títulu = Introduction to the Theory of Computation
| edición = 2
| añu = 2005
| isbn = 978-0534950972
}}



{{Tradubot|Teoría de la computación}}

{{control d'autoridaes}}
[[Categoría:Informática teórica]]