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 条
[31]   THE IRRATIONALITY EXPONENTS OF COMPUTABLE NUMBERS [J].
Becher, Veronica ;
Bugeaud, Yann ;
Slaman, Theodore A. .
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2016, 144 (04) :1509-1521
[32]   On computable numbers with an application to the AlanTuringproblem [J].
Huws C.F. ;
Finnis J.C. .
Artificial Intelligence and Law, 2017, 25 (02) :181-203
[33]   On computable numbers, with an application to the Druckproblem [J].
Berthelette, Sophie ;
Brassard, Gilles ;
Coiteux-Roy, Xavier .
THEORETICAL COMPUTER SCIENCE, 2024, 1002
[34]   Elementarily computable functions over the real numbers and R-sub-recursive functions [J].
Bournez, O ;
Hainry, E .
THEORETICAL COMPUTER SCIENCE, 2005, 348 (2-3) :130-147
[35]   The Nakamura numbers for computable simple games [J].
Kumabe, Masahiro ;
Mihara, H. Reiju .
SOCIAL CHOICE AND WELFARE, 2008, 31 (04) :621-640
[36]   COMPUTABLE REAL FUNCTIONS [J].
HAUCK, J .
ZEITSCHRIFT FUR MATHEMATISCHE LOGIK UND GRUNDLAGEN DER MATHEMATIK, 1973, 19 (02) :121-140
[37]   ON COMPUTABLE REAL FUNCTIONS [J].
LUKAVCOVA, M .
KYBERNETIKA, 1980, 16 (03) :240-247
[38]   On computable numbers, with an application to the Entscheidungsproblem - A correction [J].
Turing, AM .
PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, 1937, 43 :544-546
[39]   COMPUTABLE ABSOLUTELY NORMAL NUMBERS AND DISCREPANCIES [J].
Scheerer, Adrian-Maria .
MATHEMATICS OF COMPUTATION, 2017, 86 (308) :2911-2926
[40]   Computable absolutely Pisot normal numbers [J].
Madritsch, Manfred G. ;
Scheerer, Adrian-Maria ;
Tichy, Robert F. .
ACTA ARITHMETICA, 2018, 184 (01) :7-29