Editing Computable function (section)

== Uncomputable functions and unsolvable problems ==
{{main|List of undecidable problems}}

Every computable function has a finite procedure giving explicit, unambiguous instructions on how to compute it. Furthermore, this procedure has to be encoded in the finite alphabet used by the computational model, so there are only [[countability|countably]] many computable functions. For example, functions may be encoded using a string of bits (the alphabet {{math|&Sigma; {{=}} {0, 1}}}).

The real numbers are uncountable so most real numbers are not computable. See [[Computable number#Properties|computable number]]. The set of [[finitary]] functions on the natural numbers is uncountable so most are not computable. Concrete examples of such functions are [[Busy beaver]], [[Kolmogorov complexity]], or any function that outputs the digits of a noncomputable number, such as [[Chaitin's constant]].

Similarly, most subsets of the natural numbers are not computable. The [[halting problem]] was the first such set to be constructed. The [[Entscheidungsproblem]], proposed by [[David Hilbert]], asked whether there is an effective procedure to determine which mathematical statements (coded as natural numbers) are true. Turing and Church independently showed in the 1930s that this set of natural numbers is not computable. According to the Church–Turing thesis, there is no effective procedure (with an algorithm) which can perform these computations.