A function is considered computable if, and only if, it satisfies the following conditions as set out in the Church-Turing Thesis:
- There are exact instructions that are finite in length. It is possible to compute the function without any guessing or intuition, just following the steps.
- Given infinite time and resources, It must complete in finite time
- The instructions must be encoded in a finite set. For example, a binary function is encoded in
- It can be computed by a human with unlimited time and an unlimited supply of pen and paper could follow.
Not Computable: Uncountable sets
The real numbers are uncountable, so most real numbers are not computable. The set of finitary functions on the natural numbers is uncountable, so most are not computable. Examples of such functions are Busy Beaver and the Kolmogorov complexity. #TOSEE
Similarly, most subsets of the natural numbers are not computable. The Halting Problem was the first such set to be constructed. Turing and Church independently showed that this set of natural numbers is not computable. According to the Church-Turing Thesis, there is no effective procedure (with an algorithm) that can perform these computations.