28
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Denis Apr 26 '15 at 22:26
  • 2
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Apr 26 '15 at 23:52
  • 1
    $\begingroup$ @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. $\endgroup$ – domotorp Apr 27 '15 at 4:16
  • 3
    $\begingroup$ 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$. $\endgroup$ – Marzio De Biasi Apr 27 '15 at 7:00
  • 1
    $\begingroup$ @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. $\endgroup$ – domotorp Apr 27 '15 at 7:24
7
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – domotorp Feb 9 '16 at 18:04
  • 1
    $\begingroup$ 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.) $\endgroup$ – Emil Jeřábek supports Monica Feb 9 '16 at 18:16
  • 1
    $\begingroup$ 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$. $\endgroup$ – domotorp Feb 9 '16 at 20:52
  • $\begingroup$ 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... $\endgroup$ – domotorp Feb 10 '16 at 8:47
  • $\begingroup$ 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... $\endgroup$ – domotorp Feb 10 '16 at 14:11
3
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Nikos M. Jan 31 '16 at 22:54
  • $\begingroup$ Why will you have $T(x)\le |x|$? $\endgroup$ – domotorp Feb 1 '16 at 9:31
  • $\begingroup$ @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). $\endgroup$ – Peter Feb 1 '16 at 12:45
  • $\begingroup$ 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. $\endgroup$ – domotorp Feb 1 '16 at 14:20
  • $\begingroup$ @domotrop I see, so you want to force $T(x)$ to not be an upperbound to $C(x)$. That is more interesting... $\endgroup$ – Peter Feb 1 '16 at 14:45

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.