Benign approximations and non-speedability

MaRDI QIDQ6509267arXivFDO

Authors Rupert Hölzl

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Computation over the reals, computable analysis (03D78) Constructive and recursive analysis (03F60)

Abstract: A left-computable number $x$ is called regainingly approximable if there is a computable increasing sequence $(x_n{)}_n$ of rational numbers converging to $x$ such that $x-x_n<2^{-n}$ for infinitely many $ninmathbbN$; and it is called nearly computable if there is such an $(x_n{)}_n$ such that for every computable increasing function $scolonmathbbNomathbbN$ the sequence $(x_{s(n+1)}-x_{s(n)}{)}_n$ converges computably to 0. In this article we study the relationship between both concepts by constructing on the one hand a non-computable number that is both regainingly approximable and nearly computable, and on the other hand a left-computable number that is nearly computable but not regainingly approximable; it then easily follows that the two notions are incomparable with non-trivial intersection. With this relationship clarified, we then hold the keys to answering an open question of Merkle and Titov: they studied speedable numbers, that is, left-computable numbers whose approximations can be sped up in a certain sense, and asked whether, among the left-computable numbers, being Martin-L"of random is equivalent to being non-speedable. As we show that the concepts of speedable and regainingly approximable numbers are equivalent within the nearly computable numbers, our second construction provides a negative answer.

This page was built for publication: Benign approximations and non-speedability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6509267)