Computer Science 531 Spring 2022 Homework Set 4A
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
2022-04-28