la computación a principios del siglo xx

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étodouniversal 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.

Otro de losinventos mecánicos fue la Pascalina inventada por Blaise Pascal (1623 -
1662) de Francia y la de Gottfried Wilhelm von Leibniz (1646 - 1716) de Alemania. Con
estas máquinas, los datos se representabanmediante las posiciones de los engranajes,
y los datos se introducían manualmente estableciendo dichas posiciones finales de las
ruedas, de manera similar a como leemos los números en elcuentakilómetros de un
automóvil.

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 deTuring). 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 seencuentran 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 algoritmohabido 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 conjeturabasá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 elmá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...