¿Qué significa que una función sea computable?
What does it mean for a function to be computable?
Although informally a function is computable if its values can be calculated, Alan Turing, Alonzo Church, and Kurt Godel each had formal definitions of computablility, namely Turing Machines, Lambda Calculus, and general recursive functions.  When it was shown in the Church-Turing thesis that these three formulations are equivalent, it became more clear that they could be used as a formal definition of computability.
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.
general_qa
es