Church-Turing thesis

Main article: Church-Turing thesis

The Church-Turing thesis states that any function computable from a procedure possessing the three properties listed above is a computable function. Because these three properties are not formally stated, the Church-Turing thesis cannot be proved. The following facts are often taken as evidence for the thesis:

• Many equivalent models of computation are known, and they all give the same definition of computable function (or a weaker version, in some instances).
• No stronger model of computation which is generally considered to be effectively calculable has been proposed.

The Church-Turing thesis is sometimes used in proofs to justify that a particular function is computable by giving a concrete description of a procedure for the computation. This is permitted because it is believed that all such uses of the thesis can be removed by the tedious process of writing a formal procedure for the function in some model of computation.

Incomputable functions and unsolvable problems

Main article: List of undecidable problems

Every computable function has a finite procedure telling how to compute it. So there are only countably many computable functions.

That is, let Σ be a finite set of symbols. For example Σ = {0,1}. Then let Σ ^* be the set of all strings composed of symbols from Σ including the empty string.

So Σ ^* is an infinite set and in this example

Any infinite subset is countable. Because the elements of S can be sorted by length and placed in bijection to the natural numbers.

The set of all programs for a given computer is a subset of Σ ^* . So the set of all programs for a given computer is countable. So the set of computable functions is countable.

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. The Busy beaver function is a concrete example of such a function.

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.

Extensions of computability

The notion of computability of a function can be relativized to an arbitrary set of natural numbers A, or equivalently to an arbitrary function f from the naturals to the naturals, by using Turing machines (or any other model of computation) extended by an oracle for A or f. Such functions may be called A-computable or f-computable respectively.

Although the Church-Turing thesis states that the computable functions include all functions with algorithms, it is possible to consider broader classes of functions that relax the requirements that algorithms must possess. The field of Hypercomputation studies methods and procedures that can solve non-algorithmically decidable problems. Hyperarithmetical theory studies a different extension of standard computability. Even more general recursion theories have been studied, such as E-recursion theory in which any set can be used as an argument to an E-recursive function.