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 extened his canonical systems to define a similar concept.

Definition

Given a set of natural numbers A, a function

$f:A\subseteq \mathbb {N} \to \mathbb {N}$

is called A-computable if there exists an oracle machine with an oracle for A which can compute f.

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

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
• Turing reduction
• Turing degrees

References

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