Editing Computability theory (section)

==Turing computability==
The main form of computability studied in the field was introduced by Turing in 1936.<ref name="Turing_1936"/> A set of natural numbers is said to be a ''[[computable set]]'' (also called a ''decidable'', ''recursive'', or ''Turing computable'' set) if there is a [[Turing machine]] that, given a number ''n'', halts with output 1 if ''n'' is in the set and halts with output 0 if ''n'' is not in the set. A function ''f'' from natural numbers to natural numbers is a ''(Turing) [[computable function|computable]],'' or ''recursive function'' if there is a Turing machine that, on input ''n'', halts and returns output ''f''(''n''). The use of Turing machines here is not necessary; there are many other [[model of computation|models of computation]] that have the same computing power as Turing machines; for example the [[μ-recursive function]]s obtained from primitive recursion and the μ operator.

The terminology for computable functions and sets is not completely standardized. 
The definition in terms of μ-recursive functions as well as a different definition of {{lang|de|rekursiv}} functions by Gödel led to the traditional name ''recursive'' for sets and functions computable by a Turing machine. The word ''decidable'' stems from the German word {{lang|de|Entscheidungsproblem}} which was used in the original papers of Turing and others. In contemporary use, the term "computable function" has various definitions: according to [[Nigel J. Cutland]],<ref name="Cutland_1980"/> it is a partial recursive function (which can be undefined for some inputs), while according to [[Robert I. Soare]]<ref name="Soare_1987"/> it is a total recursive (equivalently, general recursive) function. This article follows the second of these conventions. In 1996, Soare<ref name="Soare_1996"/> gave additional comments about the terminology.

Not every set of natural numbers is computable. The [[halting problem]], which is the set of (descriptions of) Turing machines that halt on input 0, is a well-known example of a noncomputable set. The existence of many noncomputable sets follows from the facts that there are only [[countable set|countably many]] Turing machines, and thus only countably many computable sets, but according to the [[Cantor's theorem]], there are [[uncountable set|uncountably many]] sets of natural numbers.

Although the halting problem is not computable, it is possible to simulate program execution and produce an infinite list of the programs that do halt. Thus the halting problem is an example of a ''[[computably enumerable set|computably enumerable (c.e.) set]]'', which is a set that can be enumerated by a Turing machine (other terms for computably enumerable include ''recursively enumerable'' and ''semidecidable''). Equivalently, a set is c.e. if and only if it is the range of some computable function. The c.e. sets, although not decidable in general, have been studied in detail in computability theory.