For a turing machine which computes $y$ with argument $x$, how much does the descriptional length of a machine producing $y$ without input increases

Question

Let $f$ be some function in some programming language (like C), and we need $n$ bits to store this function. Suppose we have some fixed value $v$ for the argument, then let

g() { f(v) }

be the function with no argument which just calles $f$ with $v$ as an argument. Then we need $n + |v| + C$ bits to store it, where $C$ is some constant which takes account of the additional bits needed to declare $g$, and this is independent of $v$ and $f$.

So in any programming language so far, to go from programs accepting parameters, to the one for a fixed parameter the desriptional complexity raises up at most by a fixed constant plus the descriptional length of $v$.

Does the same hold for Turing-machines? If I have a Turing-Machine which for input $x$ produces $y$, then to have a machine without accepting parameter to produce $y$ I can built one that first writes $x$ and then runs $M$, and a general machine that writes $x$ for any $x$ would be one that saves the tokens of $x$ in its states and writes them one after another. If I look at how instructions are specified in Turing machines, then we see that for $x$ we need $|x|\cdot C$ bits (with $C > 1$) then to store this additional machine, hence given $M$ with $M(x) = y$ we get a machine $M_x = y$ without arguments with $$ |M| + C|x| + C' $$ needed bits, where $C > 1$ and $C'$ account for some additional setup independent of $M$ and $x$.

But would it be possible to built a Turing machine $M_x$ with $M_x = y$ without input which has descriptional complexity at most $|M| + |x| + C'$ for some constant $C'$ independent of $M$ and $x$? Like above for ordinary programming languages?

Answer 1

First of all, there are two notions of Kolmogorov complexity, that Li and Vitanyi (in their classic monograph) call algorithmic complexity and algorithmic prefix complexity. Each of them is defined with respect to a universal computer which has a certain property.

Algorithmic complexity $C(x)$ has the property that for every computer $P$, if we denote by $C_P(x)$ the complexity of $x$ with respect to $P$, then $|C(x) - C_P(x)| \leq \gamma_P$, where $\gamma_P$ depends only on $P$. This property is known as universality.

Algorithmic prefix complexity $K(x)$ uses a computer in which the valid programs form a prefix code (a prefix computer), and we only require the universality property for prefix computers.

The actual definitions are slightly more complicated, since we also need to define, at the same time, the notion $C(x|y)$ or $K(x|y)$.

If you want to use some encoding of Turing machines as your definition of Kolmogorov complexity (of either kind), you need to use an encoding which is universal. But the point of Kolmogorov complexity is that which computer you use doesn't matter, since the resulting notions of Kolmogorov complexity only differ by an additive constant.

Finally, the Kolmogorov complexity analog of your "substitution" rule is $$ K(x) \leq K(x|y) + K(y) + O(1). $$ In fact, more is true: $$|K(x|y) + K(y) - K(x,y)| = O(1). $$ This holds for prefix complexity.