On the hierarchy and extension of monotonically computable real numbers. (Q1426053): Difference between revisions

The authors consider the classes WC, \(c\)-MC, \(\omega\)-MC, WBC and RA of real numbers. These classes contain all real numbers \(x\) satisfying the corresponding condition. WC: \(x\) is in WC if \(x\) has a recursive approximation \(q_0,q_1,...\) of rational numbers such that the sum \(| q_0-q_1| +| q_1-q_2| +| q_2-q_3| +...\) converges; \(c\)-MC: \(x\) is in \(c\)-MC if \(x\) has a recursive approximation \(q_0,q_1,...\) of rationals such that \(| q_m-x| \leq c*| q_n-x| \) for all \(n\) and all \(m > n\) where \(c\) is a real number with \(c \geq 1\); \(\omega\)-MC: \(x\) is in \(\omega\)-MC if \(x\) has a recursive approximation \(q_0,q_1,...\) of rationals such that there is a recursive function \(h\) mapping \(\{0,1,2,...\}\) to \(\{1,2,...\}\) such that \(| q_m-x| \leq h(n)*| q_n-x| \) for all \(n\) and all \(m > n\); WBC: \(x\) is in WBC if \(x\) has a recursive approximation \(q_0,q_1,...\) of rationals such that there is a recursive function \(h\) such that \(m \leq h(n)\) whenever there is a monotone increasing sequences \(i_0,i_1,...,i_{2m+1}\) of indices with \(| q_{i_{2k}}-q_{i_{2k+1}}| \geq 2^{-n}\) for \(k=0,1,...,m\); RA: \(x\) is in RA if \(x\) has a recursive approximation, that is, \(x\) can be computed relative to the halting problem \(K\). The authors give a survey of the known relations between these classes and then show the following new results: \(c_1\)-MC is a proper subclass of \(c_2\)-MC whenever \(1 \leq c_1 < c_2\); \(\omega\)-MC is incomparable to WC; \(c\)-MC is a proper subclass of WC for any constant \(c\); \(\omega\)-MC is incomparable to WBC. The authors state as an open problem whether there is a hierarchy inside \(\omega\)-MC depending on the choice of the function \(h\). The authors have already solved this problem [\textit{X. Zheng} and \textit{R. Rettinger}, ``h-monotonically computable real numbers'', in: International Conference on Computability and Complexity in Analysis, CCA 2003, August 28--30, 2003, Cincinnati, USA, 375--388 (2003)]. In particular, if \(h\) is increasing and not bounded by a constant, then it generates the whole class \(\omega\)-MC: Let \(x\) be in \(\omega\)-MC witnessed by the recursive approximation \(q_0,q_1,...\) and the function \(h'\) and assume that \(h\) is a recursive, increasing and unbounded function with \(h(0) \geq h'(0)\). Then one can take \(r_{n}\) to be \(q_{n'}\) for the maximal \(n' \leq n\) such that \(h'(n') \leq h(n)\). The resulting approximation \(r_0,r_1,...\) witnesses that \(x\) is in \(\omega\)-MC via the function \(h\).