[46] A set A N is K-trivial if its characteristic sequence = 12 ... satisfies K(1:n) K(n)+O(1). Certain properties of such sequences

• [46] A set A ⊆ N is K-trivial if its characteristic sequence

χ = χ1χ2 ... satisfies K(χ1:n) ≤ K(n)+O(1). Certain properties of such sequences were already established in Exercise 3.5.9, Items

(b) and (c).

Here we identify sets with their characteristic sequences.

(a) Show that all K-trivial sets are Δ0 2-definable.

(b) Show that the class of K-trivial sets is closed under ⊕, where ⊕ is defined for the corresponding characteristic sequences as in Exercise 3.5.8.

(c) Show that a set A is K-trivial iff it is low for the class of Martin-L¨of random sets, that is, every Martin-L¨of random set is already MartinL¨of random relative to Turing machines with A as an oracle. In particular, K-triviality is closed downward under Turing reducibility; see Exercise 1.7.16 on page 43.

(d) Show that a set A is K-trivial iff A is low for K, that is, K(x) ≤

KA(x) + O(1) for every x.

Comments. A great deal of recent computability-theory research deals with K-triviality, in particular with the incomputable K-trivial sequences.

They are incomputable, but only barely so, and in that sense not completely computably predictable. They are, so to speak, the sequences exhibiting the weakest form of randomness and form the other side of the random-sequence spectrum from the Martin-L¨of random sequences.

Source for Items

(a) and (b): [R.G. Downey, D.R. Hirschfeldt, A. Nies, and F. Stephan, Proc. 7th and 8th Asian Logic Confs, Singapore Univ.

Press, 2003, pp. 103–131]. Source for Items

(c) and (d): [A. Nies, Adv.

Math., 197:1(2005), 274–305].