Computable function

Summary

A computable function is a function on the natural numbers whose values can be calculated by an algorithm. Formally, it is a partial function computed by a Turing machine, and this class equals the class of partial general recursive functions. Computable functions are the central objects of computability theory. Some functions, such as the one that tells whether a program halts, are well defined but not computable.