George Barmpalias

  1. Universal computably enumerable sets and initial segment prefix-free complexity.

    Authors: George Barmpalias
    Subjects: Logic
    Abstract

    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.

Syndicate content