-3
$\begingroup$

There are numerous proofs that most strings are incompressible. I am interested in strings that represent natural numbers. Assume the Kolmogorov complexity of a natural number, $K(n)$, is the smallest busy beaver(BB) that writes $n$ 1's and halts. It seems easy to prove nearly all natural numbers are compressible using this definition.

Consider the function $\sum(n)$ which is the maximum number of 1's that can be written by a halting BB with $n$ states. It is simple to show there exists a BB with $n$ states that writes $n$ 1's and halts. This means $K(n) \leq n$. It is known $\sum(3) = 6$ so $K(6) = 3$. This allows us to prove $K(7) \leq 4$. We start with the 3 state BB that writes 6 1's and replace the halt state with a 4th state. On input 0 this state writes a 1 and halts. On input 1 this state writes 1 then moves right and stays in state 4. This new 4 state machine will write 7 1's and halt. We can add this new state as often as we want to write larger numbers.

For example, it is known $\sum(5) \geq 4098$. This means $(n>4098) \rightarrow (K(n) \leq n-4093)$. It seems the larger a number is the more it can be compressed.

Does the Kolmogorov complexity of strings representing natural numbers become more compressible as the numbers get larger?


Apparently, I didn't present my question very well. Let $s$ be a bit string that represents a natural number. I want to know if the Kolmogorov complexity, $K(s)$, is less than $|s|$ for most strings larger than a certain size. Above, I defined $K(n)$ as the number of states of the smallest busy beaver(BB) that writes $n$ 1's and halts. This means any string with $n$ 1's can represent $n$. I used this definition so I could show how Rado's sigma function, $\sum(x)$, guarantees all representations for $n>5$ are compressible.

A more standard definition of $K(n)$ would be the number of states in the smallest TM/BB that writes $n$ consecutive 1's and halts. Since the BB for $\sum(3)$ writes six consecutive 1's, we can still prove $K(n)<n$ for all $n>5$ with this definition.

We can define the representation of a number as the binary expansion of that number. This means we are assuming the representation can always be compressed such that $K(n) \leq log_2(n)+1$. I want to know if we can do better. Is it true $K(n) < log_2(n)$ for nearly all large enough $n$? (Assuming we represent $n$ by its binary expansion.)

The idea would be to create a set of compressible strings such that any large enough bit string would contain one or more of these compressible sub-strings. For example, since '111111' is a compressible string any representation containing '111111' as a sub-string is also compressible.

$\endgroup$
2
  • $\begingroup$ What is your representation of natural numbers ? $\endgroup$ Aug 17 '15 at 17:48
  • 1
    $\begingroup$ Unless your model of computation violates the Church-Turing thesis, nearly all natural numbers are incompressible. $\endgroup$ Aug 18 '15 at 7:15
3
$\begingroup$

I think there is confusion here based on binary vs unary representation. The statement 'most strings are incompressible' means that the Kolmogorov complexity $K(n)$ is approximately $|n|$ (that is, approximately $\log_2 n$) for most $n$. Of course, every natural number $n < 2^k$ has a $k$-bit binary representation. It is only in the unary representation that every natural number $n$ has complexity approximately $n$.

Now, you may find alternative representations, possibly exotic ones, such as your busy beaver example, which achieves the same bound as the binary representation (i.e., every number $n$ has a representation of size approximately $\log_2 n$) but these do not 'compress' numbers more than the binary representation does.

$\endgroup$
4
  • $\begingroup$ How do you define $K(n)$? I am using the number of states required for a TM to print a string representing $n$. Using this measure I think we can show a large enough string with $k$ bits can be printed by a TM with fewer than $k$ states. $\endgroup$ Aug 19 '15 at 2:51
  • 1
    $\begingroup$ I mean the standard Kolmogorov complexity, the length of the shortest program that outputs $n$. But I think your measure is not so different, especially if you are outputting unary numbers. How do you output a $k$ bit string with less than $k$ states? $\endgroup$
    – Joe Bebel
    Aug 19 '15 at 3:28
  • $\begingroup$ We start with a short program that writes a long string and we extend the program. There is a 3 state busy beaver that writes '111111'. We can add states to this machine such that each additional state writes an additional '1' (see above). This allows us to print $x>5$ 1's using $x-(6-3)$ states. There is a 4 state BB that writes 13 consecutive 1's. For $x>12$ we can write $x$ 1's with $x-(13-4)$ states. $\endgroup$ Aug 20 '15 at 3:27
  • 1
    $\begingroup$ Yes, but one can write $x$ using $\log_2 x$ bits. So writing $x$ out with less than $x$ states is not particularly interesting, as a turing machine can print $x$ using a constant number of states (a fixed program) plus $\log_2 x$ additional states to encode $x$. I also highly doubt that you can do better. $\endgroup$
    – Joe Bebel
    Aug 20 '15 at 5:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.