Solovay reducibility via Lipschitz functions and signed-digit representation

Article type: Research Article

Authors: Kumabe, Masahiro^a | Miyabe, Kenshi^{b; *} | Suzuki, Toshio^c

Affiliations: [a] Department of Liberal Arts, The Open University of Japan, Chiba, Japan | [b] Department of mathematics, Meiji University, Kawasaki, Japan | [c] Department of Mathematical Sciences, Tokyo Metropolitan University, Hachioji, Japan

Correspondence: [*] Corresponding author. [email protected].

Abstract: We explore Solovay reducibility in the context of computably approximable reals, extending its natural characterization for left-c.e. reals via computable Lipschitz functions. Our paper offers two distinct characterizations: the first employs Lipschitz functions, while the second utilizes Turing reductions with bounded use with respect to signed-digit representation. Additionally, we examine multiple related reducibilities and establish separations among them. These results contribute to a refined perspective of the relationship between Solovay reducibility and computable Lipschitz functions.

Keywords: Solovay reducibility, Lipschitz function, signed-digit representation, computably approximable real

DOI: 10.3233/COM-230486

Journal: Computability, vol. Pre-press, no. Pre-press, pp. 1-27, 2024