Page 1 of 1
Problem 5. Let C(x) = Cu(x) be the Kolmogorov complexity of a word z relative to some fixed optimal description mode U.
Posted: Fri May 20, 2022 2:33 pm
by answerhappygod
- Problem 5 Let C X Cu X Be The Kolmogorov Complexity Of A Word Z Relative To Some Fixed Optimal Description Mode U 1 (33.51 KiB) Viewed 38 times
Problem 5. Let C(x) = Cu(x) be the Kolmogorov complexity of a word z relative to some fixed optimal description mode U. a) Prove that there exists some constant M such that for all x |C(x0) - C(x1)| < M. b) Show that for all sufficiently large n there exist such words yn, yn that differ in only one bit, but C(yn) < 2n, Clyn) > 2".