Item

(b) follows by appropriate modification of the reference machine. Source: The basic Equation 8.3 appears in

[P. G´acs, Lecture Notes on Descriptional Complexity and Randomness, Manuscript, Boston University, 1987; T.M. Cover, P. G´acs, and R.M.

Gray, Ann. Probab., 17:3(1989), 840–865; W.H. Zurek, Phys. Rev. A, 40(1989), 4731–4751] but the result is presumably older. A complex argument for Item

(a) in a physics setting is [C. Caves, pp. 91–115 in:

W.H. Zurek, ed., Complexity, Entropy and the Physics of Information, Addison-Wesley, 1991]. Item

(b) is spelled out in [R. Schack, Int. J. Theoret. Phys., 36(1997), 209–226]. The last two papers use the nonstandard complexity variant of Example 3.8.2, but this is not required to prove the result.