Monotonically computable real numbers

被引:0
作者
Rettinger, R
Zheng, XZ
Gengler, R
von Braunmühl, B
机构
[1] Fern Univ Hagen, D-58084 Hagen, Germany
[2] Brandenburg Tech Univ Cottbus, D-03044 Cottbus, Germany
关键词
computable real number; monotonically computable real number; weakly computable real number; semi-computable real number; hierarchy;
D O I
10.1002/1521-3870(200204)48:3<459::AID-MALQ459>3.3.CO;2-0
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A real number x is called k-monotonically computable (k-mc), for constant k > 0, if there is a computable sequence (x(n))(nepsilonN) of rational numbers which converges to x such that the convergence is k-monotonic in the sense that k . \x - x(n) \ greater than or equal to \x - x(m)\ for any m > n and x is monotonically computable (me) if it is k-mc for some k > 0. x is weakly computable if there is a computable sequence (x(s))(sepsilonN) of rational numbers converging to x such that the sum Sigma(sepsilonN) \x(s) - x(s+1)\ is finite. In this paper we show that all me real numbers are weakly computable but the converse fails. Furthermore, we show also an infinite hierarchy of me real numbers.
引用
收藏
页码:459 / 479
页数:21
相关论文
共 20 条
  • [1] Weakly computable real numbers
    Ambos-Spies, K
    Weihrauch, K
    Zheng, XZ
    [J]. JOURNAL OF COMPLEXITY, 2000, 16 (04) : 676 - 690
  • [2] CALUDE C, STACS98, P596
  • [3] CALUDE C, 1999, CDMTCS RES REPORT SE
  • [4] Calude C. S., 1998, Fundamenta Informaticae, V33, P105
  • [5] CEITIN GS, 1971, ZAP NAUCN SEM LENING, V20, P290
  • [6] CEITIN GS, 1971, ZAP NAUCN SEM LENING, V20, P263
  • [7] HO CK, 1994, 9402 U CHIC DEP COMP
  • [8] Ko K.-I., 1991, Complexity Theory of Real Functions
  • [9] REDUCIBILITIES ON REAL NUMBERS
    KO, KI
    [J]. THEORETICAL COMPUTER SCIENCE, 1984, 31 (1-2) : 101 - 123
  • [10] POUREL B, 1989, COMPUTABILITY ANAL P