¿Qué significa que una función sea computable?
Aunque informalmente una función es computable si sus valores pueden calcularse, Alan Turing, Alonzo Church y Kurt Godel tenían sendas definiciones formales de computabilidad, a saber, las máquinas de Turing, el cálculo lambda y las funciones recursivas generales.  Cuando se demostró en la tesis de Church-Turing que estas tres formulaciones son equivalentes, quedó más claro que podían utilizarse como definición formal de la computabilidad.