Leibniz (a quien conocemos en Matemáticas por crear el cálculo) soñaba con 2 cosas:
- Crear un lenguaje en el que se pudieran expresar problemas de cualquier tipo (filosóficos, políticos, sociales, etcétera).
- Encontrar un método que pudiera resolver todos los problemas expresados en este lenguaje.
Si nos restringimos puramente a los problemas matemáticos ¿el primer sueño de Leibniz se cumplió? La respuesta es que sí, pues se ha visto a lo largo de la licenciatura, en nuestros cursos de álgebra, geometría, probabilidad, etcétera, que hemos podido formular una gran gama de problemas matemáticos dentro de la teoría de conjuntos y la lógica de primer orden (, , ).
Reconocemos que el primer sueño se cumplió (al menos para las Matemáticas, lo cual ya es demasiado) pero ¿qué hay del segundo?
Hilbert lo planteó como un reto: el problema de la decisión (Entscheidungsproblem). Él realmente creía que tarde o temprano encontraríamos tal método.
Debemos saber, sabremos (pone su epitafio).
Sin embargo, en 1936 de manera independiente, Alonzo Church y Alan Turing rompieron los sueños e ilusiones del pobre Leibniz (y de Hilbert). Para ello, primero tuvieron que formalizar la noción intuitiva que había detrás de ese dichoso método. El cálculo lambda por un lado y las maquinas de Turing por el otro. Luego demostraron que había problemas que no se podían resolver con sus respectivos formalismos (Halting problem). Además, Turing probó que sus modelos eran equivalentes.
Hoy en día, nuestras computadoras siguen la arquitectura de Von Neumann, la cual está basada en el concepto de la máquina de Turing. Además, los lenguajes de programación imperativos y los ensambladores están basados en la forma en que trabaja una máquina de Turing: mediante una secuencia de instrucciones. Mientras que los lenguajes de programación funcionales están basados en el cálculo lambda.