Robert Rettinger

MFCS Conference 2009 Conference Paper

Points on Computable Curves of Computable Lengths

• Robert Rettinger
• Xizhong Zheng

Abstract A computable plane curve is defined as the image of a computable real function from a closed interval to the real plane. As it is showed by Ko [7] that the length of a computable curve is not necessarily computable, even if the length is finite. Therefore, the set of the computable curves of computable lengths is different from the set of the computable curves of finite lengths. In this paper we show further that the points covered by these two sets of curves are different as well. More precisely, we construct a computable curve K of a finite length and a point z on the curve K such that the point z does not belong to any computable curve of computable length. This gives also a positive answer to an open question of Gu, Lutz and Mayordomo in [4].

MFCS Conference 2003 Conference Paper

Ershov's Hierarchy of Real Numbers

• Xizhong Zheng
• Robert Rettinger
• Romain Gengler

Abstract Analogous to Ershov’s hierarchy for \(\Delta^{\rm 0}_{\rm 2}\) -subsets of natural numbers we discuss the similar hierarchy for recursively approximable real numbers. Namely, with respect to different representations of real numbers, we define k -computability and f -computability for natural numbers k and functions f. We will show that these notions are not equivalent for representations based on Cauchy sequences, Dedekind cuts and binary expansions.

STOC Conference 2003 Conference Paper

The computational complexity of some julia sets

• Robert Rettinger
• Klaus Weihrauch

MFCS Conference 2001 Conference Paper

Hierarchy of Monotonically Computable Real Numbers

• Robert Rettinger
• Xizhong Zheng

Abstract A real number x is called h-monotonically computable ( h- mc), for some function h, if there is a computable sequence ( x s ) ∈ℕ of rational numbers such that h(n)∣ x-x n ∣≥∣ x-x m ∣ for any m ≥n. x is called ω -monotonically computable (ω-mc) if it is h -mc for some recursive function h and, for any c ∈ℝ, x is c-mc if it is h -mc for the constant function h ≡ c. In this paper we discuss the properties of c-mc and ω-mc real numbers. Among others we will show a hierarchy theorem of c -mc real numbers that, for any constants c 2 > c 1 ≥1, there is a c 2 -mc real number which is not c 1 -mc and that there is an ω-mc real number which is not c-mc for any c ∈ ℝ. Furthermore, the class of all ω-mc real numbers is incomparable with the class of weakly computable real numbers which is the arithmetical closure of semi-computable real numbers.