Teoria de la computacion

Es un conjunto de conocimientos racionales, sistematizados, y funcionales, que se centran en el estudio de la abstracción de los procesos que ocurren en la realidad con el fin de reproducirlos con ayuda de sistemas formales, es decir, a través de códigos de caracteres e instrucciones lógicas, reconocibles por el ser humano, con capacidad de ser modeladas en las limitaciones de dispositivos queprocesan información y efectúan cálculos, tales como el ordenador. Para ello se apoya en la teoría de autómatas para simular y estandarizar dichos procesos, así como para formalizar los problemas y darles solución.


Teoría de autómatas
Artículo principal: Teoría de autómatas

Esta teoría provee modelos matemáticos que formalizan el concepto de computadora o algoritmo de manera suficientementesimplificada y general para que se puedan analizar sus capacidades y limitaciones. Algunos de estos modelos juegan un papel central en varias aplicaciones de las ciencias de la computación, incluyendo procesamiento de texto, compiladores, diseño de hardware e inteligencia artificial.

Los tres principales modelos son los autómatas finitos, autómatas con pila y máquinas de Turing, cada uno consus variantes deterministas y no deterministas. Los autómatas finitos son buenos modelos de computadoras que tienen una cantidad limitada de memoria, los autómatas con pila modelan los que tienen gran cantidad de memoria pero que solo pueden manipularla a manera de pila (el último dato almacenado es el siguiente leído), y las máquinas de Turing modelan las computadoras que tienen una gran cantidadde memoria almacenada en una cinta. Estos autómatas están estrechamente relacionados con la teoría de lenguajes formales; cada autómata es equivalente a una gramática formal, lo que permite reinterpretar la jerarquía de Chomsky en términos de autómatas.

Existen muchos otros tipos de autómatas como las máquinas de acceso aleatorio, autómatas celulares, máquinas ábaco y las máquinas de estadoabstracto; sin embargo en todos los casos se ha mostrado que estos modelos no son más generales que la máquina de Turing, pues la máquina de Turing tiene la capacidad de simular cada uno de estos autómatas. Esto da lugar a que se piense en la máquina de Turing como el modelo universal de computadora.

Teoría de la computabilidad
Artículo principal: Teoría de la computabilidad
Véase también:Indecidibilidad

Esta teoría explora los límites de la posibilidad de solucionar problemas mediante algoritmos. Gran parte de las ciencias computacionales están dedicadas a resolver problemas de forma algorítmica, de manera que el descubrimiento de problemas imposibles es una gran sorpresa. La teoría de la computabilidad es útil para no tratar de resolver algoritmicamente estos problemas, ahorrandoasí tiempo y esfuerzo.

Los problemas se clasifican en esta teoría de acuerdo a su grado de imposibilidad:

Los computables son aquellos para los cuales sí existe un algoritmo que siempre los resuelve cuando hay una solución y además es capaz de distinguir los casos que no la tienen. También se les conoce como decidibles, resolubles o recursivos.
Los semicomputables son aquellos paralos cuales hay un algoritmo que es capaz encontrar una solución si es que existe, pero ningún algoritmo que determine cuando la solución no existe (en cuyo caso el algoritmo para encontrar la solución entraría a un bucle infinito). El ejemplo clásico por excelencia es el problema de la parada. A estos problemas también se les conoce como listables, recursivamente enumerables o reconocibles, porquesi se enlistan todos los casos posibles del problema, es posible reconocer a aquellos que sí tienen solución.
Los incomputables son aquellos para los cuales no hay ningún algoritmo que los pueda resolver, no importando que tengan o no solución. El ejemplo clásico por excelencia es el problema de la implicación lógica, que consiste en determinar cuándo una proposición lógica es un teorema;...