Asymptotic growth of a non-computable sequence

[José Manuel Rodríguez Caballero]

Hi Freek,


> I don't really understand the question ("fixed Turing
> machine", won't this number depend on the Turing machine,
> and maybe for every n another Turing machine is better?),


Yes, but it would be nice to know some results which are valid for all
Turing machines; for example, the result below:

If a(n) has this property, then the same number
> with zero and one flipped should have the same property?


I think that you meant:

Theorem: Consider a fixed Turing machine. Let a(n, epsilon) be the smallest
number, having exactly n binary digits that cannot be compressed to less
than (1 - epsilon)*n bits (with respect to the fixed Turing machine). For
any epsilon > 0 and for all n large enough, a(n, epsilon) < 2^(n+1) -
2^(n-1).

Proof.
  We proceed by reductio ad absurdum, Assume that there is a strictly
increasing sequence of natural numbers x_n for which

a(x_n, epsilon) >= 2^(x_n + 1) - 2^(x_n - 1) for all n.

Let b(n, epsilon) be equal to a(x_n, epsilon) with all its binary digits
flipped, except the first one. By construction, b(n, epsilon) has exactly
x_n binary digits, and it satisfies the inequality

 b(n, epsilon) < 2^(x_n + 1) - 2^(x_n - 1).

Notice that the minimum number of bits needed to define b(n, epsilon) is
the minimum number of bits required to express a(x_n, epsilon) minus a
constant depending on the encoding. As n goes to infinity, this ratio goes
to 1. Therefore, for all n large enough, b(n, epsilon) cannot be compressed
to less than (1 - epsilon)*n bits. This contradicts the extremal property
in the definition of a(x_n, epsilon). Therefore, the sequence x_n cannot
exist.
QED

Corollary: 1 <= a(n, epslion)/2^n <= 1.5 for all n large enough. (that is
an improvement with respect to the trivial bound)

Nevertheless, this generic proof does not hold for the original case, when
epsilon is zero.

Kind regards,
José M.




On Thu, 12 Aug 2021 at 05:43, Freek Wiedijk <freek at cs.ru.nl> wrote:

> Hi José,
>
> >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.
>
> I don't really understand the question ("fixed Turing
> machine", won't this number depend on the Turing machine,
> and maybe for every n another Turing machine is better?),
> but: If a(n) has this property, then the same number
> with zero and one flipped should have the same property?
> That suggests that it needs to be at most one half?
>
> Freek
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20210812/51047b32/attachment.html>