English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We show that there are Turing complete computably enumerable sets ofarbitrarily low non-trivial initial segment prefix-free complexity. Inparticular, given any computably enumerable set $A$ with non-trivialprefix-free initial segment complexity, there exists a Turing completecomputably enumerable set $B$ with complexity strictly less than the complexityof $A$. On the other hand it is known that sets with trivial initial segmentprefix-free complexity are not Turing complete.  Moreover we give a generalization of this result for any finite collection ofcomputably enumerable sets $A_i, i<k$ with non-trivial initial segmentprefix-free complexity. An application of this gives a negative answer to aquestion from \cite[Section 11.12]{rodenisbook} and \cite{MRmerstcdhdtd} whichasked for minimal pairs in the structure of the c.e.\ reals ordered by theirinitial segment prefix-free complexity.  Further consequences concern various notions of degrees of randomness. Forexample, the Solovay degrees and the $K$-degrees of computably enumerable realsand computably enumerable sets are not elementarily equivalent. Also, thedegrees of randomness based on plain and prefix-free complexity are notelementarily equivalent; the same holds for their $\Delta^0_2$ and $\Sigma^0_1$substructures.

Universal computably enumerable sets and initial segment prefix-free complexity