9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dan Brumleve Nov 17 '17 at 6:05
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.