Editing Computable function (section)

==Extensions of computability==

===Relative computability===

The notion of computability of a function can be [[relative computability|relativized]] to an arbitrary [[Set (mathematics)|set]] of [[natural number]]s ''A''. A function ''f'' is defined to be '''computable in ''A''''' (equivalently '''''A''-computable''' or '''computable relative to ''A''''') when it satisfies the definition of a computable function with modifications allowing access to ''A'' as an [[oracle (computability)|oracle]]. As with the concept of a computable function relative computability can be given equivalent definitions in many different models of computation. This is commonly accomplished by supplementing the model of computation with an additional primitive operation which asks whether a given integer is a member of ''A''. We can also talk about ''f'' being '''computable in ''g''''' by identifying ''g'' with its graph.

===Higher recursion theory===

[[Hyperarithmetical theory]] studies those sets that can be computed from a [[computable ordinal]] number of iterates of the [[Turing jump]] of the empty set. This is equivalent to sets defined by both a universal and existential formula in the language of second order arithmetic and to some models of [[Hypercomputation]]. 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.

===Hyper-computation===
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 models of computation that go beyond normal Turing computation.