On the number of infinite sequences with trivial initial segment complexity
George Barmpalias and Tom Sterkenburg
Summary
The sequences which have trivial prefix-free initial segment
complexity are known as K-trivial sets, and form a cumulative hierarchy of length omega.
We show that the problem of finding the number of K-trivial sets in the various levels of the hierarchy
is $\Delta^0_3$. This answers a question of Downey/Miller/ Yu from Section 10.1.4
of the book Algorithmic Randomness and Complexity by Downey/Hirschfeldt which also appears as
Problem 5.2.16 in the book Computability and Randomness of A. Nies.
We also show the same for the hierarchy of the low for K sequences, which are
the ones that (when used as oracles) do not give shorter initial segment complexity
compared to the computable oracles. In both cases the classification $\Delta^0_3$
is sharp.