Historia de la computabilidad

La idea de disponer de un algoritmo, o receta para efectuar alguna tarea, ha existido durante miles de años. También durante muchos años la gente creyó que si cualquier problema podía iniciarse demanera precisa, entonces con suficiente esfuerzo seria posible encontrar una solución con el tiempo(o tal vez una prueba de que no existe solución podría proporcionarse con el tiempo). En otraspalabras, se creía que no había problema que fuera tan intrínsicamente difícil que en principio nunca pudiera resolverse.

Uno de los grandes promotores de esta creencia fue el famoso matemático DavidHilbert. En cierta ocasión afirmo:
“Todo problema matemático definido debe ser necesariamente susceptible de un planteamiento exacto, ya sea en forma de una respuesta real a la pregunta planteada o debidoa la constatación de la imposibilidad de resolverlo, a lo que se debería la falla necesaria de todos los intentos… una de las cosas que nos atrae mas cuando nos dedicamos a un problema matemático esprecisamente que dentro de nosotros siempre escuchamos la llamada: e aquí el problema, busca la solución; puedes encontrarla por pensamiento puro, ya que en matemáticas no existe cosa alguna que nopueda conocerse.”

La meta de Hilbert era crear un sistema matemático formal en el que todos los sistemas pudieran plantearse con precisiones y términos de proposiciones que fueran verdaderas ofalsas. Su idea era encontrar un algoritmo que, dada cualquier proposición en el sistema formal, determinara si esa proposición era o no verdadera. Si Hilbert hubiera logrado este objetivo, entoncescualquier problema que estuviera bien definido podría haberse resuelto simplemente al ejecutar el algoritmo. Al decidir la verdad de una proposición dada en el sistema formal, Hilbert lo denominóentscheidungsproblem, considerándolo como un problema abierto fundamental en matemáticas.

Por desgracia para el objetivo de Hilbert, en la década de 1930 se produjo una serie de investigaciones que...