zbMATH — the first resource for mathematics

Comparing c.e. sets based on their settling times. (English) Zbl 1151.03332
Cooper, S. Barry (ed.) et al., Computation and logic in the real world. Third conference on computability in Europe, CiE 2007, Siena, Italy, June 18–23, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73000-2/pbk). Lecture Notes in Computer Science 4497, 196-204 (2007).
Summary: To each computably enumerable (c.e.) set \(A\) with a particular enumeration \(\{A _{s }\}_{s \in \omega}\), there is associated a settling function \(m _{A }(x)\), where \(m _{A }(x)\) is the last stage when a number less than or equal to \(x\) was enumerated into \(A\). In [Z. Math. Logik Grundlagen Math. 14, 339–356 (1968; Zbl 0217.01202)], R. W. Robinson classified the complexity of c.e. sets into two groups of complexity based on whether or not the settling function was dominant. An extension of this idea to a more refined ordering of c.e. sets was first introduced by A. Nabutovsky and S. Weinberger in [Geom. Dedicata 101, 1–54 (2003; Zbl 1039.58009)] and R. I. Soare [Bull. Symb. Log. 10, No. 4, 457–486 (2004; Zbl 1085.03033)], for application to differential geometry. There they defined one c.e. set \(A\) to settling time dominate another c.e. set \(B\) \((B >_{\text{st}} A)\) if for every computable function \(f\), for all but finitely many \(x, m _{B }(x) > f(m _{A }(x))\). In [J. Symb. Log. 71, No. 4, 1394–1410 (2006; Zbl 1109.03035)] B. F. Csima and R. I. Soare introduced a stronger ordering, where \(B > _{\text{sst}} A\) if for all computable \(f\) and \(g\), for almost all \(x, m _{B }(x) > f(m _{A }(g(x)))\). We give a survey of the known results about these orderings, make some observations, and outline the open questions.
For the entire collection see [Zbl 1119.68004].
03D25 Recursively (computably) enumerable sets and degrees
Full Text: DOI