Uncomputable Functions and Unsolvable 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 countably many computable functions. For example, functions may be encoded using a string of bits (the alphabet Σ = {0, 1} ).
The real numbers are uncountable so most real numbers are not computable. See 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.
Read more about this topic: Computable Function
Famous quotes containing the words functions and/or problems:
“Empirical science is apt to cloud the sight, and, by the very knowledge of functions and processes, to bereave the student of the manly contemplation of the whole.”
—Ralph Waldo Emerson (1803–1882)
“The truth of the thoughts that are here set forth seems to me unassailable and definitive. I therefore believe myself to have found, on all essential points, the final solution of the problems. And if I am not mistaken in this belief, then the second thing in which the value of this work consists is that it shows how little is achieved when these problems are solved.”
—Ludwig Wittgenstein (1889–1951)