Codable sets and orbits of computably enumerable sets

A set X of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. Let ε denote the structure of the computably enumerable sets under inclusion, $\varepsilon = (\{W_e\}_{e\in \omega}, \subseteq)$. We previ...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of symbolic logic 1998-03, Vol.63 (1), p.1-28
Main Authors: Harrington, Leo, Soare, Robert I.
Format: Article
Language:English
Subjects:
Approximation
Automorphisms
Computability
Definability
Information content
Mathematical functions
Mathematical logic
Recursion
Recursively enumerable sets
Citations: Items that this one cites
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 X of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. Let ε denote the structure of the computably enumerable sets under inclusion, $\varepsilon = (\{W_e\}_{e\in \omega}, \subseteq)$. We previously exhibited a first order ε-definable property Q(X) such that Q(X) guarantees that X is not Turing complete (i.e., does not code complete information about c.e. sets). Here we show first that Q(X) implies that X has a certain "slowness" property whereby the elements must enter X slowly (under a certain precise complexity measure of speed of computation) even though X may have high information content. Second we prove that every X with this slowness property is computable in some member of any nontrivial orbit, namely for any noncomputable A ∈ ε there exists B in the orbit of A such that X ≤T B under relative Turing computability (≤T). We produce B using the Δ03-automorphism method we introduced earlier.
ISSN:0022-4812
1943-5886
DOI:10.2307/2586583