5
$\begingroup$

A simple counting argument shows most strings can't be compressed to shorter strings. But, compression is usually defined using Kolmogorov complexity. A string is compressible if its Kolmogorov complexity is less than its length, $K(s) < |s|$. The Kolmogorov complexity of a string is defined as the size of the smallest Turing machine (TM) that writes the string and halts when given a blank tape. I want to define the size of a TM as the number of states the machine has. I want to use a simple type of TM known as a Busy Beaver. BB's use two symbols, 0 and 1. A BB blank tape is initialized to all 0's and is unbounded in both directions.

Let the Kolmogorov complexity of natural number $n$, $K(n)$, be the number of states in the smallest BB that writes $n$ 1's and halts when given a blank tape. I use this definition so I can use known results about busy beavers, particularly Rado's sigma function, $\sum(n)$. $\sum(n)$ is defined as the maximum number of 1's an n-state BB can write and halt when given a blank tape. It is known $\sum(n)$ grows faster than any recursive function. This shows there is no recursive limit on how much a natural number can be compressed.

$\sum(2)=4$ so $K(4)=2$. This means 4 is a compressible number. This is the definition of the BB:

A0: 1RB / B0: 1LA

A1: 1LB / B1: 1RHalt

"A0: 1RB" means in state A on input 0 write 1, move one position right, and switch to state B. We can "extend" this machine to create new machines that compress natural numbers. To extend this machine replace the halt state with a new state. On input 0 this state writes 1 and halts. On input 1 it writes 1, moves one position right, and stays in the same state.

A0: 1RB / B0: 1LA / C0: 1RHalt

A1: 1LB / B1: 1RC / C1: 1RC

This 3 state machine writes 5 1's and halts. This proves $K(5) \leq 3$ and 5 is a compressible number. In fact, all numbers greater than 3 are compressible by at least 2 because we can write the first 4 1's using only 2 states. $\forall n(n>3 \rightarrow K(n) \leq n-2)$

We know natural number $n$ can be represented as a binary number with $log_2(n)+1$ bits. Let a number be super compressible if $K(n) < log_2(n)+1$. We see 4 is super compressible because $K(4)=2 < log_2(4)+1 = 3$. It is known $\sum(5) \ge 4098$. This means $K(4098) = 5$ and 4098 is super compressible. By extending this 5-state machine we can show 4099 through 4107 are also super compressible. In general, the range $\sum(n)$ through $\sum(n)+log_2(\sum(n))-n$ will be super compressible. For example, it is known $\sum(6) \ge 3.515 * 10^{18267}$. This proves the range $3.515 * 10^{18267}$ through $3.515 * 10^{18267} + log_2(10^{18267})$ is super compressible.

Are all large enough natural numbers super compressible? If not, why not?

Note there are lots of machines besides the ones defined by $\sum(n)$. There are probably lots of halting 5-state machines that write more that $2^5$ 1's and less than 4098 1's. All such machines define ranges of super compressible numbers. I previously asked a similar question without getting an adequate answer.

$\endgroup$
  • 8
    $\begingroup$ Don't we normally define Kolmogorov complexity of a string as the number of bits encoding the smallest Turing machine that outputs the string? You might as well say all binary strings can be compressed by rewriting them in ternary. $\endgroup$ – user253751 Sep 20 '15 at 9:12
  • $\begingroup$ the rough intuition of Kolmogorov complexity is that most strings chosen at random are not significantly compressible. this is (intuitively) because a random string is like/ indistinguishable from "noise". in other words there is no "magic" about compression and on average versus large random strings it typically "loses" ie cannot lead to savings. $\endgroup$ – vzn Sep 20 '15 at 14:46
  • $\begingroup$ @vzn Agreed. But defining a Kolmogorov-like complexity as here, in terms of the number of states the defining Turing machine has, rather than the size of its description, gives a very different result, as Yuval's answer shows. $\endgroup$ – David Richerby Sep 20 '15 at 15:05
  • 2
    $\begingroup$ I think you would get a better reception if you presented yourself better; e.g. you're not doing yourself any favors by calling your complexity measure "Kolmogorov complexity", and it's misleading to talk about "compressibility" without emphasizing up front that you're not talking about what is usually meant by the phrase. $\endgroup$ – user5386 Sep 20 '15 at 16:15
  • 1
    $\begingroup$ @david ok this seems to be significantly different than std kolmogorov complexity defn(s) & think maybe its not helpful and/or confusing to redefine it in this way (because it almost conflicts with std defns in the well/ long established theory) & that the question should better distinguish this somewhat unusual different angle. $\endgroup$ – vzn Sep 20 '15 at 23:32
