In Kikuchi's paper Kolmogorov complexity and the second incompleteness theorem the Kolmogorov Complexity (KC) of $x$ is defined s

$$ K(x) = \mu e (\varphi_e(0) \simeq x) \, . $$

This seems to give exponentially larger outcomes then the more common (rough) definition of $K(x)$ as "the length of the smallest computer program running on some fixed universal TM that returns $x$". One example where this influences the theory of KC is in the simple and often used lemma "$K(x) \leq \log x + c$ for some fixed constant $c$", which appears false under Kikuchi's definition.

How does Kikuchi's definition match up with the usual KC definition? To what degree does the chosen admissible enumeration of the partial computable functions play a role? I don't see an easy fix to the above problem. Kikuchi's definition seems fundamentally different, already because no two strings can have the same KC under it. Or is it just a typo and did he actually mean $ K(x) = \mu |e| (\varphi_e(0) \simeq x) $? It doesn't seem that way however, as then Lemma 2.1 wouldn't make any sense.

I cross posted a version of this question on MO, since I don't expect an answer here anymore.


1 Answer 1


Well, I don't think this is an answer, I have a lot of doubts about it, I would make a comment, but it is too large. I will share some thoughts about this expanding in the direction you are thinking. I don't understand fully the topic, so I would like to know if more people agree with the following.

I will use $K$ for this complexity you mentioned and $C$ for the usual one.

We can turn a partial computable universal function multi-variable function like $\phi(x,y)$ into a single variable function $\phi(c(x,y))$ with a suitable coding like: $1^x0y$, or $1^{|x|}0xy$. We are thinking of strings and number as the same thing here, because of the lexicographical bijection between $\mathbb{N}$ and the strings $\{0,1\}^*$ (note that on this bijection 0 goes to the empty string $\varepsilon$).

So, If we have a universal $\phi$ that works with let say the first of the coding above, we have:

$$\phi_p(c(0)) = \phi(c(p,0) ) = \phi(c(p))$$

The first equality by the enumeration theorem, the second one because in this coding $0 = \epsilon$. We are gonna drop the $c$ assume we can do $\phi= \psi \circ c$, with a $\psi$ that works codding the input. With this we can also define $C$ as additively optimum ($C(x) \leq C_\phi(x)+x$) in the usual way, as described by Li and Vitányi book.

The $\mu$ operator on partial recursion functions operates like: if the sentence $...x...$ is true for some $x$, then $\mu x(...x...)$ is the smallest $x$ for which $...x... $ is true.

So we have:

$$ K(x) = \mu p( \phi_p(0) =x) = \mu p(\phi(p) = x ) = \min \{ p : \phi(p) =x \}$$

Well the last sentence is by definition the minimal program $x^*$ with respect to this $\phi$. And we have:

$$C(x) = | x^*|= | K(x) |$$

And we know that by the lexicographic bijection that ($\log$ is the floor log function of base 2 like the one on Li Vitańyi text):

$$C(x) = |K(x)| = \log (K(x))$$

So yes, $K(x)$ behaves exponentially with respect to $C(x)$.

Raatkainen uses this complexity mesure in his article: On Interpreting Chaitin's Incompleteness Theorem, p. 574, and says that $K(x)$ coincides with usual way to define $C(x)$. I think he is saying that with respect only to incompleteness results. Because the function $\log$ is monotonic, formulas using $\leq$ of the type $(...K(x)... \leq ...)$ could be translated to $(... C(x) ... \leq...)$ changing every number of the kind $y$ by $\log(y)$. In this sense, we could argue that if we proof that: $K(x) > c$ is unprovable on a theory $T$, then $C(x) > \log(c)$ would also be unprovable. So I think it could be argued that the results with $K(x)$ could be translated to the conventional $C(x)$ with respect to incompleteness, if we translate it properly.

I can't see how the admissible enumeration will play a role here. If we have a enumeration $\phi_0,...,\phi_n,...$ we couldn't argue that there is an admissible system of index $\psi_0,...,\psi_n$ such that the indexes $0,...,n...$ are the size of the programs. For we have more than one program of the same size that gives the same output, any computable $f$ that goes from the system of indices for $\psi$ to the system $\phi$ would not be surjective.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .