Weakly computable real numbers

被引:53
作者
Ambos-Spies, K
Weihrauch, K
Zheng, XZ [1 ]
机构
[1] BTU Cottbus, Fak 1, D-03013 Cottbus, Germany
[2] Fern Univ Hagen, D-58084 Hagen, Germany
[3] Univ Heidelberg, Inst Math, D-69120 Heidelberg, Germany
关键词
D O I
10.1006/jcom.2000.0561
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
A real number x is recursively approximable if it is a limit of a computable sequence of rational numbers. If, moreover. the sequence is increasing (decreasing or simply monotonic), then x is called left computable (right computable or semi computable). x is called weakly computable if it is a difference of two left computable real numbers. We show that a real number is weakly computable if and only if there isa computable sequence (x(s))(s is an element ofN) of rational numbers which converges to x weakly effectively, namely the sum of jumps of the sequence is bounded. It is also shown that the class of weakly computable real numbers extends properly the class of semi-computable real numbers and the class of recursively approximable real numbers extends properly the class of weakly computable real numbers. (C) 2000 Academic Press.
引用
收藏
页码:676 / 690
页数:15
相关论文
共 50 条
[21]   A hierarchy of Turing degrees of divergence bounded computable real numbers [J].
Rettinger, Robert ;
Zheng, Xizhong .
JOURNAL OF COMPLEXITY, 2006, 22 (06) :818-826
[22]   The closure properties on real numbers under limits and computable operators [J].
Zheng, XZ .
THEORETICAL COMPUTER SCIENCE, 2002, 284 (02) :499-518
[23]   Reordered Computable Numbers [J].
Janicki, Philip .
THEORY OF COMPUTING SYSTEMS, 2024, 68 (06) :1683-1708
[24]   Degrees of weakly computable reals [J].
Ng, Keng Meng ;
Stephan, Frank ;
Wu, Guohua .
LOGICAL APPROACHES TO COMPUTATIONAL BARRIERS, PROCEEDINGS, 2006, 3988 :413-422
[25]   Genericity of Weakly Computable Objects [J].
Hoyrup, Mathieu .
THEORY OF COMPUTING SYSTEMS, 2017, 60 (03) :396-420
[26]   Genericity of Weakly Computable Objects [J].
Mathieu Hoyrup .
Theory of Computing Systems, 2017, 60 :396-420
[27]   The elementary computable functions over the real numbers: applying two new techniques [J].
Manuel L. Campagnolo ;
Kerry Ojakian .
Archive for Mathematical Logic, 2008, 46 :593-627
[28]   The elementary computable functions over the real numbers: applying two new techniques [J].
Campagnolo, Manuel L. ;
Ojakian, Kerry .
ARCHIVE FOR MATHEMATICAL LOGIC, 2008, 46 (7-8) :593-627
[29]   On computable numbers, with an application to the Entscheidungsproblem [J].
Turing, AM .
PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, 1937, 42 :230-265
[30]   On computable automorphisms of the rational numbers [J].
Morozov, AS ;
Truss, JK .
JOURNAL OF SYMBOLIC LOGIC, 2001, 66 (03) :1458-1470