Tequiero

República Bolivariana de Venezuela
Ministerio Del Poder Popular Para La Educación
U.E.P. Sagrado Corazón De Jesús
Los Teques – Edo. Miranda

Teoría De la Computación
Teoría De la Computación

Prof: Integrante:
Gustavo PinoSosa Angelys #22
3ro “A” Los Teques, 29 de Octubre de 2012

Índice

Introducción……………………………………………………..
Historia……………………………………………………………
Teoría De La Computación…………………………………....
Teoría De La Computabilidad………………………………….
Teoría De La Complejidad Computacional…………………..
Conclusión…………………………………………………………..
Bibliografía…………………………………………………………..Historia


La teoría de la computación comienza propiamente a principios del siglo XX, poco antes que las computadoras electrónicas fuesen inventadas. En esta época varios matemáticos se preguntaban si existía un método universal para resolver todos los problemas matemáticos. Para ello debían desarrollar la noción precisa de método para resolver problemas, es decir, la definición formal dealgoritmo.
Algunos de estos modelos formales fueron propuestos por precursores como Alonzo Church (cálculo Lambda), Kurt Gödel (funciones recursivas) y Alan Turing (máquina de Turing). Se ha mostrado que estos modelos son equivalentes en el sentido de que pueden simular los mismos algoritmos, aunque lo hagan de maneras diferentes. Entre los modelos de cómputo más recientes se encuentran loslenguajes de programación, que también han mostrado ser equivalentes a los modelos anteriores; esto es una fuerte evidencia de la conjetura de Church-Turing, de que todo algoritmo habido y por haber se puede simular en una máquina de Turing, o equivalentemente, usando funciones recursivas. En 2007 Nachum Dershowitz y Yuri Gurevich publicaron una demostración de esta conjetura basándose en ciertaaxiomatización de algoritmos.
Uno de los primeros resultados de esta teoría fue la existencia de problemas imposibles de resolver algorítmicamente, siendo el problema de la parada el más famoso de ellos. Para estos problemas no existe ni existirá ningún algoritmo que los pueda resolver, no importando la cantidad de tiempo o memoria se disponga en una computadora. Asimismo, con la llegada de lascomputadoras modernas se constató que algunos problemas resolubles en teoría eran imposibles en la práctica, puesto que dichas soluciones necesitaban cantidades irrealistas de tiempo o memoria para poderse encontrar.






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.

Teoría De La Computabilidad

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 formaalgorí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 algorítmicamente 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 resuelvecuando 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 para los 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...