Asymptotic growth of a non-computable sequence
Kreinovich, Vladik
vladik at utep.edu
Wed Aug 11 15:09:01 EDT 2021
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
Maybe you meant something else?
From: FOM [mailto:fom-bounces at cs.nyu.edu] On Behalf Of José Manuel Rodríguez Caballero
Sent: Tuesday, August 10, 2021 11:01 PM
To: Foundations of Mathematics <fom at cs.nyu.edu>
Subject: Asymptotic growth of a non-computable sequence
Dear FOM members,
In a recent preprint [1] comparing 't Hooft's and Wolfram's deterministic models of quantum mechanics, I considered the following sequence: a(n) is the smallest number having n binary digits, which can't be compressed concerning a fixed Turing machine. I would appreciate some references to tools to estimate the asymptotic growth of this sequence.
Kind regards,
José M.
References:
[1] arXiv:2108.03751 [quant-ph]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20210811/b2e0a7d5/attachment-0001.html>
More information about the FOM
mailing list