Editing Computability theory (section)

==Name==
The field of mathematical logic dealing with computability and its generalizations has been called "recursion theory" since its early days. [[Robert I. Soare]], a prominent researcher in the field, has proposed<ref name="Soare_1996"/> that the field should be called "computability theory" instead. He argues that Turing's terminology using the word "computable" is more natural and more widely understood than the terminology using the word "recursive" introduced by Kleene. Many contemporary researchers have begun to use this alternate terminology.{{efn|[[MathSciNet]] searches for the titles like "[[computably enumerable]]" and "c.e." show that many papers have been published with this terminology as well as with the other one.}} These researchers also use terminology such as ''partial computable function'' and ''computably enumerable ''(''c.e.'')'' set'' instead of ''partial recursive function'' and ''recursively enumerable ''(''r.e.'')'' set''. Not all researchers have been convinced, however, as explained by Fortnow<ref name="Fortnow_2004"/> and Simpson.<ref name="Simpson_1998"/>
Some commentators argue that both the names ''recursion theory'' and ''computability theory'' fail to convey the fact that most of the objects studied in computability theory are not computable.<ref name="Friedman_1998"/>

In 1967, Rogers<ref name="Rogers_1987"/> has suggested that a key property of computability theory is that its results and structures should be invariant under computable [[bijection]]s on the natural numbers (this suggestion draws on the ideas of the [[Erlangen program]] in geometry). The idea is that a computable bijection merely renames numbers in a set, rather than indicating any structure in the set, much as a rotation of the Euclidean plane does not change any geometric aspect of lines drawn on it. Since any two infinite computable sets are linked by a computable bijection, this proposal identifies all the infinite computable sets (the finite computable sets are viewed as trivial). According to Rogers, the sets of interest in computability theory are the noncomputable sets, partitioned into equivalence classes by computable bijections of the natural numbers.