Jump to content

Relative computability

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Gauge (talk | contribs) at 04:27, 19 September 2005 (Definition: clean up definition). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

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 1B is A-computable.

Examples

  • For any recursive set , -computability coincides with regular computability

See also

References