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 conayuda 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 ydarles solución.

Historia

Véanse también: Entscheidungsproblem y Tesis de Church-Turing.
La teoría de la computación comienza propiamente a principios del siglo XX, poco antes que las computadoraselectró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ónprecisa 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), KurtGö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 manerasdiferentes. 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 laconjetura 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 YuriGurevich 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...