I think what can be found in that book is a proof of the coding theorem, which is different from the claim you call the “Levin bound” here, I think. What you call the Levin bound is proved in this paper and has a much simpler proof than the coding theorem.
I think what can be found in that book is a proof of the coding theorem, which is different from the claim you call the “Levin bound” here, I think. What you call the Levin bound is proved in this paper and has a much simpler proof than the coding theorem.