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

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

• the procedure you talk about is the Turing machine that computes P? could you also briefly elaborate on the invariance property of kolmogorov complexity? – ZeroDay Fracture Apr 5 '18 at 23:59
• No, the procedure accepts P (and DIFF) as inputs. – Yuval Filmus Apr 6 '18 at 4:44
• 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. – Yuval Filmus Apr 6 '18 at 4:46
• The basic approach is what I use in my answer. Another basic technique is dovetailing. – Yuval Filmus Apr 6 '18 at 4:51
• 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? – ZeroDay Fracture Apr 8 '18 at 6:49