Reducibilities of sets based on constructive functions of a real variable. (English) Zbl 0646.03038

Demuth, Osvald

Commentat. Math. Univ. Carol. 29, No. 1, 143-156 (1988).

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