Kolmogorov Complexity proving there exists a constant for when if two strings are equal length - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-07-17T07:02:49Z https://cs.stackexchange.com/feeds/question/90242 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/90242 2 Kolmogorov Complexity proving there exists a constant for when if two strings are equal length ZeroDay Fracture https://cs.stackexchange.com/users/79425 2018-04-05T05:07:56Z 2018-04-08T06:43:12Z <p>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 </p> <blockquote> <p>$C(x) \leq |x| + c$ </p> </blockquote> <p>my question lies in finding that c for a given problem. </p> <p>Given this problem </p> <blockquote> <p>there is a constant $c$ $∈$ $\mathbb{N}$ such that, for $\forall$ x,y ∈ $\{0,1\}^+$ with $|x|=|y|$</p> <p>$H(x,y)$ is the hamming distance between $x$ and $y$</p> <p>$C(y)$ ≤ $C(x)$ $+ 2·H(x,y)·$(1 + $\lceil log|x|\rceil$)$+ c$ </p> </blockquote> <p>How would I go about mathematically proving there there is a constant $c$ $∈$ $\mathbb{N}$ what does finding a constant tell us</p> <blockquote> <p>Constant is defined as follows </p> <p>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)?</p> </blockquote> https://cs.stackexchange.com/questions/90242/-/90266#90266 2 Answer by Yuval Filmus for Kolmogorov Complexity proving there exists a constant for when if two strings are equal length Yuval Filmus https://cs.stackexchange.com/users/683 2018-04-05T17:57:12Z 2018-04-05T17:57:12Z <p>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.</p> <p>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)$.</p>