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?

  • $\begingroup$ I recommend reading about Kolmogorov complexity, where these issues are clarified. $\endgroup$ Apr 20 '17 at 10:09
  • $\begingroup$ Could you please be more specific? Actually these issues arised as I was reading about Kolmogorov complexity! $\endgroup$
    – StefanH
    Apr 20 '17 at 10:38
  • 1
    $\begingroup$ It depends what encoding you use. Kolmogorov complexity suggests using an encoding which satisfies some universality property. Moreover, the encoding can either be self-terminating or not. The answer depends on these issues. $\endgroup$ Apr 20 '17 at 10:41
  • $\begingroup$ A universal encoding will look more like C than a textbook-style Turing machine. Indeed, there is nothing particularly important about Turing machines, which in many regards are not a good choice for modeling computation. $\endgroup$ Apr 20 '17 at 10:43
  • $\begingroup$ When we can do this, than Kolmogorov complexity would be subadditive as we can encode the input in the machine with overhead independent of $x$, build a machine that executes both and hence have a description for the concatenation. This is related to this question of mine: cstheory.stackexchange.com/questions/38033/… I thought if that would not be possible in the world of Turing machines than the failure of subadditivity would be more justified $\endgroup$
    – StefanH
    Apr 20 '17 at 11:18

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.

  • $\begingroup$ In what sense does this answers the question if we can encode a fixed argument just with a constant overhead independent of the argument into a new machine? Do you got what I was asking? $\endgroup$
    – StefanH
    Apr 20 '17 at 12:01
  • $\begingroup$ The answer to your question is that it is (i) ill-defined, and (ii) the property you want holds for algorithmic prefix complexity. This suggests that instead of exploring encodings of Turing machines (which is not well-defined), you should just stick to the usual notions of Kolmogorov complexity, which are intended to capture such properties. $\endgroup$ Apr 20 '17 at 12:06
  • $\begingroup$ Personally I am not too interested in Turing machines, and even less in their encodings, but perhaps you'll find a more sympathetic expert in the crowd. $\endgroup$ Apr 20 '17 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.