Article ID Journal Published Year Pages File Type
426014 Information and Computation 2013 19 Pages PDF
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
,