Relative computability
Appearance
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 a function
is called -computable if there exists an oracle machine with an oracle for which can compute
A set is called -recursive if its indicator function is -computable
Examples
- For any recursive set , -computability coincides with regular computability
See also
References
- R. I. Soare, "Computability and Recursion", Bulletin of Symbolic Logic 2 (1996), 284-321.