<p>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 &lt; 2^k$ has a $k$-bit binary representation. It is only in the unary representation that every natural number $n$ has complexity approximately $n$.</p>

<p>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.</p>

CC BY-SA 3.0
2015-08-19T02:51:21.917Z
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.
Russell Easterly
CC BY-SA 3.0
2015-08-19T03:28:28.533Z
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?
Joe Bebel
CC BY-SA 3.0
2015-08-20T03:27:33.420Z
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.
Russell Easterly
CC BY-SA 3.0
2015-08-20T05:24:38.697Z
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.
Joe Bebel
CC BY-SA 3.0
2015-08-18T08:00:44.323Z
2015-08-18T08:00:44.323Z
Joe Bebel
<p>There are numerous proofs that <a href="https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compression" rel="nofollow">most strings are incompressible</a>. I am interested in strings that represent natural numbers. Assume the Kolmogorov complexity of a natural number, $K(n)$, is the smallest <a href="https://en.wikipedia.org/wiki/Busy_beaver#.CE.A3.2C_complexity_and_unprovability" rel="nofollow">busy beaver</a>(BB) that writes $n$ 1's and halts. It seems easy to prove nearly all natural numbers are compressible using this definition.</p>

<p>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.</p>

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

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

<hr>

<p>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 <a href="http://www.drivenbycode.com/turing-machines-and-the-busy-beaver-game/" rel="nofollow">busy beaver</a>(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&gt;5$ are compressible.</p>

<p>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)&lt;n$ for all $n&gt;5$ with this definition.</p>

<p>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) &lt; log_2(n)$ for nearly all large enough $n$? (Assuming we represent $n$ by its binary expansion.) </p>

<p>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.     </p>

CC BY-SA 3.0
2015-08-17T17:48:57.747Z
What is your representation of natural numbers ?
Joshua Herman
CC BY-SA 3.0
2015-08-18T07:15:21.587Z
Unless your model of computation violates the Church-Turing thesis, nearly all natural numbers are incompressible.
András Salamon
<kolmogorov-complexity>
Are nearly all natural numbers compressible?
Russell Easterly
# Are nearly all natural numbers compressible?

(Asked by: username_0 on 2015-08-17)

There are numerous proofs that [most strings are incompressible](https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compression). I am interested in strings that represent natural numbers. Assume the Kolmogorov complexity of a natural number, $K(n)$, is the smallest [busy beaver](https://en.wikipedia.org/wiki/Busy_beaver#.CE.A3.2C_complexity_and_unprovability)(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](http://www.drivenbycode.com/turing-machines-and-the-busy-beaver-game/)(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)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.

**Tags:** kolmogorov-complexity
> **Comments:**
> **username_1**: What is your representation of natural numbers ?  
> **username_2**: Unless your model of computation violates the Church-Turing thesis, nearly all natural numbers are incompressible.  

---

## 1 answers

### Answer by username_3 on 2015-08-18. Score: 3

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: 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?  
> **username_0**: 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.  
> **username_3**: 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.  

---

