Reducibilities on real numbers (Q795039): Difference between revisions

The structure of recursive real functions is investigated through the notion of reducibility. The main result is that a recursive real function f maps a real number x to a real number y if and only if x is truth-table reducible to y in the sense that there is a truth-table oracle Turing machine M that computes a Cauchy sequence representation of x whenever a Cauchy sequence representation of y is given as an oracle. (An oracle Turing machine M is truth-table if the queries made by M depend only on the input and are independent of the oracle.) Other results include: a monotonic increasing recursive real function f maps x to y iff x is many- one reducible to y; a polynomial-time computable real function f maps x to y iff x is polynomial-time Turing reducible to y; and a monotonic increasing, polynomial-time computable real function f maps x to y iff x is polynomial-time many-one reducible to y. Questions are asked to find a characterization, in terms of the notion of reducibility, of the pairs of real numbers (x,y) for which there exist differential, recursive real functions f mapping x to y.