Asymptotic growth of a non-computable sequence

[Dennis E. Hamilton]

Cabellero wrote:

> Kreinovich, Vladik wrote:

 > > Since a(n) has n binary digits, it is between 2^n and 2^{n+1} = 2*2^n, so 
this is a clear asymptotic

> where a(n) = the smallest number having n binary digits, which can't be 
> compressed concerning a fixed Turing machine

 > I suspect that a(n)/2^n converges to 1 as n goes to infinity.

[orcmid responds]

The TL:DR: There is something more meant about the fixed Turing machine and 
what it means to have uncompressible cases.  That needs to be expressed.

A thought experiment,

Not to be overly fussy, we can presume that the leading bit is always 1 (to 
avoid trivial compressibility) and in that case, the range of candidate binary 
numbers is from 2^(n-1) to 2^n-1 and there are 2^(n-1) of them.  Cabellero's 
suspicion can then be stated  that as n approaches infinity, a(n)/2^(n-1) 
approaches 1.  In effect, the proportion compressible by any fixed TM 
approaches 0.

We are left to deal with what it means to be uncompressible.  Maybe 
information theory shows us enough about that without consideration of Turing 
machines at all.

Presume, first, that lossless compression is intended: From the number 
representing a compressed value, we can recover the original.

I contrived an easy way to do that by assuming the a(n) candidates to all have 
the first of the n bits being 1.  Suppose then that the number corresponding 
to a compressed value first bit of 0 and fewer than n of them. If we allow 
exactly n all we have to do is flip the leading bit to 0 or even flip all the 
bits.  We know how to decompress all of those with a trivial algorithm.  But 
there's no compression and we have one wasted bit, the leading 1/0.

If there must be fewer than n bits in the compression, there are at most n-1 
of them, including the leading 0 bit, and that means there are fewer than 
2^(n-2) of them.  So, without trying, we know as many as half of the originals 
cannot be compressed by any method that is lossless and for which the 
compression is shorter than the original.   There's probably a tighter proof 
by induction.  We don't need that to see the bind.

We are now up against a well-known characteristic of compression algorithms. 
The more successful the compression is for many cases, there must also be 
cases where the compression result is worse -- has more bits than the 
original.  In practical schemes, the cost of expanded cases is minimized (like 
that fixed initial 1 bit taken to mean not compressed).  And in practical 
schemes, there is something that is known about the nature of the strings of 
bits that has the algorithm provide successful compressions in practice, with 
pessimistic cases producing tolerably-larger results.

I suspect that the fixed Turing machine case is around a different question, 
albeit constrained in at least the manner I have sketched.

 - Dennis