On the hierarchy and extension of monotonically computable real numbers.
type: Item
instance of: scholarly article
title: On the hierarchy and extension of monotonically computable real numbers.
zbMATH Open document ID: 1043.03037
DOI: 10.1016/S0885-064X(03)00066-9
author: Robert Rettinger
author: Xizhong Zheng
published in: Journal of Complexity
publication date: 2004-03-14T00:00:00Z
review text: 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, 37…
reviewed by: Frank Stephan
Mathematics Subject Classification ID: 03D65
Mathematics Subject Classification ID: 03F60
zbMATH DE Number: 2056486
zbMATH Keywords: recursively approximable real numbers
zbMATH Keywords: monotonically computable real numbers
zbMATH Keywords: weakly computable real numbers
zbMATH Keywords: dense hierarchy
MaRDI profile type: Publication
cites work: Weakly computable real numbers
cites work: A characterization of c. e. random reals
cites work: Q3837995
cites work: Recursively enumerable reals and Chaitin \(\Omega\) numbers
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Randomness and recursive enumerability
cites work: The definition of random sequences
cites work: A computable ordinary differential equation which possesses no computable solution
cites work: Q4530157
cites work: Recursive Real Numbers
cites work: Q5805955
cites work: Cohesive sets and recursively enumerable Dedekind cuts
cites work: Recursion Theory and Dedekind Cuts
cites work: Nicht konstruktiv beweisbare Sätze der Analysis
cites work: On Computable Numbers, with an Application to the Entscheidungsproblem
cites work: Q4485693
cites work: Q4218154
cites work: The closure properties on real numbers under limits and computable operators.
description: scientific article; zbMATH DE number 2056486