RE: Asymptotic growth of a non-computable sequence

[Kreinovich, Vladik]

Thanks for the clarification, this makes sense, I am forwarding this to Kolmogorov complexity mailing list, since the shortest length into which we can compress is exactly Kolmogorov complexity

 

From: José Manuel Rodríguez Caballero [mailto:josep...@gmail.com]
Sent: Wednesday, August 11, 2021 4:29 PM
To: Kreinovich, Vladik <vla...@utep.edu>
Cc: Foundations of Mathematics <f...@cs.nyu.edu>
Subject: Re: Asymptotic growth of a non-computable sequence

 

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.

 

[Paul Vitanyi]

----- Forwarded Message -----
From: Paul Vitanyi <pa...@cwi.nl>
To: Kreinovich, Vladik <vla...@utep.edu>
Sent: Thu, 12 Aug 2021 14:50:36 +0200 (CEST)
Subject: Re: [AIT] RE: Asymptotic growth of a non-computable sequence

Vladik,  not so. The Kolmogorov complexity of astring x is the smallest string x* from which x can be reproduced by a universal Turing machine. This turns out

to be a lower bound on the shortest length into which we can compress x.

Paul Vitanyi

>
> More information: http://www.hutter1.net/ait.htm

> ---

> You received this message because you are subscribed to the Google Groups "Algorithmic Information Theory" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to ait0+uns...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/ait0/53eac56f86d44c5aa04ea342d403962e%40ITDSRVMBX011.utep.edu.

--

Paul Vitanyi, CWI, Science Park 123, 1098 XG Amsterdam, The Netherlands,
Tel. (+)31 20 5924124; Fax (+)31 20 5924199; pa...@cwi.nl;
http://www.cwi.nl/~paulv/
~
~
~
~
~
~
~
~
~

--

Paul Vitanyi, CWI, Science Park 123, 1098 XG Amsterdam, The Netherlands,
Tel. (+)31 20 5924124; Fax (+)31 20 5924199; pa...@cwi.nl;
http://www.cwi.nl/~paulv/
~
~
~
~
~
~
~
~
~