Algebraic Aspects of the Computably Enumerable Degrees

A set A of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. The class of sets B which contain the same information as A under Turing computability (≤T) is the (Turing) degree of A, and a degree is c...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of the National Academy of Sciences - PNAS 1995-01, Vol.92 (2), p.617-621
Main Authors: Slaman, Theodore A., Soare, Robert I.
Format: Article
Language:English
Subjects:
Algebra
Computability
Integers
Mathematical functions
Mathematical sets
Mathematical theorems
Mathematics
Minimal pairs
Partially ordered sets
Unsolvability
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A set A of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. The class of sets B which contain the same information as A under Turing computability (≤T) is the (Turing) degree of A, and a degree is c.e. if it contains a c.e. set. The extension of embedding problem for the c.e. degrees mathscrR = (R,
ISSN:0027-8424
1091-6490
DOI:10.1073/pnas.92.2.617