Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Computer Science 531

Spring 2022

Homework Set 4A

Problem 25. Let pX,pq be an ensemble. Prove that, for every t ą 0,

HpX,pq ě Probrppxq ď ts log

Problem 26. Prove that there does not exist a constant c P N such that, for all x P Σ˚ , Kpxq ď |x| ` c

Problem 27. For each n P N, let

xn  “ b0 b1 ...bn´1

be the n-bit string whose i-th bit, for each 0 ď i ă n, is

#

Prove that there is a constant c P N such that, for all n P N,

Kpxnq ď 4logpn ` 1q ` c

Problem 28. Prove that, for every computable partial function f :Ď Σ˚ Ñ Σ˚ , there is a constant cf  P N such that, for all x P domf ,

Kpfpxqq ď Kpxq ` cf