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 capacidades fundamentales 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.
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 de algoritmo.
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 los lenguajes
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 cierta axiomatización de algoritmos.1
Uno de los primeros
resultados de esta teoría fue la existencia de problemas imposibles de resolver
algoritmicamente, 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 las computadoras 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.....
COMO UTILIZAR WINOWS MOVIE MAKER
COMO UTILIZAR WINDOWS MOVIE MAKER EN WIN 7
COMO UTILIZAR HERRAMIENTAS DE WORD
COMO UTILIZAR PHOTOSHOP CS5
HERRAMIENTAS DE PHOTOSHOP CS5
No hay comentarios:
Publicar un comentario