<p>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:</p>

<p>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.</p>

<p>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.</p>

<p>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!</p>

CC BY-SA 3.0
2016-02-09T18:04:16.893Z
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
CC BY-SA 3.0
2016-02-09T18:16:41.100Z
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
CC BY-SA 3.0
2016-02-09T20:52:28.503Z
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
CC BY-SA 3.0
2016-02-10T08:47:50.120Z
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
CC BY-SA 3.0
2016-02-10T14:11:47.290Z
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
CC BY-SA 3.0
2016-02-10T15:08:39.330Z
@domotorp As one of those who upvoted Denis’s comment, let me explain: it was easy to miss on first reading that you took precautions against such pathological TM, and since comment upvotes are frozen after a ridiculously short time (1minute?), I couldn’t retract my vote upon realizing that. I should be more careful, I know, but there you go. Combined with the fact that it’s impossible to *downvote* comments, it’s really easy for a comment incorrect in a nontrivial way to collect a number of upvotes.
Emil Jeřábek
CC BY-SA 3.0
2016-02-10T20:54:07.120Z
@Emil Wow, that gave back my faith, thx! (Unfortunately I cannot upvote your comment, as I wanted to test the undo function and apparently you cannot reupvote - I wonder why?)
domotorp
CC BY-SA 3.0
2016-02-09T17:31:28.017Z
2016-02-18T04:24:24.560Z
2016-02-18T04:24:24.560Z
Dan Brumleve
<p>I think the following works. I'll use $C(x)$ for the Kolmogorov complexity </p>

<ul>
<li>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.</li>
<li>Let $C^t(x)$ be the shortest program for $x$ on $t$. Note that $C^t$ is computable.</li>
<li>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.</li>
<li>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.</li>
<li>$U^t$ functions as a code for all strings, so it has limit inferior infinity.</li>
</ul>

CC BY-SA 3.0
2016-01-31T22:54:24.050Z
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.
CC BY-SA 3.0
2016-02-01T09:31:02.290Z
Why will you have $T(x)\le |x|$?
domotorp
CC BY-SA 3.0
2016-02-01T12:45:29.703Z
@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
CC BY-SA 3.0
2016-02-01T14:20:49.760Z
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
CC BY-SA 3.0
2016-02-01T14:45:38.173Z
@domotrop I see, so you want to force $T(x)$ to not be an upperbound to $C(x)$. That is more interesting...
Peter
CC BY-SA 3.0
2016-02-01T15:24:17.030Z
Also couldn't this program output 0 infinitely often?  That would violate the lim inf requirement.
Dan Brumleve
CC BY-SA 3.0
2016-02-02T10:23:26.607Z
@Dan: Yeah, you're right, that seems to be another issue.
domotorp
CC BY-SA 3.0
2016-01-31T19:35:06.137Z
2016-01-31T19:35:06.137Z
Peter
<p>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$.</p>

<blockquote>
  <p>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$?</p>
</blockquote>

<p>The conditions are necessary, because</p>

<p>(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$,</p>

<p>(b) if $\liminf_{|x|\rightarrow \infty} T(x)&lt;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$.</p>

<p>Also note that our job would be easy if we know that $T(x)$ is not surjective, but <a href="https://cstheory.stackexchange.com/questions/27424/is-kolmogorov-complexity-a-surjective-function">little is known</a> about this, so the answer might depend on $U$, though I doubt it would.</p>

<p>I know that relations are studied a lot in general, but </p>

<blockquote>
  <p>Has anyone ever asked a similar question where our goal is to give an algorithm that does <em>not</em> output some parameter?</p>
</blockquote>

<p>My motivation is this problem <a href="http://arxiv.org/abs/1302.1109" rel="nofollow noreferrer">http://arxiv.org/abs/1302.1109</a>.</p>

CC BY-SA 3.0
2015-04-26T19:20:38.303Z
Isn't it the case if such $T$ exists then the Halting problem would be computable?
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-04-26T20:12:03.563Z
@Mohammad: Nope.
domotorp
CC BY-SA 3.0
2015-04-26T22:26:51.667Z
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
CC BY-SA 3.0
2015-04-26T23:52:23.267Z
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
CC BY-SA 3.0
2015-04-27T04:16:49.630Z
@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
CC BY-SA 3.0
2015-04-27T06:34:56.077Z
@Joshua: Yes, diagonal arguments have been around for a long time, what I meant was that I want the diagonal function to be recursive. I've updated the second question to make it more clear.
domotorp
CC BY-SA 3.0
2015-04-27T07:00:18.510Z
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
CC BY-SA 3.0
2015-04-27T07:24:59.140Z
@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
CC BY-SA 3.0
2015-04-27T08:08:39.230Z
@Ricky: Yes, it is.
domotorp
CC BY-SA 3.0
2015-04-27T08:37:57.787Z
@Ricky: Yes, isn't this the standard way?
domotorp
CC BY-SA 3.0
2015-04-27T21:55:26.973Z
given that Kolmogorov Complexity is defined up to an additive constant (and this constant can vary with Turing machine depending on encoding primarily), i would say no.
Nikos M.
CC BY-SA 3.0
2015-04-27T22:05:56.117Z
indeed given the fact that KC can be approximated (e,g by Shannon entropy as the supremum) even by randomisation
Nikos M.
CC BY-SA 3.0
2016-01-31T19:36:32.820Z
@NikosM. For a given universal Turing machine and encoding the value is precisely defined. The constant term only comes in when you want to talk about K as a property of the string.
Peter
CC BY-SA 3.0
2016-01-31T22:52:19.923Z
@Peter, i dont think so, i would say not necesarily, for example there can be equivalent representations of same KC, but it is rather diificult to do a comprehensive analysis on a comment (maybe at some time a answer may be given)
Nikos M.
CC BY-SA 3.0
2016-01-31T23:56:22.403Z
@NikosM I may have phrased that poorly. I simply meant that the constant term only comes in when you want to talk about K's invariance to the choice of U. If you fix U, it's simply some function, and you miss the important property (invariance), but it does become precisely defined (ie. down to the bit). For this question, you can just fix U, and dat about a specific, well-defined $K^U(x)$.
Peter
CC BY-SA 3.0
2016-02-01T00:03:54.330Z
@Peter, yes but still the constant is not tied just to the model (i.e TM) but also to representation. Invariance includes the undefined constant. In fact these undefined constants in such theories have much information underneath (which acts as a "translation operator"). But again this is for another discussion
Nikos M.
CC BY-SA 3.0
2016-02-03T05:38:41.887Z
Can T(x) assumed to be injective?
ARi
CC BY-SA 3.0
2016-02-03T06:39:40.017Z
@ARi Definitely not, as like $2^n$ strings need to be mapped to $n$ values, right?
domotorp
<cc.complexity-theory><kolmogorov-complexity><universal-computation><universal-turing-machines>
Can we not output the Kolmogorov complexity?
domotorp
# Can we not output the Kolmogorov complexity?

(Asked by: username_0 on 2015-04-26)

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)

