  We show that there are Turing complete computably enumerable sets of
arbitrarily low non-trivial initial segment prefix-free complexity. In
particular, given any computably enumerable set $A$ with non-trivial
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 $A_i, i<k$ with non-trivial initial segment
prefix-free complexity. An application of this gives a negative answer to a
question from \cite[Section 11.12]{rodenisbook} and \cite{MRmerstcdhdtd} which
asked for minimal pairs in the structure of the c.e.\ reals ordered by their
initial segment prefix-free complexity.
  Further consequences concern various notions of degrees of randomness. For
example, the Solovay degrees and the $K$-degrees of computably enumerable reals
and computably enumerable sets are not elementarily equivalent. Also, the
degrees of randomness based on plain and prefix-free complexity are not
elementarily equivalent; the same holds for their $\Delta^0_2$ and $\Sigma^0_1$
substructures.
