Jump to content

Relative computability

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by CBM (talk | contribs) at 22:44, 26 August 2006 (Definition: the previous definition used the letter ''A'' to mean two differnet things. I also added a defn of relative computable enumerability.). 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 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 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 1B 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

See also

References