# Kolmogorov Complexity proving there exists a constant for when if two strings are equal length

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

• What do you mean by "optimality constant"?
– D.W.
Apr 5 '18 at 16:27
• 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 Apr 5 '18 at 16:46
• 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.
– D.W.
Apr 7 '18 at 0:03

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