Also note that our job would be easy if we know that $T(x)$ is not surjective, but [little is known](https://cstheory.stackexchange.com/questions/27424/is-kolmogorov-complexity-a-surjective-function) 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>.

**Tags:** cc.complexity-theory, kolmogorov-complexity, universal-computation, universal-turing-machines

> **Comments:**
> **username_1**: Isn't it the case if such $T$ exists then the Halting problem would be computable?  
> **username_0**: @Mohammad: Nope.  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_0**: @username_2: I think you are wrong. According to my definition of universal Turing-machines given in the first para, all lengths can be valid programs.  
> **username_0**: @Joshua: Yes, diagonal arguments have been around for a long time, what I meant was that I want the diagonal function to be recursive. I've updated the second question to make it more clear.  
> **username_4**: 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$.  
> **username_0**: @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.  
> **username_0**: @Ricky: Yes, it is.  
> **username_0**: @Ricky: Yes, isn't this the standard way?  
> **username_5**: given that Kolmogorov Complexity is defined up to an additive constant (and this constant can vary with Turing machine depending on encoding primarily), i would say no.  
> **username_5**: indeed given the fact that KC can be approximated (e,g by Shannon entropy as the supremum) even by randomisation  
> **username_6**: @NikosM. For a given universal Turing machine and encoding the value is precisely defined. The constant term only comes in when you want to talk about K as a property of the string.  
> **username_5**: @username_6, i dont think so, i would say not necesarily, for example there can be equivalent representations of same KC, but it is rather diificult to do a comprehensive analysis on a comment (maybe at some time a answer may be given)  
> **username_6**: @NikosM I may have phrased that poorly. I simply meant that the constant term only comes in when you want to talk about K's invariance to the choice of U. If you fix U, it's simply some function, and you miss the important property (invariance), but it does become precisely defined (ie. down to the bit). For this question, you can just fix U, and dat about a specific, well-defined $K^U(x)$.  
> **username_5**: @username_6, yes but still the constant is not tied just to the model (i.e TM) but also to representation. Invariance includes the undefined constant. In fact these undefined constants in such theories have much information underneath (which acts as a "translation operator"). But again this is for another discussion  
> **username_7**: Can T(x) assumed to be injective?  
> **username_0**: @username_7 Definitely not, as like $2^n$ strings need to be mapped to $n$ values, right?  

---

## 2 answers

### Answer by username_8 on 2016-02-09. Score: 7

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 username_2 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!

> **Comments:**
> **username_0**: 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?  
> **username_9**: 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.)  
> **username_0**: 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$.  
> **username_0**: What username_2 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 username_6's incorrect answer received so many upvotes, I'm loosing faith in this site...  
> **username_0**: It doesn't matter how the TMs are encoded, as long as my criteria about the universal TM is satisfied, so username_2'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...  
> **username_9**: @username_0 As one of those who upvoted username_2’s comment, let me explain: it was easy to miss on first reading that you took precautions against such pathological TM, and since comment upvotes are frozen after a ridiculously short time (1minute?), I couldn’t retract my vote upon realizing that. I should be more careful, I know, but there you go. Combined with the fact that it’s impossible to *downvote* comments, it’s really easy for a comment incorrect in a nontrivial way to collect a number of upvotes.  
> **username_0**: @Emil Wow, that gave back my faith, thx! (Unfortunately I cannot upvote your comment, as I wanted to test the undo function and apparently you cannot reupvote - I wonder why?)  

---

### Answer by username_6 on 2016-01-31. Score: 3

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.

> **Comments:**
> **username_5**: 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  
> **username_0**: Why will you have $T(x)\le |x|$?  
> **username_6**: @username_0 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).  
> **username_0**: 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.  
> **username_6**: @domotrop I see, so you want to force $T(x)$ to not be an upperbound to $C(x)$. That is more interesting...  
> **username_8**: Also couldn't this program output 0 infinitely often?  That would violate the lim inf requirement.  
> **username_0**: @Dan: Yeah, you're right, that seems to be another issue.  

---