3
$\begingroup$

I'm not entirely sure what you're scheme is. However, given the information in your question, I should be able to simply answer the question in your title.

It seems that in your scheme the asymptotic growth of the range of numbers that are "super compressible" is:

$$[10^n, 10^n+log(10^n)] = [10^n, 10^n+n]$$

However, $\lim_{n\to\infty} {n \over 10^n} = 0$, so I'm afraid that when the numbers get big nearly no numbers are super compressible. Additionally, since $\lim_{n\to\infty} {cn \over 10^n} = 0$ for any constant $c$, this result is irrespective of how many sequences of precomputed 'super compressible' numbers you find.


It's hard (at least for me, give a call to our friend Shannon) to show this rigorously, but even if you add more and more sequences of 'super compressible' numbers, you will never be able to represent more than double the range using one extra bit of information.

$\endgroup$
  • $\begingroup$ I have a gut feeling that the claim that nearly all natural numbers are super-compressible would violate the Kraft-McMillan theorem. That might be one way to make a rigorous proof. $\endgroup$ – Pseudonym Sep 20 '15 at 2:47
  • $\begingroup$ This what I was looking for. I don't see how you prove $c$ is a constant. The number of compressible numbers could grow extremely fast. I think we can show if there is a range $[x,2x]$ of super compressible numbers then all numbers greater than $x$ are super compressible. $\endgroup$ – Russell Easterly Sep 21 '15 at 4:44
5
$\begingroup$

For every $n$ there is a "busy beaver" machine (i.e., a Turing machine on the tape alphabet $\{0,1\}$ run on the empty tape) which outputs $1^n$ using $O(\log n/\log\log n)$ states, which is asymptotically optimal (up to constants).

Here is how this machine works. For every $C$, we will construct such a machine having $O(\log n/C) + O(C2^C)$ states. The machine will first write the binary representation of $n$, and then use $O(1)$ states to convert it to its unary representation (that is, $1^n$); we will only describe the first phase.

The machine runs in $\log n/C$ rounds, maintaining a unary counter whose value at round $r$ is $1^r$ (after all the rounds finish, we erase the counter). At each round, we write $C$ bits of the binary representation of $n$. This is accomplished using $O(C2^C)$ states which implement adding $C$ bits (for which choice of $C$ bits), and $O(\log n/C)$ states for control (we use the unary counter to switch control to the correct state). This completes the description of the machine.

A machine with $S$ states on the binary tape alphabet has description size $O(S\log S)$. Hence we expect that the optimal answer be $O(\log n/\log\log n)$. Indeed, if we choose $C$ very carefully to be $\log (\log n/(\log\log n)^2)$, then the construction above gives a "busy beaver" machine with $O(\log n/\log\log n)$ states, which is optimal up to constants.

If the tape alphabet is allowed to grow with $n$, then $O(1)$ states suffice to output $1^n$: the alphabet will be of size $n + O(1)$, and we will use a certain cell as a counter. This construction shows that it is important to limit the tape alphabet.

$\endgroup$
  • $\begingroup$ ofc think this is all great/ informative but needs to be tied into the question in a more specific way eg summary etc., also it doesnt mention kolmogorov complexity etc $\endgroup$ – vzn Sep 20 '15 at 23:29
  • 1
    $\begingroup$ @vzn It completely answers the question, and uses Kolmogorov complexity, in the guise of description size, for the lower bound. What more can you wish for? $\endgroup$ – Yuval Filmus Sep 21 '15 at 4:26

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.