Asymptotic growth of a non-computable sequence

José Manuel Rodríguez Caballero josephcmac at gmail.com
Wed Aug 11 18:29:01 EDT 2021


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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20210811/8abb40ac/attachment.html>


More information about the FOM mailing list