Is Kolmogorov complexity a surjective function?

Question

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.

Answer 1

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).