RE: Asymptotic growth of a non-computable sequence

8 views
Skip to first unread message

Kreinovich, Vladik

unread,
Aug 11, 2021, 6:42:26 PM8/11/21
to José Manuel Rodríguez Caballero, ai...@googlegroups.com

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

unread,
Aug 12, 2021, 8:52:33 AM8/12/21
to ai...@googlegroups.com


----- 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.



--


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/
~
~
~
~
~
~
~
~
~
Reply all
Reply to author
Forward
0 new messages