# Can we not output the Kolmogorov complexity?

Let us fix a prefix-free encoding of Turing-machines and a universal Turing-machine $U$ that on input $(T,x)$ (encoded as the prefix-free code of $T$ followed by $x$) outputs whatever $T$ outputs on input $x$ (possibly both running forever). Define the Kolmogorov complexity of $x$, $K(x)$, as the length of the shortest program $p$ such that $U(p)=x$.

Is there a Turing machine $T$ such that for every input $x$ it outputs an integer $T(x)\le |x|$ that is different from the Kolmogorov complexity of $x$, i.e., $T(x)\ne K(x)$ but $\liminf_{|x|\rightarrow \infty} T(x)=\infty$?

The conditions are necessary, because

(a) if $T(x)\not \le |x|$, then it would be easy to output a number that is trivially different from $K(x)$ because it is bigger than $|x|+c_U$,

(b) if $\liminf_{|x|\rightarrow \infty} T(x)<C$ is allowed, then we can just output $0$ (or some other constant) for almost all numbers, by "luckily" guessing the at most one (finitely many numbers) that evaluate to $0$ (to some other constant) and output there something else. We can even guarantee $\limsup_{|x|\rightarrow \infty} T(x)=\infty$ by outputting something like $2\log n$ for $x=2^n$.

Also note that our job would be easy if we know that $T(x)$ is not surjective, but little is known about this, so the answer might depend on $U$, though I doubt it would.

I know that relations are studied a lot in general, but

Has anyone ever asked a similar question where our goal is to give an algorithm that does not output some parameter?

My motivation is this problem http://arxiv.org/abs/1302.1109.

• It depends on your encoding, since as mentioned in the topic on surjectivity of $K$ you link to, it could be the case that only programs $p$ of even length are valid. So to make your question non-trivial you need to have more hypotheses on the encoding. – Denis Apr 26 '15 at 22:26
• To your second question: yes. Given an integer $M$, let $[M]$ denote the $M$-th Turing machine. A diagonally non-recursive (or DNR) function is a function $f\colon \mathbb{N} \to \mathbb{N}$ such that for all integers $M$, $[M](M) \neq f(M)$. (That is, if $[M]$ halts on $M$, then $f(M) \neq [M](M)$, and otherwise $f(M)$ can be arbitrary.) These have been studied quite a bit recently in the computability / computable randomness community. Google "diagonally non-recursive" to find papers on this. – Joshua Grochow Apr 26 '15 at 23:52
• @Denis: I think you are wrong. According to my definition of universal Turing-machines given in the first para, all lengths can be valid programs. – domotorp Apr 27 '15 at 4:16
• A few times ago I thought (in vain) about an apparently simpler version: (dis)proving that for large enough $x_0$, $K(x) \neq |x|/2$ for all $x \geq x_0$. – Marzio De Biasi Apr 27 '15 at 7:00
• @Ricky: That's fine, I have no restrictions on the encodings of the Turing machines, only on the programs, that you can read in the first para. – domotorp Apr 27 '15 at 7:24

The question can be rephrased as whether or not $\lim \inf_{\vert x \vert \rightarrow \infty}{\vert T(x) - K(x) \vert} = 0$, and as Denis points out in the comments this is false for some encodings. Here is a weaker statement and an attempted proof of it that doesn't depend on any details of the encoding, but I'll assume a binary language for simplicity:

Let $T:\{0,1\}^* \rightarrow \mathbb{N}$ be a computable function satisfying $0 \le T(x) \le \vert x \vert$ and $\lim \inf_{\vert x \vert \rightarrow \infty}{T(x)} = \infty$. Then $\lim \inf_{\vert x \vert \rightarrow \infty}{\vert T(x) - K(x) \vert} \lt \infty$. Informally, if there is a target around each string's Kolmogorov complexity that grows unboundedly wide, no computable function can avoid hitting it.

