On the number of infinite sequences with trivial initial segment complexity
George Barmpalias, Tom Sterkenburg
Abstract:
The sequences which have trivial prefix-free initial segment
complexity are known as K-trivial sets, and form a cumulative
hierarchy of length ~. We show that the problem of finding the number
of K-trivial sets in the various levels of the hierarchy is
~^0_3. This answers a question of Downey/Miller/Yu (see [DH10, Section
10.1.4]) which also appears in [Nie09, Problem 5.2.16].
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 ~^0_3 is sharp.