<p>Just an extended comment with no deep insights: perhaps you can cheat on the encoding of a Turing machine, and build an <em>artificial</em> encoding that leads to a surjective Kolmogorov complexity:</p>

<ul>
<li>$0$ represents the Turing machine that outputs $0$ (1 state TM); </li>
<li>$0p$ represents the Turing machine that outputs $p+1$ (the number represented by the binary string $p$ plus one); it is simply an implicit "zipped" version of a decidable TM that outputs $p+1$;</li>
<li>$1p$ represents the $p+1$-th Turing machine in a standard enumeration (the enumeration can skip the TMs already included with $0$ and $0p$).</li>
</ul>

<p>The corresponding universal TM on input $bx$ checks what is the value of $b$, if it is $0$ then it simply outputs $x+1$, otherwise it  simulates TM $M_{x+1}$ ($M_0$ when $x$ is the empty string); note that $M_{x+1}$ embeds the inputs. </p>

<p>For all strings $x$, $1 \leq K(x) \leq |x|+1$; and for all $n \geq 1$ there are $2^{n}$ strings of length $n$ but there are only $2^{n-1}-1$ programs of length $&lt; n$ that can be represented using the $1p$ encoding; and only $2^{n}-1$ programs of length $n$ that can be represented using the $1p$ encoding; so at least a string $x'$  of length $n$ cannot be represented with a program $1p$ of length $\leq n$; but it can surely be represented with the program $0x'$ of length $n+1$ (we don't worry if there is also a program $1p$ of the same length $n+1$ that generates it).</p>

<p>We can conclude that for all $n &gt; 1$, there exists a string $x', |x'|=n$ such that $K(x') = n+1$ (so this particular K is surjective).</p>

CC BY-SA 3.0
2014-11-12T19:51:29.157Z
2014-11-12T21:33:07.520Z
2014-11-12T21:33:07.520Z
Marzio De Biasi
<p>Let us fix an encoding of Turing-machines and a universal Turing-machine, U, that on input (T,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 an N such that for all n>N there is an x with K(x)=n?</p>
</blockquote>

<p><strong>Remark.</strong> If we define universal Turing-machines in a different way, the answer can be negative. For example, consider a U that on input (T,x) simulates T on x if the length of (T,x) is divisible by 100, and otherwise does nothing.
One can modify this example in several ways to obtain counterexamples for different definitions of universal Turing-machines.</p>

CC BY-SA 3.0
2017-11-17T06:05:58.447Z
Far from what you're asking for, but I think it's not hard to prove that the image of $K$ has positive linear density regardless of $U$.   This implies for example that $K(x)$ is infinitely often composite.
Dan Brumleve
<cc.complexity-theory><universal-computation><kolmogorov-complexity><universal-turing-machines>
Is Kolmogorov complexity a surjective function?
domotorp
# Is Kolmogorov complexity a surjective function?

(Asked by: username_0 on 2014-11-12)

Let us fix an encoding of Turing-machines and a universal Turing-machine, U, that on input (T,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 an N such that for all n>N there is an x with K(x)=n?

**Remark.** If we define universal Turing-machines in a different way, the answer can be negative. For example, consider a U that on input (T,x) simulates T on x if the length of (T,x) is divisible by 100, and otherwise does nothing.
One can modify this example in several ways to obtain counterexamples for different definitions of universal Turing-machines.

**Tags:** cc.complexity-theory, universal-computation, kolmogorov-complexity, universal-turing-machines
> **Comments:**
> **username_1**: Far from what you're asking for, but I think it's not hard to prove that the image of $K$ has positive linear density regardless of $U$.   This implies for example that $K(x)$ is infinitely often composite.  

---

## 1 answers

### Answer by username_2 on 2014-11-12. Score: 3

Just an extended comment with no deep insights: perhaps you can cheat on the encoding of a Turing machine, and build an *artificial* encoding that leads to a surjective Kolmogorov complexity:

* $0$ represents the Turing machine that outputs $0$ (1 state TM);
* $0p$ represents the Turing machine that outputs $p+1$ (the number represented by the binary string $p$ plus one); it is simply an implicit "zipped" version of a decidable TM that outputs $p+1$;
* $1p$ represents the $p+1$-th Turing machine in a standard enumeration (the enumeration can skip the TMs already included with $0$ and $0p$).

The corresponding universal TM on input $bx$ checks what is the value of $b$, if it is $0$ then it simply outputs $x+1$, otherwise it simulates TM $M\_{x+1}$ ($M\_0$ when $x$ is the empty string); note that $M\_{x+1}$ embeds the inputs.

For all strings $x$, $1 \leq K(x) \leq |x|+1$; and for all $n \geq 1$ there are $2^{n}$ strings of length $n$ but there are only $2^{n-1}-1$ programs of length $< n$ that can be represented using the $1p$ encoding; and only $2^{n}-1$ programs of length $n$ that can be represented using the $1p$ encoding; so at least a string $x'$ of length $n$ cannot be represented with a program $1p$ of length $\leq n$; but it can surely be represented with the program $0x'$ of length $n+1$ (we don't worry if there is also a program $1p$ of the same length $n+1$ that generates it).

We can conclude that for all $n > 1$, there exists a string $x', |x'|=n$ such that $K(x') = n+1$ (so this particular K is surjective).


---