To see this, let $n$ be a random $b$-bit number, i.e. $0 \le n \lt 2^b$ and $K(n) \ge b$. For all $b$ such a random $n$ exists. Also note that there are an infinite number of values of $b$ for which $\vert \{T(x) = b\} \vert \ge 2^b$, this follows from the conditions placed on $T$. Now let $x$ be the $n^{\text{th}}$ smallest string such that $T(x) = b$. Clearly there is a constant $c_1$ such that $K(x) \gt b - c_1$, because $K(n) \ge b$ and $n$ can be computed from $x$. And there is a constant $c_2$ such that $K(x) \lt b + c_2$, because $K(n)$ is also bounded from above by only a constant more than $b$, and $x$ can be computed from $n$. Then $\vert K(x) - T(x) \vert \lt c_1 + c_2$, and we have an infinite number of choices for $b$ (those with a preimage of cardinality at least $2^b$), yielding an infinite number of values for $x$, so we are done.

An implication is that for some $c \in \mathbb{Z}$, $T(x) = K(x) + c$ infinitely often. So one might say we can't not output something that's not the Kolmogorov complexity!

• Nice, I think this should work. Of course, there might not be any strings with $f(x)=b$, so maybe you want to require $f(x)\ge b$, right? – domotorp Feb 9 '16 at 18:04
• It needs to be $f(x)=b$ so that $n$ is computable from $x_{b,n}$. So, I guess one needs to choose $b$ so that $\ge2^{b+1}$ or so strings map to it. Presumably, the assumptions should imply there are infinitely many such $b$ (though I don’t quite see it at the moment). (As far as I can tell, the assumptions have not been used in any other way.) – Emil Jeřábek supports Monica Feb 9 '16 at 18:16
• Yes, indeed this is needed. But the proof is easy by contradiction - if it is always $<2^b$ if $b>b_0$, then by looking at any range $b_0<b\le B$, we can conclude that at least $B-b_0$ strings are mapped to $\le b_0$, thus infinitely many, which contradicts $\liminf=\infty$. – domotorp Feb 9 '16 at 20:52
• What Denis talks about does not apply to the way I have defined universality in the first line of my question. His remark is also trivial, I have no clue why so many people have upvoted his comment. But alas, also Peter's incorrect answer received so many upvotes, I'm loosing faith in this site... – domotorp Feb 10 '16 at 8:47
• It doesn't matter how the TMs are encoded, as long as my criteria about the universal TM is satisfied, so Denis's comment is incorrect. If it was stated as a remark about another model, then it would be a different thing. Anyhow, instead of moping over this, let's try to see if we can strengthen your idea... – domotorp Feb 10 '16 at 14:11

I think the following works. I'll use $C(x)$ for the Kolmogorov complexity

• Give $U$ a time bound $t$ (say, some exponential function of the length of the input program), and call the result $U^t$. If a program exceeds the timebound, $U^t$ enters an infinite loop.
• Let $C^t(x)$ be the shortest program for $x$ on $t$. Note that $C^t$ is computable.
• Let $T(x)$ return $C^t(x) + 1$, unless this value is equal to $|x|$ in which case return 0. Unless $x$ is the output of the empty program, in which case return 1.
• Since $C(x) \leq C^t(x)$, $T(x)$ will always be different from $C(x)$. The logic in the previous step takes care of the edge cases.
• $U^t$ functions as a code for all strings, so it has limit inferior infinity.
• a couple of comments, KC theory in an alternative (but equivalent) interpretation states the following: Almost all strings are already in their optimum representation (wrt to a given model) except denumerable many strings which can be transformed into an optimum representation (minimum) w.r.t to a given computation model (or TM). In this sense almost every program outputs optimum string representations, but these are not known (or computable) a-priori – Nikos M. Jan 31 '16 at 22:54
• Why will you have $T(x)\le |x|$? – domotorp Feb 1 '16 at 9:31
• @domotorp Technically we have $T(x) \leq |x| + c$ where $c$ is the length of the shortest print program. Of course, this constant is also there for $C(x)$ (and in fact, unless the print program is really slow, it's the same constant). – Peter Feb 1 '16 at 12:45
• But this is what makes the whole question interesting! I could have asked any function instead of $|x|$, e.g., $|x|/2+99$, my only objective was to eliminate solutions similar to yours. – domotorp Feb 1 '16 at 14:20
• @domotrop I see, so you want to force $T(x)$ to not be an upperbound to $C(x)$. That is more interesting... – Peter Feb 1 '16 at 14:45