Historia De La Teoría De La Computacion

ÍNDICE

Introducción..................................................................................... 3

Alan Turing (Máquina de Turing, Tésis Chruch-Turing)..................................... 4

Norberto Weiner, Alfredo Tarski....................................................... 5

Historia de la Teoría de la Computación

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.

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.

La historia de la lógica para la computación se inicia con la Revolución digital, esta revolución se inició con la invención de la computadora digital y el acceso universal a redes de alta velocidad. Alan Turing fue el que unió a la lógica y la computación antes que cualquier computadora fuera inventada. Weiner funda la ciencia de la cibernética. En la escuela moderna de la computación están presentes lógicos que han permitido avances importantes: Hoare presenta un sistema axiomático de los sistemas de programación y Dijkstra un sistema de verificación y deducción de programas a partir de especificaciones.

Alan Turing

Matemático y lógico quien fue pionero en la teoría de la computación y contribuyó en importantes análisis lógicos de los procesos computacionales. Las especificaciones para la computadora abstracta que él ideó (llamada la máquina de Turing) resultó ser

...