2024/08/07 by Titov, Ivan
#03D32 (Primary) 03D30 #68Q30 (Secondary) #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.2408.04074
The original notion of Solovay reducibility was introduced by Robert M. Solovay (unpublished notes) in 1975 as a measure of relative randomness. The S2a-reducibility introduced by Xizhong Zheng and Robert Rettinger (DOI:10.1007/978-3-540-27798-939) in 2004 is a modification of Solovay reducibility suitable for computably approximable (c.a.) reals. We demonstrate that Solovay reducibility implies S2a-reducibility on the set of c.a. reals, even with the same constant, but not vice versa.