Relative computability

In computability theory relative computability or relativized computability is the study of computability concepts relative to a given set. Most concepts in regular computability can be generalized to relative computability.

The first formal definition of relative computability, then called relative reducibility, was given by Alan Turing in 1939 in terms of oracle machines. Later in 1943 and 1952 Stephen Kleene defined an equivalent concept in terms of recursive functions. In 1948 Emil Post extended his canonical systems to define a similar concept.

Definition

Given a set of natural numbers A and a natural number k, a partial function $f\colon \mathbb {N} ^{k}\rightarrow \mathbb {N}$ is called A-recursive or A-computable if there exists an oracle machine which computes f when given an oracle for A.

A set B is called A-recursive or A-computable if its indicator function 1_B is A-computable.

A set B is called A-recursively enumerable or A-computably enumerable if there is an A-computable function whose domain is exactly the set B. This is equivalent to the existence of an A-computable function whose range is B.

Examples

• For any recursive set A, a function f as above is A-computable iff it is computable in the usual sense.

See also

• Turing equivalence (recursion theory)
• Turing reduction
• Turing degrees

References

• R. I. Soare, "Computability and Recursion", Bulletin of Symbolic Logic 2 (1996), 284-321.