2023/03/21 by Hölzl, Rupert, Janicki, Philip
#03D32 #03D78 #03F60 #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.2303.11986
A left-computable number x is called regainingly approximable if there is a computable increasing sequence (xn)n of rational numbers converging to x such that x - xn < 2-n for infinitely many n ∈ ℕ; and it is called nearly computable if there is such an (xn)n such that for every computable increasing function s \colon ℕ → ℕ the sequence (xs(n+1) - xs(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öf 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.