zbMATH — the first resource for mathematics

Reducibilities of sets based on constructive functions of a real variable. (English) Zbl 0646.03038
The author introduces various types of reducibility by means of constructive functions, investigates their properties, mutual relationships and their relation to truth-table and Turing reducibility. Set A of natural numbers is said to be f-reducible to set B of natural numbers if there is a constructive function F (of constructive reals) such that for its (classical) maximal continuous extension R[F] it holds that \(R[F](r_ B)\) is defined and \(R[F](r_ B)=r_ A\), where \(r_ B=\sum_{x\in B}2^{-x-1}\). The different types of reducibility are obtained by restricting the kind of constructive functions F admitted, such as to (constructively) uniformly continuous or monotone ones.
Reviewer: B.van Rootselaar
03D30 Other degrees and reducibilities in computability and recursion theory
03F65 Other constructive mathematics
Full Text: EuDML