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)?


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)$.

| cite | improve this answer | |
  • $\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$ – ZeroDay Fracture Apr 5 '18 at 23:59
  • $\begingroup$ No, the procedure accepts P (and DIFF) as inputs. $\endgroup$ – Yuval Filmus Apr 6 '18 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$ – Yuval Filmus Apr 6 '18 at 4:46
  • $\begingroup$ The basic approach is what I use in my answer. Another basic technique is dovetailing. $\endgroup$ – Yuval Filmus Apr 6 '18 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$ – ZeroDay Fracture Apr 8 '18 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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