la computacion


Queridos lectores de Wikipedia: somos la entidad sin ánimo de lucro al cargo de la 5ª web más importante del mundo. Solo tenemos un equipo de 175 personas pero damos servicio a 500 millones de usuarios, y tenemos costes como cualquier otra web de gran importancia: servidores, electricidad, alquiler, programas y personal. Wikipedia es algo especial. Es como una biblioteca, o un parque público.Es como un templo para la mente, un lugar al que todos podemos ir a pensar y aprender. Para proteger nuestra independencia, nunca mostraremos publicidad. No aceptamos fondos gubernamentales. Funcionamos con donaciones de una media de Bs.F. 100 aproximadamente. Ahora es el momento en que pedimos. Si todos los que leen este mensaje nos donaran el precio de una taza de café, habríamos concluido larecogida de fondos en una hora. Si Wikipedia es útil para ti, dedica un minuto a mantenerla funcionando otro año. Por favor, ayúdanos a olvidarnos de la recogida de fondos y volver a dedicarnos a Wikipedia. Gracias. Por favor, ayúdenos
 
Teoría de la computación
La teoría de la computación es una rama de la matemática y la computación que centra su interés en las limitaciones y capacidadesfundamentales de las computadoras. Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo (cuenta o cálculo) y la clasificación de problemas.
Índice
1 Principales subramas
1.1 Teoría de autómatas
1.2 Teoría de la computabilidad
1.3 Teoría de la complejidad computacional
2 Otras subramas
3 Historia
4 Referencias
Principales subramas
Teoría deautó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 suficientemente simplificada 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 con sus 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 solopueden 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 cantidad de 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 enté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 estado abstracto; 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 lamá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 descubrimientode problemas imposibles es una gran sorpresa. La teoría de la computabilidad es útil para no tratar de resolver algoritmicamente estos problemas, ahorrando así 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...