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
相关论文
共 18 条
[1]  
CALUDE C, STACS 98, P596
[2]  
Carstens H. G., 1976, Arch. Math. Log, V18, P55
[3]  
CEITIN GS, 1971, ZAP NAUCN SEM LENING, V20, P263
[4]  
COOPER SB, 1971, THESIS LEICESTER U L
[5]  
ERSHOV YL, 1968, ALGEBRA LOGIKA+, V7
[6]  
ERSHOV YL, 1970, ALGEBRA LOGICA, V9, P34
[7]  
ERSHOV YL, 1968, ALGEBRA LOGIKA+, V7
[8]  
FRIEDBERG R. M., 1958, J SYMBOLIC LOGIC, V23, P309
[9]   SEMIRECURSIVE SETS AND POSITIVE REDUCIBILITY [J].
JOCKUSCH, CG .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1968, 131 (02) :420-&
[10]   ON THE DEFINITIONS OF SOME COMPLEXITY CLASSES OF REAL NUMBERS [J].
KO, KI .
MATHEMATICAL SYSTEMS THEORY, 1983, 16 (02) :95-109