Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4661790 | Annals of Pure and Applied Logic | 2013 | 14 Pages |
Abstract
We present an extended discussion of the existing research on this topic, along with recent developments and open problems. Besides this survey, our main original result is the following characterization of the computably enumerable sets with trivial initial segment prefix-free complexity. A computably enumerable set A is K-trivial if and only if the family of sets with complexity bounded by the complexity of A is uniformly computable from the halting problem.
Related Topics
Physical Sciences and Engineering
Mathematics
Logic
Authors
George Barmpalias, Angsheng Li,