# 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
##### MSC:
 03D30 Other degrees and reducibilities in computability and recursion theory 03F65 Other constructive mathematics
##### Keywords:
reducibility; constructive functions
Full Text: