### Solovay reducibility and continuity

#### Abstract

The objective of this study is a better understandingof the relationships between reduction and continuity. Solovay reduction is a variation of Turing reduction based on the distance of two real numbers. We characterize Solovay reduction by the existence of a certain real function that is computable (in the sense of computable analysis) and Lipschitz continuous. We ask whether there

exists a reducibility concept that corresponds to H¨older continuity. The answer is affirmative. We introduce quasi Solovay reduction and characterize this new reduction via H¨older continuity. In addition, we separate it from Solovay reduction and Turing reduction and investigate the relationships between complete sets and partial randomness.

#### Keywords

Solovay reducibility, Lipschitz continuity, Hölder continuity, computable analysis

#### Full Text:

2. [PDF]DOI: https://doi.org/10.4115/jla.2020.12.2

This work is licensed under a Creative Commons Attribution 3.0 License.

Journal of Logic and Analysis ISSN: 1759-9008