When talking about kolmogorov complexity, I understand that it describes true randomness of given (for now) a string $x$, if we can describe x in less than the $|x|$ then its complexity is said to be

$C(x) \leq |x| + c$

my question lies in finding that c for a given problem.

Given this problem

there is a constant $c$ $∈$ $\mathbb{N}$ such that, for $\forall$ x,y ∈ $\{0,1\}^+$ with $|x|=|y|$

$H(x,y)$ is the hamming distance between $x$ and $y$

$ C(y)$$C(x)$ $+ 2·H(x,y)·$(1 + $ \lceil log|x|\rceil $)$ + c$

How would I go about mathematically proving there there is a constant $c$ $∈$ $\mathbb{N}$ what does finding a constant tell us

Constant is defined as follows

as in what does this given a TM M and universal TM $u$ s.t. there exists a constant $c_M$ s.t. $C_u(x) \leq C_M(x) + c_M$(From Solomonoff and turing's theorem)?

  • $\begingroup$ What do you mean by "optimality constant"? $\endgroup$
    – D.W.
    Apr 5, 2018 at 16:27
  • $\begingroup$ I think it says that given a universal TM u and a standard TM M that computes x we get the optimality constant to be $C_u(x) \leq C_M(x) + c_M$ . so a universal TM is always going to be optimal. I guess you could just say constant if that makes more sense $\endgroup$ Apr 5, 2018 at 16:46
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/90242/755, cstheory.stackexchange.com/q/40531/5038. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$
    – D.W.
    Apr 7, 2018 at 0:03

1 Answer 1


Consider a procedure which has two inputs, $P$ and $DIFF$. Here $P$ is a self-delimiting program, and $DIFF$ is a list of indices, stored in some self-delimiting fashion (we leave the encoding vague for now). The procedure runs $P$, flips all the indices in $DIFF$, and prints the output. Using the invariance property of Kolmogorov complexity, we immediately get that there is a program of length $|P|+|DIFF|+O(1)$ which simulates the procedure above.

Now take any two vectors $x,y$. Let $P$ be a self-delimiting program of size $C(x)$ producing $x$, and let DIFF be the list of differences, which can be encoded using $H(x,y)(1+\lceil \log |x| \rceil)$ bits (this improves on your exercise; we're using the fact that $|x|$ is known by the procedure). It follows that $C(y) \leq C(x) + H(x,y)(1+\lceil \log |x| \rceil) + O(1)$.

  • $\begingroup$ the procedure you talk about is the Turing machine that computes P? could you also briefly elaborate on the invariance property of kolmogorov complexity? $\endgroup$ Apr 5, 2018 at 23:59
  • $\begingroup$ No, the procedure accepts P (and DIFF) as inputs. $\endgroup$ Apr 6, 2018 at 4:44
  • $\begingroup$ The invariance property states that we can simulate every "computer" at an additive loss. I don't remember the official name of the property, but it's a basic feature of Kolmogorov complexity, so you probably learned it. $\endgroup$ Apr 6, 2018 at 4:46
  • $\begingroup$ The basic approach is what I use in my answer. Another basic technique is dovetailing. $\endgroup$ Apr 6, 2018 at 4:51
  • $\begingroup$ I understand your skeleton proof completely, just confused on small part about the self-delimiting program P. is this analogous in saying P is shortest description for the string x? $\endgroup$ Apr 8, 2018 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.