Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426014 | Information and Computation | 2013 | 19 Pages |
Abstract
We show that there are Turing complete computably enumerable sets of arbitrarily low nontrivial initial segment prefix-free complexity. In particular, given any computably enumerable set A with nontrivial prefix-free initial segment complexity, there exists a Turing complete computably enumerable set B with complexity strictly less than the complexity of A. On the other hand it is known that sets with trivial initial segment prefix-free complexity are not Turing complete.Moreover we give a generalization of this result for any finite collection of computably enumerable sets AiAi, i
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
George Barmpalias,