A real number x is computable iff it is the limit of an effectively converging computable sequence of rational numbers, and x is left computable iff it is the supremum of a computable sequence of rational numbers. By applying the operations “sup” and “inf” alternately n times to computable sequences of rational numbers we introduce a non-collapsing hierarchy {Σn, Πn, Δn : n ∈ ℕ} of real numbers. We characterize the classes Σ2, Π2 and Δ2 in various ways and give (...) several interesting examples. (shrink)

A real number is recursively approximable if there is a computable sequence of rational numbers converging to it. If some extra condition to the convergence is added, then the limit real number might have more effectivity. In this note we summarize some recent attempts to classify the recursively approximable real numbers by the convergence rates of the corresponding computable sequences ofr ational numbers.

Area number x is called k-monotonically computable , for constant k > 0, if there is a computable sequence n ∈ ℕ of rational numbers which converges to x such that the convergence is k-monotonic in the sense that k · |x — xn| ≥ |x — xm| for any m > n and x is monotonically computable if it is k-mc for some k > 0. x is weakly computable if there is a computable sequence s ∈ ℕ of (...) rational numbers converging to x such that the sum equation image|xs — xs + 1| is finite. In this paper we show that a mc real numbers are weakly computable but the converse fails. Furthermore, we show also an infinite hierarchy of mc real numbers. (shrink)

In mathematics, various representations of real numbers have been investigated. All these representations are mathematically equivalent because they lead to the same real structure - Dedekind-complete ordered field. Even the effective versions of these representations are equivalent in the sense that they define the same notion of computable real numbers. Although the computable real numbers can be defined in various equivalent ways, if computable is replaced by primitive recursive (p. r., for short), these definitions lead to a number of different (...) concepts, which we compare in this article. We summarize the known results and add new ones. In particular we show that there is a proper hierarchy among p. r. real numbers by nested interval representation, Cauchy representation, b -adic expansion representation, Dedekind cut representation, and continued fraction expansion representation. Our goal is to clarify systematically how the primitive recursiveness depends on the representations of the real numbers. (shrink)

In mathematics, various representations of real numbers have been investigated. All these representations are mathematically equivalent because they lead to the same real structure – Dedekind-complete ordered field. Even the effective versions of these representations are equivalent in the sense that they define the same notion of computable real numbers. Although the computable real numbers can be defined in various equivalent ways, if “computable” is replaced by “primitive recursive” , these definitions lead to a number of different concepts, which we (...) compare in this article. We summarize the known results and add new ones. In particular we show that there is a proper hierarchy among p. r. real numbers by nested interval representation, Cauchy representation, b -adic expansion representation, Dedekind cut representation, and continued fraction expansion representation. Our goal is to clarify systematically how the primitive recursiveness depends on the representations of the real numbers. (shrink)

A real α is called a c. e. real if it is the halting probability of a prefix free Turing machine. Equivalently, α is c. e. if it is left computable in the sense that L = {q ∈ ℚ : q ≤ α} is a computably enumerable set. The natural field formed by the c. e. reals turns out to be the field formed by the collection of the d. c. e. reals, which are of the form α—β, where (...) α and β are c. e. reals. While c. e. reals can only be found in the c. e. degrees, Zheng has proven that there are Δ02 degrees that are not even n-c. e. for any n and yet contain d. c. e. reals, where a degree is n-c. e. if it contains an n-c. e. set. In this paper we will prove that every ω-c. e. degree contains a d. c. e. real, but there are ω + 1-c. e. degrees and, hence Δ02 degrees, containing no d. c. e. real. (shrink)

For semi-continuous real functions we study different computability concepts defined via computability of epigraphs and hypographs. We call a real function f lower semi-computable of type one, if its open hypograph hypo is recursively enumerably open in dom × ℝ; we call f lower semi-computable of type two, if its closed epigraph Epi is recursively enumerably closed in dom × ℝ; we call f lower semi-computable of type three, if Epi is recursively closed in dom × ℝ. We show that (...) type one and type two semi-computability are independent and that type three semi-computability plus effectively uniform continuity implies computability, which is false for type one and type two instead of type three. We show also that the integral of a type three semi-computable real function on a computable interval is not necessarily computable. (shrink)

Let h : ℕ → ℚ be a computable function. A real number x is called h-monotonically computable if there is a computable sequence of rational numbers which converges to x h-monotonically in the sense that h|x – xn| ≥ |x – xm| for all n andm > n. In this paper we investigate classes h-MC of h-mc real numbers for different computable functions h. Especially, for computable functions h : ℕ → ℚ, we show that the class h-MC coincides (...) with the classes of computable and semi-computable real numbers if and only if Σi∈ℕ) = ∞and the sum Σi∈ℕ) is a computable real number, respectively. On the other hand, if h ≥ 1 and h converges to 1, then h-MC = SC no matter how fast h converges to 1. Furthermore, for any constant c > 1, if h is increasing and converges to c, then h-MC = c-MC. Finally, if h is monotone and unbounded, then h-MC contains all ω-mc real numbers which are g-mc for some computable function g. (shrink)

The computability of reals was introduced by Alan Turing [20] by means of decimal representations. But the equivalent notion can also be introduced accordingly if the binary expansion, Dedekind cut or Cauchy sequence representations are considered instead. In other words, the computability of reals is independent of their representations. However, as it is shown by Specker [19] and Ko [9], the primitive recursiveness and polynomial time computability of the reals do depend on the representation. In this paper, we explore how (...) the weak computability of reals depends on the representation. To this end, we introduce three notions of weak computability in a way similar to the Ershov's hierarchy of Δ02-sets of natural numbers based on the binary expansion, Dedekind cut and Cauchy sequence, respectively. This leads to a series of classes of reals with different levels of computability. We investigate systematically questions as on which level these notions are equivalent. We also compare them with other known classes of reals like c. e. and d-c. e. reals. (shrink)