Question

Show that for any ,$\mathit{c}$ some strings $\mathit{x}$and $\mathit{y}$ exist, where$\mathit{K}\mathbf{\left(}\mathbf{x}\mathbf{y}\mathbf{\right)}\mathbf{>}\mathit{K}\mathbf{\left(}\mathbf{x}\mathbf{\right)}\mathbf{+}\mathit{K}\mathbf{\left(}\mathbf{y}\mathbf{\right)}\mathbf{+}\mathit{c}$

Short answer

It is proved that .$K\left(xy\right)=K\left(x\right)+K\left(y\right)+c$

Step-by-step solution

Assuming a Turing Machine

Assume a Turing Machine $M$ where$w$ is string as input.

Also,$x\in w$ where$x$, is binary string in .$w$

Let$d\left(x\right)=$ Minimum description as shortest string in .$w$

We can say that the description complexity of:$x$

$\mathbf{K}\left(\mathbf{x}\right)=\left|\mathbf{d}\left(\mathbf{x}\right)\right|$

Now, we have string $xy$ which can be decomposed as$x$and .$y$

We will consider $c=$value use to match left and right side

Now let us assume a Turing Machine $T$ which will break the input string $w$ into two parts as $d\left(x\right)$ and $d\left(y\right)$, and we can combine both parts at any instance

Conclusion from observation of Step 1

Now, we can obtain both the parts, can make them run simultaneously to get string$x$and$y$, and can again concatenate them to get $xy$as combine.

It is very clear from above that $Length\left(xy\right)>Length\left(x\right)$ or $Length\left(y\right)$. We can use constant term ‘$c$’ which will balance the $xy$ and individual .$part(x,y)$

This shows that descriptive complexity of $xy$will be greater than individual descriptive complexity of$x$and$y$.

Hence we can say that:

$K\left(xy\right)>K\left(x\right)+K\left(y\right)$

Or$K\left(xy\right)=K\left(x\right)+K\left(y\right)+c$

$K\left(xy\right)=K\left(x\right)+K\left(y\right)+c$